数据结构之栈与队列

数据结构与算法

---

一、栈的概念

栈（stack）是限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（LastIn First Out）的线性表，简称LIFO结构。

栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。

栈的插入操作，叫作进栈，也称压栈、入栈；栈的删除操作，叫作出栈，也有的叫作弹栈。

栈的抽象数据类型

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

二、栈的顺序存储结构及实现

通常定义一个top变量来指示栈顶元素在数组中的位置，这个top就如同物理中的游标卡尺的游标，可以来回移动，意味着栈顶的top可以变大变小，无论如何游标不能超出尺的长度。若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判定条件定为top等于-1。

栈的结构定义

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

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

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

时间复杂度O(1)。

2.2 栈的顺序存储结构——出栈

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

时间复杂度O(1)。

2.3 两栈共享空间

栈的顺序存储只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题，但是有一个明显的缺陷：必须事先定义存储空间的大小。万一不够用了，就需要编程手段来扩展数组的容量，非常麻烦。
解决方案：两栈共享空间

基本思路：栈存储从两端向中间靠拢，top1和top2是栈1和栈2的栈顶指针，只要top1和top2相差大于1，则说明栈不满。若指针之间相差1时，即top1+1==top2为栈满。若栈2是空栈，栈1的top1等于n-1时，就是栈1满了。反之，当栈1为空栈时，top2等于0时，为栈2满。

两栈共享空间的结构的代码：

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

两栈共享空间的push方法

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

两栈共享空间的pop方法

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

三、栈的链式存储结构及实现

3.1 栈的链式存储结构

栈的链式存储结构，简称为链栈。
链栈中，栈顶放在单链表的头部。链栈不需要头结点。
对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机崩溃的情况，而不是这个链栈是否溢出的问题。链栈的空就是top=NULL的时候。

链栈的结构代码：

typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
} StackNode, *LinkStackPtr;
typedef struct LinkStack
{
    LinkStackPtr top;
    int count;
} LinkStack;

3.2 栈的链式存储结构——进栈操作

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

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

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

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

链栈的进栈push和出栈pop操作都很简单，没有任何循环操作，时间复杂度均为O(1)。

对比顺序栈与链栈:
时间复杂度: 均为O(1)
空间性能:
顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便;
链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制。

如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议使用顺序栈会更好一些。

四、栈的应用

4.1 递归：斐波那契数列（Fibonacci）

$$f(n) = \begin{cases} 0 & \text{当n = 0} \\ 1 & \text{当n = 1} \\ f(n-1) + f(n-2) & \text{当n > 1} \end{cases}$$
用循环实现：

int main()
{
    int i;
    int a[40];
    a[0] = 0;
    a[1] = 1;
    printf("%d ", a[0]);
    printf("%d ", a[1]);
    for (i = 2; i < 40; i++)
    {
        a[i] = a[i - 1] + a[i - 2];
        printf("%d ", a[i]);
    }
    return 0;
}

用递归实现：

/* 斐波那契的递归函数 */
int Fbi(int i)
{
    if (i < 2)
        return i == 0 ? 0 : 1;
    /* 这里Fbi就是函数自己，它在调用自己 */
    return Fbi(i - 1) + Fbi(i - 2);    
}
int main()
{
    int i;
    for (i = 0; i < 40; i++)
        printf("%d ", Fbi(i));
    return  0;
}

递归图示：

递归定义
迭代和递归的区别：迭代使用的是循环结构，递归使用的是选择结构。递归能使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存。迭代则不需要反复调用函数和占用额外的内存。
递归与栈的联系
在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。

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

后缀表达法：一种不用括号的表达式，由波兰逻辑学家Jan·ukasiewicz发明，也称为逆波兰（Reverse Polish Notation，RPN）。
对于“9+(3-1)×3+10÷2”，使用后缀表达式表示为：“9 3 1-3*+102/+”。
规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。
中缀表达式转后缀表达式
中缀表达式“9+(3-1)×3+10÷2”转化为后缀表达式“9 3 1-3*+10 2/+”。
规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

五、队列

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。假设队列是q=(a1,a2,......,an)，那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，列在最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后，如图6所示。

5.1 队列的抽象数据类型

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

5.2 循环队列

假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为O(1)，如图7所示。

与栈不同的是，队列元素的出列是在队头，即下标为0的位置，那也就意味着，队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为空，此时时间复杂度为O(n)，如图8所示。

这样的结构对于出列来说非常不便利，为什么队列中的每个元素都要移动呢？所以引进了循环队列。
循环队列定义：队列中头尾相接的顺序存储结构称为循环队列。
引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列或者满队列。满队列情况如下：

那么如何判断此时的队列究竟是空还是满呢？
办法一是设置一个标志变量flag，当front==rear，且flag=0时为队列空，当front==rear，且flag=1时为队列满。
办法二是当队列空时，条件就是front=rear，当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。例如图10所示，我们就认为此队列已经满了，也就是说，我们不允许图9的右图情况出现。

第二种方法中队列满的条件为：(rear+1)%QueueSize==front
通用的计算队列长度公式为：(rear-front+QueueSize)%QueueSize
循环队列的顺序存储结构代码如下：

/* QElemType类型根据实际情况而定，这里假设为int */
typedef int QElemType;    
/* 循环队列的顺序存储结构 */
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;
    /* 将元素e赋值给队尾 */
    Q->data[Q->rear] = e;                       
    /* rear指针向后移一位置， */
    Q->rear = (Q->rear + 1) % MAXSIZE;          
    /* 若到最后则转到数组头部 */
    return OK;
}

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

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

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

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

空队列时，front和rear都指向头结点。
链队列的结构为：

/* QElemType类型根据实际情况而定，这里假设为int */
typedef int QElemType;       
/* 结点结构 */
typedef struct QNode         
{
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;
/* 队列的链表结构 */
typedef struct               
{
    /* 队头、队尾指针 */
    QueuePtr front, rear;    
} LinkQueue;

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

入队操作时，其实就是在链表尾部插入结点:

其代码如下：

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

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

出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点:

代码如下：

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

5.3.3 循环队列与链队列的比较

选项	循环队列	链队列
时间	基本操作O(1)，循环队列是事先申请好空间，使用期间不释放	基本操作O(1)，链队列每次申请和释放结点也会存在一些时间开销
空间	必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题	需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。

总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果无法预估队列的长度时，则用链队列。