数据结构——栈和队列

前言

       栈和队列是两种不同的线性数据结构。这两种数据结构相比之前的基础数据结构顺序表和链表来说，特点更加突出，实用性也更强。而这两种数据结构的实现也建立在顺序表和链表的基础之上，建议先了解顺序表和链表的原理再学习栈和队列。

【顺序表解析】传送门:http://t.csdn.cn/TZ5mw。

【链表解析】传送门:http://t.csdn.cn/CRTmg。

---

1 栈

1.1 区分栈与栈区

       可能有些同学在学习内存的时候听说过内存中的栈区。栈区与本文中讨论的栈是有本质区别的。栈区是内存中的一块区域，而栈是一种数据结构。

1.2 思路引入

       不知道大家有没有去过超市，由于网上购物的兴起，我已经很久没有去过线下的超市了。记得小时候去超市的时候，由于要买的东西比较多，通常会推上一个购物车，这样一来我可以把挑选好的商品放入购物车中，等到结账时再拿出来。

        到结账时，要把商品一件一件的放到收银台上，在这个过程中我们可以发现，我们通常都是先拿位于上方的商品，再拿下方的。这是因为上方商品压住了下方商品，导致我们难以先拿下方商品。而这些商品的相对位置其实与我们将其放入购物车的时间有关，越早放入购物车，商品就越位于下方。因此，后进入购物车的商品，通常先离开购物车，这就是栈的特点。

1.3 基本思路

       栈(Stack)是一种线性数据结构，可以想象一下把购物车压缩成线状（竖直放置），每个高度上只能放一件商品，如下图。

        通常，我们将最后一个元素的位置称为栈顶，第一个元素的位置称为栈底。如此一来，插入和删除元素都只能在栈顶进行，我们通常把栈的插入称为入栈，删除称为出栈。

        其实与上图类似的图形，在学习基础数据结构时我们就见到过。我们将上图顺时针旋转90度可以得到以下图形。

        这样看是不是清楚多了，这其实就是一个顺序表，而所谓的入栈和出栈其实就是顺序表的尾插和尾删。

1.4 栈的实现 

       栈的实现可以使用顺序表，也可以使用链表。这里我选用顺序表进行模拟实现。

1.4.1 接口

       既然是通过顺序表来实现栈，那么模拟的结构也与顺序表相似，区别在于栈有唯一的插入和删除方式，也就没有头插，尾插，随机插入这类说法了。

       由于在栈里只能操作栈顶元素，因此这里多了一个获取栈顶元素的功能，用来访问栈内元素。另外，在使用栈的时候，有时会以栈是否为空作为判断条件，因此多出一个判空功能。学习过顺序表后，下面的实现看上去就非常简单了。

#pragma once
#include
#include
#include
#include
 
#define MAX 100    //最大容量
#define STACKADD 2 //扩容容量
 
typedef int SDateType;
typedef struct Stack
{
	SDateType* data;
	int top;
	int capacity;
}Stack;
 
//初始化栈
void StackInit(Stack* ps);
//判空
bool StackEmpty(Stack* ps);
//入栈
void StackPush(Stack* ps, SDateType x);
//出栈
void StackPop(Stack* ps);
//获取栈顶元素
void StackGetTop(Stack* ps, SDateType* d);
//销毁栈
void StackDestroy(Stack* ps);

1.4.2 初始化与判空

      由于我们是用顺序表来实现栈，那么这里我们就可以参考顺序表的初始化。不同点在于，由于栈顶是栈最后一个元素所在的位置，因此在初始化时，由于栈为空，那么栈顶的位置显然不是0。在这里我们可以将top初始化为-1，那么当第一个元素入栈时，让top自增1，栈顶位置就变成了0，这样就解决了这一问题。

void StackInit(Stack* ps)
{
    assert(ps);
    ps->data = (SDateType*)malloc(STACKADD * sizeof(SDateType));
    if (ps->data == NULL)
    {
        perror("Init malloc:");
        return;
    }
    ps->top = -1;
    ps->capacity = STACKADD;
}

        完成初始化后，再来看判空就非常简单了，因为初始化后的栈不就是一个空栈吗？那么判空的条件就是top等于-1。

bool StackEmpty(Stack* ps)
{
    assert(ps);
    if (ps->top != -1)
        return false;
    else
        return true;
}

1.4.3 入栈，出栈与获取栈顶元素

       根据上面的分析，入栈和出栈的操作就是顺序表的尾插和尾删。需要注意点的是栈顶的位置并不是最后一个元素的下一个位置，因此需要在top+1位置插入。过程我就不过多介绍了，不理解的可以先学习顺序表。

void StackPush(Stack* ps, SDateType x)
{
    assert(ps);
    ps->top++;
    if (ps->top == ps->capacity && ps->capacity != MAX)
    {
        ps->data = (SDateType*)realloc(ps->data, (ps->capacity + STACKADD) * sizeof(SDateType));
        if(ps->data==NULL)
        {
            perror("Push realloc:");
            return;
        }
    }
    ps->data[ps->top] = x;
}

 

void StackPop(Stack* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    ps->top--;
}

        关于获取栈顶元素，这个操作比较简单，就是通过下标访问数组元素，将栈顶元素值赋给传入的指针变量所指向的变量。

void StackGetTop(Stack* ps, SDateType* d)
{
    assert(ps);
    assert(!StackEmpty(ps));
    *d = ps->data[ps->top];
}

1.4.4 栈的销毁

       动态开辟的空间使用完毕后都要手动释放，而栈的销毁只要有首元素的地址（栈底地址）即可。

void StackDestroy(Stack* ps)
{
    assert(ps);
    free(ps->data);
    ps->data = NULL;
}

1.5 疑难杂症

1.5.1 为何不采用头插和头删

       我在画图时将竖直的栈顺时针旋转90度形成了顺序表，那么可不可以逆时针旋转90度呢？这样一来，我们的入栈和出栈操作就变成了顺序表的头插和头删。而在顺序表中，尾插和尾删的时间复杂度均为O(1)，而头插和头删的时间复杂度均为O(n)。这就是入栈和出栈采用尾插和尾删而不是头插和头删的原因。

1.5.2 为何不采用链表实现 

       与顺序表相比，链表的头插和头删的时间复杂度均为O(1)，并且在其它方面链表的效率也不输顺序表。在栈的实现中，链表唯一一点不如顺序表的地方就在于销毁。链表的节点是散布内存各处的，销毁时需要通过遍历逐一释放节点，时间复杂度为O(n)。而顺序表的数据存储在一段连续的空间上，只需要空间的首地址即可一键释放，时间复杂度为O(1)。这就是文章采用顺序表实现栈的原因。

2 队列 

2.1 思路引入

       队列(Queue)在生活中其实非常常见，如在食堂排队打饭的队列、在超市收银台排队等待支付的队列，或是等待办理某项业务的队列。这些队列的出现通常是为了控制秩序，提高业务办理的效率。

       数据结构中所说的队列与我们生活中的队列有一个共同点的特点。假设我们把排队的人看成一个一个的节点，排在最前面的人称为队头，最后的人称为队尾。由于排队是为了办理某项业务，那么当队头的人办理完业务之后就可以离开了，称为出队列，而如果有新需要办理该业务的人，则他应该排在队尾，称为入队列。

2.2 基本思路

       根据上面的分析，队列的数据插入和删除的特点为一侧插入，另一侧删除。也就是说，我们可以采用头插加尾删的组合，也可以采用头删加尾插的组合。

       如下图（图中箭头方向为链表节点的指针方向，不是队列朝向）。

2.3 队列的实现

       队列作为一种线性数据结构，我们同样可以用顺序表或者链表还原。我认为最好理解的实现方式就是采用头删加尾插的链表来实现队列。

2.3.1 接口

       采用链表来实现，首先要做的就是声明所需的链表节点结构。而对于队列，这里我选择再声明一个Queue结构，可以保存队列的队头节点和队尾节点的地址，这样一来就能通过地址更快速地找到队尾节点而不是遍历链表。

#pragma once
#include
#include
#include
#include
 
typedef int QDataType;
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;
 
typedef struct Queue
{
	QueueNode* front;
	QueueNode* rear;
}Queue;
 
//初始化队列
void QueueInit(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//取队头元素
void QueueGetFront(Queue* pq, QDataType* d);
//销毁队列
void QueueDestroy(Queue* pq);

2.3.2 初始化与判空

       我们期望的初始化结果应该是一个空队列，也就是一个没有任何节点的队列，那么我们的初始化就并不需要创建节点，只需要将队列的front指针和rear指针置空即可。

       那么队列的判空条件也就显而易见了，当front指针为空时，该队列即为空队列。代码如下。

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->front = pq->rear = NULL;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	if (pq->front == NULL)
		return true;
	else
		return false;
 
}

2.3.3 入队列、出队列与获取队头元素

       前面也提到过，我们这里的入队列采用尾插，出队列采用头删，这样的方式与生活最接近，更好理解。

       在入队列时，我们可以通过队尾指针直接访问队尾节点，大大提高了尾插效率，其它与链表的尾插无太大区别，同样需要注意处理链表为空的特殊情况。出队列则与链表头删无区别。这样一来，入队列和出队列的时间复杂度均为O(1)。

       如果采用顺序表来实现队列，将无可避免使用顺序表的头插或者头删，而其时间复杂度将达到O(n)。

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	if (pq->front == NULL)
	{
		pq->front = pq->rear = (QueueNode*)malloc(sizeof(QueueNode));
		if (pq->front == NULL)
		{
			perror("Push malloc:");
			return;
		}
		pq->rear->data = x;
		pq->rear->next = NULL;
	}
	else
	{
		QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
		if (newnode == NULL)
		{
			perror("Push malloc:");
			return;
		}
		pq->rear->next = newnode;
		pq->rear = pq->rear->next;
		pq->rear->data = x;
		pq->rear->next = NULL;
	}
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	QueueNode* prev = pq->front;
	if (pq->front == pq->rear)
		pq->rear = NULL;
	pq->front = pq->front->next;
	prev->next = NULL;
	free(prev);
}

       获取队头元素较简单，这里直接看代码。

void QueueGetFront(Queue* pq, QDataType* d)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	*d = pq->front->data;
}

2.3.4 队列的销毁 

       由于本文使用链表实现队列，故销毁队列与销毁链表的方式一样，通过循环遍历来销毁。

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->front;
	while (cur)
	{
		cur = cur->next;
		pq->front->next = NULL;
		free(pq->front);
		pq->front = cur;
	}
	pq->rear = NULL;
}

---

结束语 

       本篇主要介绍了栈和队列两种数据结构的实现思路，并用顺序表和链表分别模拟实现。栈和队列在部分算法中应用较多，非常有必要学习。如果文章内容有误，欢迎各位大佬指正。