数据结构：栈和队列与栈实现队列（C语言版）

前言

1.栈

1.1 栈的概念及结构

1.2 栈的底层数据结构选择

1.2 数据结构设计代码（栈的实现）

1.3 接口函数实现代码

（1）初始化栈

（2）销毁栈

（3）压栈

（4）出栈

（5）获取栈顶元素

（6）获取栈中有效元素的个数

（7）检测栈是否为空

1.4 测试函数

2. 队列

2.1 队列概念及结构

2.2 队列的底层数据结构的选择

2.2 数据结构设计代码（队列的实现）

2.3 接口函数

（1）初始化队列

（2）销毁队列

（3）队尾入队列

（4）队头出队列

（5）获取队列头部元素

（6）获取队列尾部元素

（7）获取队列中有效元素个数

（8）检测队列是否为空

2.4 测试函数

3. 栈和队列的源代码

3.1 栈

（1）Stack.h

（2）Stack.c

（3）STtest.c

3.2 队列

（1）Queue.h

（2）Queue.c

（3）Qtest.c

总结

前言

这篇文章是关于栈和队列的C语言实现，干货满满，大家可以边看边手写代码，最后附上栈和队列的参考代码。

1.栈

1.1 栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

这个数据结构可以理解为炸串。在最开始，插入丸子时，要插到这根签的最底部，就是入栈。开始吃的时候，一般从最上面的丸子入手，就是出栈。

1.2 栈的底层数据结构选择

我们学过顺序表和链表两种数据结构，用那种会更好呢？

相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。不用挪动数据，删除操作也很简单。
而链表如果要入栈，就是链表的尾插，我们需要找到链表的尾结点，效率低。出栈也是一样。

1.2 数据结构设计代码（栈的实现）

在用C语言实现栈各种接口函数，需要创建三个文件，分别是STtest.c，Stack.c和Stack.h。

STtest.c文件用来测试接口函数是否能成功。
Stack.c文件里面放的是各种接口函数实现的代码
Stack.h文件放置各种头文件的声明，栈数据结构的设计和接口函数的声明。下面的代码就是放在此文件中。

typedef int STDataType;
// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
	STDataType _a[N];
	int _top; // 栈顶
}Stack;

// 支持动态增长的栈
typedef struct Stack
{
	STDataType* a;
	int top;      //栈顶
	int capacity; //容量
}ST;

//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestroy(ST* ps);
//压栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//获取栈顶元素
STDataType StackTop(ST* ps);
//获取栈中有效元素个数
int StackSize(ST* ps);
//检测栈是否为空，为空返回true
bool StackEmpty(ST* ps);

1.3 接口函数实现代码

（1）初始化栈

初始化栈一开始要断言，断言来判断ps指针是否为空，如果为空会直接终止程序并给出提示，方便之后的调试，之后的断言不再赘述。指针指向空，内部整型数据赋值为0。但是top得注意，top其实也是个下标。看下面的注释，top可以有两种赋值方式，只是表示不同意思。

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0;//表示指向栈顶的下一个元素
    //ps->top = -1 ///表示指向栈顶元素
	ps->capacity = 0;
}

（2）销毁栈

因为我们是以数组为基础，是动态开辟的连续空间，直接释放掉ps中的数组指针，并要置为空。

void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;//易错
	ps->top = ps->capacity = 0;
}

（3）压栈

栈的压栈操作跟顺序表的尾插类似，先要检查内部空间容量是否足够，一开始给四个该数据结构的空间，之后的按两倍来扩容。最后就是插入数据，栈顶减一。

void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}

（4）出栈

这次不仅要判断ps是否不为空指针，还要判断栈内是否有元素，这样才可以删除元素，让栈顶减一即可。

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	ps->top--;
}

（5）获取栈顶元素

这里的判断跟上个接口函数一样，只有栈内有元素，才能取栈顶元素。

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->a[ps->top - 1];
}

（6）获取栈中有效元素的个数

此时的top表示的是栈顶的下一个元素的下标，刚好就是元素个数，直接返回栈顶top

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

（7）检测栈是否为空

很多人会写个if语句判断，其实可以直接像下面一样写，ps->top == 0变成一个判断语句，如果为真返回一个部位0的数，如果为假返回0。

bool StackEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

1.4 测试函数

我们写两个测试函数，第一个测试函数，是出栈和入栈的操作，可以调试查看。第二个测试函数是栈的数据打印，需要使用StackTop获取栈顶元素，然后将打印的数据出栈。

void TestStack1()
{
	ST st;
	StackInit(&st);

	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);

	StackPop(&st);
	StackPop(&st);
	StackPop(&st);
	StackPop(&st);
	StackPop(&st);

	StackDestroy(&st);
}

void TestStack2()
{
	ST st;
	StackInit(&st);

	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);

	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	StackDestroy(&st);
}

int main()
{
	TestStack1();
	TestStack2();

	return 0;
}

输出结果：

2. 队列

2.1 队列概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

这个数据结构可以理解为在银行取号，先取号的人，就是入队列。然后先取到号的人，就先去窗口处理业务，这就是出队列。

2.2 队列的底层数据结构的选择

跟栈一样，队列也可以用顺序表和链表来实现，那哪一个更好呢？

相较于数组，使用链表更优一些。队列的入队和出队，分别是链表的尾插和头删，不过我们会创建两个指针指向头结点和尾结点，所以不会有时间的消耗。
而数组在头部插入和删除数据，都要挪动数据，效率较低。

链表的数据结构存储的是一个数据变量，和指向下一个结点的指针变量。我们入队列和出队列分别在队尾和队头，所以我们在队列的数据结构定义两个链表的指针变量head和tail，表示队头和队尾

2.2 数据结构设计代码（队列的实现）

跟栈的实现一样，首先要创建三个文件Qtest.c，Queue.c和Queue.h。

Qtest.c文件用来测试接口函数是否能成功。
Queue.c文件里面放的是各种接口函数实现的代码
Queue.h文件放置各种头文件的声明，栈数据结构的设计和接口函数的声明。下面的代码就是放在此文件中。

// 链式结构：表示队列
typedef int QDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;

// 队列的结构
typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;

//初始化队列
void QueueInit(Queue* pq); 
//销毁队列
void QueueDestroy(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq, QDataType x);
//队头出队列
void QueuePop(Queue* pq);
//获取队列头部元素
QDataType QueueFront(Queue* pq);
//获取队列尾部元素
QDataType QueueBack(Queue* pq);
//获取队列中有效元素个数
int QueueSize(Queue* pq);
//检测队列是否为空，如果为空返回true
bool QueueEmpty(Queue* pq);