4.1-4.2 栈的定义

4.2.1 栈的定义

栈是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何数据元素的栈称为空栈。栈又称为后进先出(Last In First Out)的线性表，简尔LIFO结构。
它的特殊之处就在于限制了这个线性表的插入和删除位置，它始终只在栈顶进行。这也就使得：栈底是固定的，最先进栈的只能在栈底。
栈的插入操作，叫作进栈，也称压栈、入栈(push)。

栈的删除操作，叫作出栈，也有的叫作弹栈(pop)。

4.3 栈的抽象数据类型

ADT 栈(stack)
Data
    同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
    InitStack(*s)：初始化操作，建立一个空栈s。
    DestroyStack(*s)：若楼存在，则销毁它。
    ClearStack(*s)：将栽清空。
    StackEmpty(S)：若为空，返回true，否则返回false。
    GetTop(s，*e)：若栽存在且非空，用e返回s的栽顶元素。
    Push(*s，e)：若栈S存在，插入新元素e到栈S中并成为栈顶元素。
    Pop(*S，*e)：删除栈S中栈顶元素，并用e返回其值。
    StackLength(s)：返回栈s的元素个数。
endADT

4.4 栈的顺序存储结构及实现

4.4.1 栈的顺序存储结构

栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。线性表是用数组来实现的。
我们定义一个top变量来指示栈顶元素在数组中的位置，它可以来回移动，意味着栈顶的top可以变大变小，但无论如何游标不能超出栈的长度。同理，若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判定条件定为top等于-1。

栈的结构定义：

typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */
/* 顺序栈结构 */
typedef struct
{
        SElemType data[MAXSIZE];
        int top; /* 用于栈顶指针 */
}SqStack;

若现在有一个栈，StackSize是5，则栈普通情况、空栈和栈满的情况示意图如图4-4-2所示。

4.4.2 栈的顺序存储结构——进栈操作

对于栈的插入，即进栈操作，其实就是在栈顶插入一个元素。
进栈操作push，其代码如下：

/* 插入元素e为新的栈顶元素 */
Status Push(SqStack *S,SElemType e)
{
        if(S->top == MAXSIZE -1) /* 栈满 */
        {
            return ERROR;
        }
        S->top++;   /* 栈顶指针增加一 */
        S->data[S->top]=e;  /* 将新插入元素赋值给栈顶空间 */
        return OK;
}

4.4.3 栈的顺序存储结构——出栈操作

出栈操作pop，代码如下：

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(SqStack *S,SElemType *e)
{
        if(S->top==-1)
                return ERROR;
        *e=S->data[S->top]; /* 将要删除的栈顶元素赋值给e */
        S->top--;   /* 栈顶指针减一 */
        return OK;
}

两者没有涉及到任何循环语句，因此时间复杂度均是O(1)。

4.5 两栈共享空间

如果我们有两个相同类型的栈，我们为它们各自开辟了数组空间，极有可能是第一个栈已经满了，再进栈就溢出了，而另一个栈还有很多存储空间空闲。这又何必呢？我们完全可以用一个数组来存储两个栈，只不过需要点小技巧。
数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n-1处。这样，两个栈如果增加元素，就是两端点向中间延伸。
其实关键思路是：它们是在数组的两端，向中间靠拢。top1和top2是栈1和栈2的栈顶指针，可以想象，只要它们俩不见面，两个栈就可以一直使用。
从这里也就可以分析出来，栈1为空时，就是top1等于-1时；而当top2等于n时，即是栈2为空时，那什么时候栈满呢？
想想极端的情况，若栈2是空栈，栈1的top1等于n-1时，就是栈1满了。反之，当栈1为空栈时，top2等于0时，为栈2满。但更多的情况，其实就是我刚才说的，两个栈见面之时，也就是两个指针之间相差1时，即top1+1==top2为栈满。
两栈共享空间的结构的代码如下：

/* 两栈共享空间结构 */
typedef struct
{
    SElemType data[MAXSIZE];
    int top1;    /* 栈1栈顶指针 */
    int top2;    /* 栈2栈顶指针 */
}SqDoubleStack;

对于两栈共享空间的push方法，我们除了要插入元素值参数外，还需要有一个判断是栈1还是栈2的栈号参数stackNumber。插入元素的代码如下：

/* 插入元素e为新的栈顶元素 */
Status Push(SqDoubleStack *S, SElemType e, int stackNumber)
{
    if (S->top1 + 1 == S->top2)    /* 栈已满，不能再push新元素了 */
        return ERROR;
    if (stackNumber == 1)            /* 栈1有元素进栈 */
        S->data[++S->top1] = e; /* 若是栈1则先top1+1后给数组元素赋值。 */
    else if (stackNumber == 2)    /* 栈2有元素进栈 */
        S->data[--S->top2] = e; /* 若是栈2则先top2-1后给数组元素赋值。 */
    return OK;
}

因为在开始已经判断了是否有栈满的情况，所以后面的top1+1或top2-1是不担心溢出问题的。
对于两栈共享空间的pop方法，参数就只是判断栈1栈2的参数stackNumber，代码如下：

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(SqDoubleStack *S, SElemType *e, int stackNumber)
{
    if (stackNumber == 1)
    {
        if (S->top1 == -1)
            return ERROR; /* 说明栈1已经是空栈，溢出 */
        *e = S->data[S->top1--]; /* 将栈1的栈顶元素出栈 */
    }
    else if (stackNumber == 2)
    {
        if (S->top2 == MAXSIZE)
            return ERROR; /* 说明栈2已经是空栈，溢出 */
        *e = S->data[S->top2++]; /* 将栈2的栈顶元素出栈 */
    }
    return OK;
}

事实上，使用这样的数据结构，通常都是当两个栈的空间需求有相反关系时，也就是一个栈增长时另一个栈在缩短的情况。就像买卖股票一样，你买入时，一定是有一个你不知道的人在做卖出操作。有人赚钱，就一定是有人赔钱。这样使用两栈共享空间存储方法才有比较大的意义。否则两个栈都在不停地增长，那很快就会因栈满而溢出了。

4.6 栈的链式存储结构及实现

4.6.1 栈的链式存储结构

栈的链式存储结构，简称为链栈。
链栈的结构代码如下：

/* 链栈结构 */
typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStackPtr;

typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
}LinkStack;

4.6.2 栈的链式存储结构-进栈操作

对于链栈的进栈push操作，假设元素值为e的新结点是s，top为栈顶指针，示意图如图4-6-2所示代码如下。

/* 插入元素e为新的栈顶元素 */
Status Push(LinkStack *S,SElemType e)
{
    LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
    s->data=e;
    s->next=S->top;/* 把当前的栈顶元素赋值给新结点的直接后继，见图中① */
    S->top=s;         /* 将新的结点s赋值给栈顶指针，见图中② */
    S->count++;
    return OK;
}

4.6.3 栈的链式存储结构——出栈操作

至于链栈的出栈pop操作，也是很简单的三句操作。假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可，如图4-6-3所示。

/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(LinkStack *S,SElemType *e)
{
        LinkStackPtr p;
        if(StackEmpty(*S))
                return ERROR;
        *e=S->top->data;
        p=S->top;               /* 将栈顶结点赋值给p，见图中③ */
        S->top=S->top->next;    /* 使得栈顶指针下移一位，指向后一结点，见图中④ */
        free(p);                    /* 释放结点p */
        S->count--;
        return OK;
}

链栈的进栈push和出栈pop操作都很简单，时间复杂度均是O(1)。
对比一下顺序栈与链栈，它们在时间复杂度上是一样的，均为O(1)。对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。所以它们的区别是如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

4.7 栈的作用

栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于我们要解决的问题核心。反之，像数组等，因为要分散精力去考虑数组的下标增减等细节问题，反而掩盖了问题的本质。

4.8 栈的应用——递归

4.8.1-4.8.2递归定义

我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。
当然，写递归程序最怕的就是陷入永不结束的无穷递归中，所以，每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。

4.9 栈的应用——四则运算表达式求值

4.9.1 后缀(逆波兰)表示法定义

栈的现实应用也很多，我们再来重点讲一个比较常见的应用：数学表达式的求值。
一种不需要括号的后缀表达法，我们也把它称为逆波兰(Reverse Polish Notation，RPN)表示。
我们先来看看，对于“9+(3-1)×3+10÷2”，如果要用后缀表示法应该是：“9 3 1-3*+10 2/+”，这样的表达式称为后缀表达式，叫后缀的原因在于所有的符号都是在要运算数字的后面出现。

4.9.2 后缀表达式计算结果

后缀表达式：9 3 1-3*+10 2/+
规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。

4.9.3 中缀表达式转后缀表达式

我们把平时所用的标准四则运算表达式，即“9+(3-1)×3+10÷2”叫做中缀表达式。因为所有的运算符号都在两数字的中间。
中缀表达式“9+(3-1)×3+10÷2”转化为后缀表达式“9 3 1-3*+10 2/+”。
规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

4.10 队列的定义

队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出(First In First Out)的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

4.11 队列的抽象数据类型

ADT 队列(Queue)
Data
    同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
    InitQueue(*Q)：初始化操作，建立一个空队列Q。
    DestroyQueue(*Q)：若队列Q存在，则销毁它。
    ClearQueue(*Q)：将队列Q清空。
    QueueEmpty(Q)：若队列Q为空，返回true，否则返回false。
    GetHead(Q，*e)：若队列Q存在且非空，用e返回队列Q的队头元素。
    EnQueue(*Q，e)：若队列Q存在，插入新元素e到队列Q中并成为队尾元素。
    DeQueue(*Q，*e)：删除队列Q中队头元素，并用e返回其值。
    QueueLength(Q)：返回队列Q的元素个数
endADT

4.12 循环队列

4.12.1 队列顺序存储的不足

入队的时间复杂度为O(1)。
与栈不同的是，队列元素的出列是在队头，即下标为0的位置，那也就意味着，队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为空，此时时间复杂度为出队的时间复杂度为O(n)，效率太低。
如果队列前面的位置空的，后面的位置排满了，那么新进的元素可以排到前面，这就引进了循环队列的概念。
为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此队列是空队列。

4.12.2 循环队列定义

队列中头尾相接的顺序存储结构称为循环队列。
此时问题又出来了，空队列时，front等于rear，现在当队列满时，也是front等于rear，那么如何判断此时的队列究竟是空还是满呢？

1. 办法一是设置一个标志变量flag，当front==rear，且flag=0时为队列空，当front==rear，且flag=1时为队列满。
2. 办法二是当队列空时，条件就是front=rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。
   我们重点来讨论第二种方法，由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为QueueSize，那么队列满的条件是“(rear+1)%QueueSize==front”(取模“%”的目的就是为了整合rear与front大小为一个问题)。
   通用的计算队列长度公式为：(rear-front+QueueSize)%QueueSize。
   循环队列的顺序存储结构代码如下：

typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */
/* 循环队列的顺序存储结构 */
typedef struct
{
    QElemType data[MAXSIZE];
    int front;      /* 头指针 */
    int rear;       /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}SqQueue;

循环队列的初始化代码如下：

/* 初始化一个空队列Q */
Status InitQueue(SqQueue *Q)
{
    Q->front = 0;
    Q->rear = 0;
    return  OK;
}

循环队列求队列长度代码如下：

/* 返回Q的元素个数，也就是队列的当前长度 */
int QueueLength(SqQueue Q)
{
    return  (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

循环队列的入队列操作代码如下：

/* 若队列未满，则插入元素e为Q新的队尾元素 */
Status EnQueue(SqQueue *Q, QElemType e)
{
    if ((Q->rear + 1) % MAXSIZE == Q->front)    /* 队列满的判断 */
        return ERROR;
    Q->data[Q->rear] = e;               /* 将元素e赋值给队尾 */
    Q->rear = (Q->rear + 1) % MAXSIZE;/* rear指针向后移一位置， */
                                      /* 若到最后则转到数组头部 */
    return  OK;
}

循环队列的出队列操作代码如下：

/* 若队列不空，则删除Q中队头元素，用e返回其值 */
Status DeQueue(SqQueue *Q, QElemType *e)
{
    if (Q->front == Q->rear)            /* 队列空的判断 */
        return ERROR;
    *e = Q->data[Q->front];                /* 将队头元素赋值给e */
    Q->front = (Q->front + 1) % MAXSIZE;    /* front指针向后移一位置 */
                                    /* 若到最后则转到数组头部 */
    return  OK;
}

4.13 队列的链式存储结构及实现

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。
为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点，如图4-13-1所示。

空队列时，front和rear都指向头结点，如图4-13-2所示。

链队列的结构为：

typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */

typedef struct QNode    /* 结点结构 */
{
    QElemType data;
    struct QNode *next;
}QNode, *QueuePtr;

typedef struct            /* 队列的链表结构 */
{
    QueuePtr front, rear; /* 队头、队尾指针 */
}LinkQueue;

4.13.1 队列的链式存储结构——入队操作

入队操作时，其实就是在链表尾部插入结点，如图4-13-3所示。

入队代码如下：

/* 插入元素e为Q的新的队尾元素 */
Status EnQueue(LinkQueue *Q, QElemType e)
{
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if (!s) /* 存储分配失败 */
        exit(OVERFLOW);
    s->data = e;
    s->next = NULL;
    Q->rear->next = s;    /* 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中① */
    Q->rear = s;        /* 把当前的s设置为队尾结点，rear指向s，见图中② */
    return OK;
}

4.13.2 队列的链式存储结构——出队操作

出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点，如图4-13-4所示。

出队代码如下：

/* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
Status DeQueue(LinkQueue *Q, QElemType *e)
{
    QueuePtr p;
    if (Q->front == Q->rear)
        return ERROR;
    p = Q->front->next;        /* 将欲删除的队头结点暂存给p，见图中① */
    *e = p->data;                /* 将欲删除的队头结点的值赋值给e */
    Q->front->next = p->next;/* 将原队头结点的后继p->next赋值给头结点后继，见图中② */
    if (Q->rear == p)/* 空队列的时候 */ /* 若队头就是队尾，则删除后将rear指向头结点，见图中③ */
        Q->rear = Q->front;
    free(p);
    return OK;
}

对于循环队列与链队列的比较，可以从两方面来考虑，从时间上，其实它们的基本操作都是常数时间，即都为O（1）的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。
总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。

4.14 总结回顾

这一章讲的是栈和队列，它们都是特殊的线性表，只不过对插入和删除操作做了限制。
栈(stack)是限定仅在表尾进行插入和删除操作的线性表。
队列(queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
它们均可以用线性表的顺序存储结构来实现，但都存在着顺序存储的一些弊端。因此它们各自有各自的技巧来解决这个问题。
对于栈来说，如果是两个相同数据类型的栈，则可以用数组的两端作栈底的方法来让两个栈共享数据，这就可以最大化地利用数组的空间。
对于队列来说，为了避免数组插入和删除时需要移动数据，于是就引入了循环队列，使得队头和队尾可以在数组中循环变化。解决了移动数据的时间损耗，使得本来插入和删除是O(n)的时间复杂度变成了O(1)。
它们也都可以通过链式存储结构来实现，实现原则上与线性表基本相同如图4-14-1所示。