【数据结构】栈和队列的定义与实现

主页：HABUO🍁主页：HABUO

🍁如果再也不能见到你，祝你早安，午安，晚安🍁

1.栈

1.1 栈的定义及结构

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

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

出栈：栈的删除操作叫做出栈。出数据也在栈顶。 如下图所示：

总结：其实栈就是一个后进先出的一个容器，注意可以边进边出，什么意思呢？例如上述图，a1进栈之后可以出栈之后a2再进栈，因此一个入栈序列可以对应多个出栈序列。 

1.2 栈的实现

分析：我们前面学过了顺序表也即是可以动态增容的数组，也学过了链表，无论是带头不带头、循环不循环、双向不双向，我们是不是都搞定了。那我们思考一个问题，实现栈用哪种结构比较好呢？无论顺序表，链表我们是不是都实现过它们的增删查改，因此它们实现栈都是可以的，不过用顺序表更方便一些，因为你想嘛，我们只需要在一端进行操作，那现成有数组的形式在这放着，我们为什么去选择更复杂的结构呢😅，所以我们选择顺序表来实现栈。

大体思想见下图：

其实顺序表我们前面早已实现，用其实现栈也无非注意一些细节而已，不再详细赘述。

typedef int StackDataType;
typedef struct Stack
{
	StackDataType* _Array;
	int _top;
	int _capacity;
}Stack;
//栈初始化
void StackInit(Stack* s);
//销毁栈
void StackDestory(Stack* s);
//入栈
void StackPush(Stack* s, StackDataType x);
//出栈
void StackPop(Stack* s);
//获取栈顶元素
StackDataType StackTop(Stack* s);
//获取栈有效元素个数
int StackSize(Stack* s);
//判断栈是否为空，空返回1，非空返回0
int StackEmpty(Stack* s);

这是整个工程文件的头文件，放置栈的各种结构和接口的声明，我们主要就是进行出栈入栈操作，因此相对于顺序表而言，增删查改的接口相对也就少了，下面对其进行一一实现。

//栈初始化
void StackInit(Stack* s)
{
	assert(s);
	s->_Array = (Stack*)malloc(sizeof(Stack) * ARRAYINITSIZE);
	s->_top = 0;
	s->_capacity = ARRAYINITSIZE;
}
//销毁栈
void StackDestory(Stack* s)
{
	assert(s);
	free(s->_Array);
	s->_Array = NULL;
	s->_top = s->_capacity = 0;
}

这里需要注意的就是栈初始化的地方，我们可以将指针置为NULL但是，在入栈的时候我们就麻烦了需要进行情况的判断，因此我们就在初始化的时候直接开辟出一段空间来，省的到后面再进行判断，到入栈操作时我们只需判断栈满不满即可，满了就增容，不满就直接插入数据。

//入栈
void StackPush(Stack* s, StackDataType x)
{
	assert(s);
	if (s->_top == s->_capacity)
	{
		s->_capacity *= 2;
		Stack* temp = (Stack*)realloc(s->_Array, sizeof(Stack) * s->_capacity);
		if (temp == NULL)
		{
			printf("内存不足\n");
			exit(-1);
		}
		else
		{
			s->_Array = temp;
		}
	}
	s->_Array[s->_top] = x;
	s->_top++;
}
//出栈
void StackPop(Stack* s)
{
	assert(s);
	assert(s->_top != 0);
	s->_top--;
}

入栈操作相对于前面顺序表的增删查改的操作，这里就太简单了，不赘述，有需要了解的翻看前面博客顺序表的实现即可。这里需要注意assert(s->top != 0)，我们在这里加一个断言是防止栈里面没有元素，我们还进行出栈操作。

其它的接口只需返回相应的变量即可，这里我们会不会有个问题？既然直接返回相应变量，那我们还为什么去建立一个接口，其实这是为了保持我们接口的一致性，直接调用即可。 

2.队列

2.1 队列的定义及结构

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

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

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

总结：队列与我们日常排队的情形大同小异，谁先进谁就先出嘛，绝对不存在后进先出的情况，因此呢，也就意味着一种入队序列只能是对应一种出队序列。

2.2 队列的实现

分析：和上面栈的实现一样，我们采取哪种结构来进行实现呢？因为这里需要一头进，另一头出，只要是这种两头操作的我们顺序表是不是不太好，因为你只要头进行操作了，顺序表后面的数据是不是需要移动，那这里效率就下来了，所以顺序表不太好，那链表用那种形式呢？其实单链表是不完全就足够这里的功能了，为什么呢？因为我们就仅仅需要个头删或者尾插，这对单链表来说是最基本的功能了，那我们能用单链表的就尽量不要其它链表的形式，因为毕竟没必要，何必再去多存地址。综上，我们采用单链表的形式来实现队列。

typedef int QueueDataType;
typedef struct QueueListNode
{
	QueueDataType _data;
	struct QueueListNode* _next;
}QueueListNode;
typedef struct Queue
{
	QueueListNode* _front;
	QueueListNode* _rear;
}Queue;
// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QueueDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QueueDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QueueDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

这是整个工程文件的头文件，放置队列的各种结构和接口的声明，其实和栈的接口的实现基本差不多，这里唯一需要注意的是我们通过了一个结构体存放了连个头尾指针，为什么要这样做？目的就是在于使我们接口为了保持一致性，如果不这样做有部分接口需要传二级指针，那这里我们传过去结构体的地址是不是就能对结构体里的变量进行操作，换言之这些指针是不是就能改变了，而不仅仅是那些形参进行改变，我们主要就是进行入队列和出队列操作，因此相对于单链表而言，增删查改的接口相对也就少了，下面对其进行一一实现。 

// 队尾入队列 
void QueuePush(Queue* q, QueueDataType data)
{
	assert(q);
	if (q->_front == NULL)
	{
		QueueDataType* temp = (QueueListNode*)malloc(sizeof(QueueListNode));
		if (temp == NULL)
		{
			printf("内存不足\n");
			exit(-1);
		}
		else
		{
			q->_front = q->_rear = temp;
		}
	}
	else
	{
		QueueListNode* temp = (QueueListNode*)malloc(sizeof(QueueListNode));
		if (temp == NULL)
		{
			printf("内存不足\n");
			exit(-1);
		}
		else
		{
			q->_rear->_next = temp;
			q->_rear = temp;
		}
	}
	q->_rear->_data = data;
	q->_rear->_next = NULL;
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->_front != NULL);
	QueueListNode* frontNext = q->_front->_next;
	free(q->_front);
	q->_front = frontNext;
}

你看这里的入队列就分情况了，因为这和顺序表不一样，如果我们在初始化的时候没有直接进行开辟空间，为什么？因为你都不知道要放什么数据，即使你建立节点，到入队列时还是要分情况，一种是第一次入队列，你只需要将你初始化的节点的val改成所需要的数据，如果要新建立节点，你就需要再malloc一个节点。因此无论怎么样都需要分两种情况，顺序表就不需要这样，顺序表我们可以通过下标进行访问嘛。

其它的接口大同小异都是返回各种变量的数据即可，不再赘述。

总结：这篇博客我们认识两个新的数据结构，我们会不会有个这样的问题？哪里可以用到这些数据结构呢？对于栈，其实用处还蛮大的，比如如果我们想设计一个迷宫游戏，那这个走到死路时我们是不是要后退啊，这就涉及一个后进先出的问题，就可以利用我们的栈来进行实现。对于队列，日常生活中还是很常见的，我们都去过银行或者什么办公场所，是不是都有一个排队报号机，这就是一个非常典型的队列问题，先来的先排队，到了就出队列。因此今天我们所学的两种数据结构，肯定会对我们有所启发，希望我们都能有所收获。💯

🏋不是每一粒种子都能开花，但播下种子就比荒芜的旷野强百倍🏋

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：腾讯云自媒体同步曝光计划 - 腾讯云开发者社区-腾讯云