栈和队列

栈

栈的定义

引用《数据结构》严蔚敏中关于栈的定义：

栈是限定仅在表尾进行插入或删除操作的线性表。

首先，栈是一种线性表，其中的元素仍然具有前驱和后继的逻辑结构；其次，栈的基本操作被限定在了表尾，我们只能从表尾进行插入和删除操作。这导致栈中的元素具有所谓后进先出（Last In First Out, LIFO)的特性。由于我们从表尾加入元素，先加入的元素会离表尾越来越远，由于我们只能从表尾删除，越早进入栈中的元素越晚被删除。

下面我们来明确几个概念：

栈顶，指的是栈中可以进行删除和插入操作的一端，也就是表尾。
栈底，指的是栈中不能进行删除和插入操作的一端，也就是表头。
入栈，即元素被插入栈中。
出栈，即元素被从栈中删除。

栈的逻辑机构与线性表一致，事实上，栈是一种操作受限条件下的线性表。

栈的基本操作

栈的基本操作也同样可以分为创销增删查。由于栈只能从栈顶（表尾）进行插入和删除，这里我们只定义两个函数：

//将e入栈
bool Push(Stack &S, ElemType e);

//将栈顶元素出栈，并将值保存在e
bool Pop(Stack &S, ElemType &e);

这两个操作分别是栈上的插入和删除操作，如果我们要创建一个栈，首先初始化一个空栈，然后进行若干次入栈操作即可；而销毁一个栈也只要进行若干次出栈操作然后释放资源即可。

我们也可以用下面的函数得到栈顶元素的值，但不删除栈顶元素：

ElemType GetTop(Stack S);

栈的出栈顺序和入栈顺序

对于给定的入栈顺序，并不是所有的出栈顺序都是合法的。比如我们假设以\(1, 2, 3, 4\)的顺序进栈，对于出栈顺序\(4, 2, 1, 3\)，我们有如下的分析：

若\(4\)第一个出栈，根据进栈顺序，我们需要先把\(1, 2, 3\)入栈，然后在\(4\)入栈后马上执行出栈。

这之后，从栈底到栈顶的元素依次是\(1, 2, 3\)。

由于栈只能从栈顶删除元素，因此下一个出栈的应当是\(3\)，而不可能是\(2\)。

有了上面这个例子，我们大致就可以体会到，并不是所有的出栈顺序都是合法的。对于一个给定的入栈顺序，我们有这样的结论：

对于一个给定的入栈顺序，其可能的出栈顺序一共有：

\[\frac{1}{n+1}\binom{2n}{n} \]
这个数在组合数学中被称为卡特兰数。

当然，对于给定的出栈顺序和入栈顺序，我们还可以求可能的操作，对于入栈顺序\(1, 2, 3, 4\)和出栈顺序\(3, 2, 4, 1\)，我们有以下操作：

先进行三次Push，此时栈中元素为\(1, 2, 3\)

再进行两次Pop，此时栈中的元素为\(1\)，出栈的顺序为\(3, 2\)

然后进行一次push和一次Pop，此时的栈中元素为\(1\)，出栈顺序为\(3, 2, 4\)

最后进行一次Pop，栈为空，出栈顺序为\(3, 2, 4, 1\)

以上就是通过一系列操作从给定的输入顺序得到给定的输出顺序的例子。对于这一类的问题，还可以有很多种类的问法，比如如果第三个出栈的元素是\(x\)，第四个元素有几种可能？这些问题的分析方法其实都大同小异，只要对于元素的进出栈情况进行分类讨论就可以了。

顺序栈

下面我们讲一下栈的具体实现，第一种就是顺序栈。顺序栈和顺序表的很相似，大致的定义就是：

typedef struct {
	ElemTyped data[MaxSize];
    int top;
}SqStack;

在上面的定义中，我们有一个data数组用于存放数据，而top用于指示此时栈顶的位置。对于初始化一个栈，此时的栈是空的，top置为\(0\)肯定是不合适的，因为\(0\)这个位置也是可以存放元素的，不过我们只需要将top置为\(-1\)就可以了，这就表明此时的栈是空的，如果要判断一个栈是否为空，只需要判断top是否为\(-1\)即可。代码如下：

void InitStack(SqStack &S) {
    S.top = -1;
}

bool Empty(SqStack &S) {
    return S.top == -1;
}

对于顺序栈的入栈和出栈，代码如下：

bool Push(SqStack &S, ElemType e) {
    if (S.top == MaxSize - 1)
        return false;
    S.data[++S.top] = e;
    return true;
}

bool Pop(SqStack &S, ElemType &e) {
    if (S.top == -1)
        return false;
    e = S.data[S.top--];
    return true;
}

这里要注意++i这种语法，如果写错成i++就会导致代码出现错误，至于i++和++i的区别，这里不多介绍；其次，在删除操作中，我们没有修改data数组中的数据，而是直接把top递减了，这是因为，我们无需在乎数组中驻留的“脏数据”，只要其逻辑上不在栈中即可。

对于读栈顶的操作，只要返回S.data[S.top]即可。

顺序栈的优点是明确的，操作简单且容易实现。但是顺序栈也有大小不可变的缺点，这导致了栈在使用中的不灵活，一定程度上也会造成空间的浪费，在栈满了的情况下还会导致上溢，也就是在栈满的情况下进行了插入操作。

共享栈

共享栈是一种两个栈共享一块数据存储空间的栈，定义如下：

typedef struct {
    ElemType data[MaxSize];
    int top1, top2;
}ShareStack;

在初始化的时候，我们将top1置为\(-1\)，将top2置为\(MaxSize\)，分别作为栈1和栈2的栈顶的指示。在栈1进行插入的时候，先将top1递增，再在相应的位置插入数据，而栈2则是将top2递减，再将数据放入对应位置。删除操作则类似。其实这相当于内存中的堆栈模型，两个栈各据一端，相向增长。判空操作和普通的栈类似，而判满操作则可以：

bool Empty(ShareStack S) {
    return S.top1 + 1 == S.top2;
}

共享栈在一定程度上缓和了上溢的情况，对于两个栈，假设他们的\(MaxSize = n\)，在这个情况下，只要其中一个栈的元素个数达到了\(n\)，再次进行插入就会造成上溢，而在使用共享栈的情况下，即使某个栈的元素个数达到了\(n\)，只要另一个栈没满，就不会上溢，相当于把另外一个栈的空资源给了这个栈。

链栈

链栈也就是用链式实现的栈，其定义与链表的相似：

typedef struct Node{
    ElemType data;
    Node *next;
}Node, *LinkStack;

我们定义栈顶在表头的位置，对于带头结点的链栈，我们可以写出其插入和删除操作：

bool Push(LinkStack &S, ElemType e) {
    Node *q = (Node *)malloc(sizeof(Node));
    if (q == NULL)
        return false;
    q->next = S->next;
    S->next = q;
    return true;
}

bool Pop(LinkStack &S, ElemType &e) {
    if (S->next == NULL)
        return false;
    Node *q = S->next;
    S->next = q->next;
    free(q);
    return true;
}

在上面的实现中，注意到插入操作是没有判满的，因为链栈可以动态扩容，一般来说不会满，除非内存耗尽。

链栈由于其动态扩容的特性，相较于顺序栈，不再受限于固定的大小，但相应的，由于需要额外的存储空间存放下一个结点的地址，其存储密度是更小的。

队列

定义

队列是一种只允许在一端进行插入，另一端进行删除的线性表。与栈相似的，队列也是一种线性表，其也具有前驱和后继的逻辑结构。但是与栈不同的是，队列是所谓先进先出（First In First Out, FIFO）的，这就像现实中的排队一样，人们从队尾加入对于，从队头离开队伍，只有队头的人才能先获取相应的服务，然后离开，这也保证了排队的公平性。

我们把队列中进行删除操作的一端称为队头(front)，将进行删除操作的一端称为队尾(rear)。在队列中，我们记录队列的队头和队尾，并且进行相应的操作。

操作

队列同样有创销增删查的基本操作，我们有如下操作：

//初始化
void InitQueue(Queue &Q);

//销毁
void DestoryQueue(Queue &Q);

//插入
bool EnQueue(Queue &Q, ElemType e);

//删除
bool DeQueue(Queue &Q, ElemType &e);

//查找队首元素
ElemType GetHead(Queue Q);

上面这些操作就是队列的基本操作，对于队列我们要注意其判空和判满的操作，不同的实现需要不同的判空判满方式，下面我们会穿插介绍。

顺序队列

队列的顺序实现和栈类似，同样是需要一个数组存放数据，不过栈需要两个变量用以标记队头和队尾，如下：

typedef struct {
    ElemType data[MaxSize];
    int front, rear;
}SqQueue;

在这一段代码中，front用于指示队头，rear用于指示队尾。对于front，每删除一个元素，其就往前一位，而rear则是每删除一个元素，就往后一位，如果我们用最简单的实现方法，在若干次删除操作以后，front就会越来越大，如果我们只在front和\(MaxSize - 1\)的范围内存储数据，这就会导致存储空间越来越小，因为front越来越接近\(MaxSize\)，这是不合理的。因此我们需要一个办法来克服这个问题，这就要引出我们的下一个知识点，循环队列：

循环队列

循环队列是顺序队列的一种具体实现方式，在rear不断增大到\(MaxSize-1\)后，如果要进行一次新的插入，我们并不是直接判断队列为满，而是将rear置为\(0\)，，在\(0\)的位置插入新的元素，这样，我们就可以充分利用\(0\)到front之间的空的存储空间。具体的，我们看看插入和删除的代码，这里我们假设rear是指示队尾的下一个位置：

bool EnQueue(SqQueue &Q, ElemType e) {
    if ((Q.rear + 1) % MaxSize == Q.front)
        return false;
    Q.data[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MaxSize;
    return true;
}

bool DeQueue(SqQueue &Q, ElemType &e) {
    if (Q.rear == Q.front)
        return false;
    e = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return ture;
}

注意这里的判空和判满操作，事实上，在上面的这种实现方式下，我们是牺牲了一个存储单元的，如果我们不牺牲这个单元，那么在队满的时候，rear和front会重叠，这与我们的初始条件是一致的，这样我们就不能通过两个指针的相对位置来判断此时的空和满了。这里我们介绍三种解决办法：

如上述代码的办法，牺牲一个存储空间，当rear在front后面一个位置的时候就判断为满
在定义中加入size变量，当size为\(0\)时队列为空，size为\(MaxSize\)的时候，队列为满
在定义中加入tag变量，其为\(0\)时标记最近一次操作为删除，其为\(1\)时标记最近一次操作为插入，只有删除操作可以让队列空，只有插入操作可以让队列满，结合这个变量和两个指针的相对位置就可以判断此时队列的状态了。要注意，这个变量应当初始化为\(0\)，因为初始状态表为空

根据front和rear的具体语义不同，判空和判满的操作也会有所不同，这是需要具体问题具体分析的。

如果我们要判断一个循环队列的队列长度，有：

\[len(Q) = (rear + MaxSize - front) \mod{MaxSize} \]

这个很好理解，\(MaxSize - front\)计算的是front到数组边界的距离，其加上rear到另一个边界的距离，就是总的长度，这是一个定性的分析，具体的还要考虑两个指针的相对位置，分情况讨论。

链队列

循环队列是一个很精巧的设计，但是其逻辑并不是很简单，下面介绍链队列，就具有逻辑和使用简单的有点：

typedef struct Node{
    ElemType data;
    Node *next;
}Node;

typedef struct {
    Node *front, *rear;
}LinkQueue;

在上面的定义中，我们将front和rear集成到了一个结构体里，这个结构体用来表示链队列。

我们定义链队列的队头在链表的表头，队尾在链表的表尾，这样的好处是可以简化插入和删除操作，对于带头结点的链队列，我们有：

bool EnQueue(LinkQueue &Q, ElemType e) {
    Node *q = (Node *)malloc(sizeof(Node));
    if (q == NULL)
        return false;
    q->next = Q.rear->next;
    Q.rear->next = q;
    Q.rear = q;
    return true;
}

bool DeQueue(LinkQueue &Q, ElemType &e) {
    if (Q.front == Q.rear)
        return false;
    Node *q = Q.front->next;
    e = q->data;
    Q.front->next = q->next;
    if (Q.rear == q)
        Q.rear = Q.front;
    free(q);
    return true;
}

注意到，这里的插入也没有判满，理由和链栈一致。另外，我们在删除操作中需要注意删除的是否是队列中的最后一个元素，如果是，就需要让rear指向头结点。