数据结构04：栈与队列

1. 栈的定义

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

2. 栈的抽象数据类型

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

3. 栈的顺序存储结构及其实现

栈的结构定义：

typedef int SElemType;
typedef struct {
    SElemType data[MAXSIZE];
    int top; /* 用于栈顶指针 */
}

若现在有一个栈，StackSize是5，则站普通情况、空栈和栈满的情况如图：

3.1 进栈操作

/* 插入元素e为新的栈顶元素 */
Status Push(SqStack *S, SElemType e) {
    if(S->top == MAX_SIZE - 1) /* 满栈 */
        return ERROR;
    S->top++;
    S->data[S->top] = e;
    return OK;
}

3.2 出栈操作

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

4. 两栈共享空间

top1和top2是栈1和栈2的栈顶指针，top1等于-1时，栈1为空；top2等于n时，栈2为空；当top1 + 1 == top2时，栈满。

两栈共享控件的结构代码如下：

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

/* 插入元素e为新的栈顶元素 */
Status Push(SqDoubleStack *S, SElemType e, int stackNumber) {
    if(S->top1 + 1 == S->top2)
        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;
}

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

5. 栈的链式存储结构及实现

5.1 栈的链式存储结构

链栈的结构代码如下：

typedef struct StackNode {
    SElemType data;
    struct StackNode *next;
}StackNode, *LinkStackPtr;

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

5.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->count++;
    return OK;
}

5.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;
    S->top = S->top->next;
    free(p);
    S->count--;
    return OK;
}

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

6. 栈的应用-递归

6.1 斐波那切数列实现

int Fbi(int i) {
    if(i < 2)
        return i == 0 ? 0 : 1;
    return Fbi(i - 1) + Fbi(i - 2);
}

6.2 递归定义

把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。
每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引入自身而是返回值退出。

7. 栈的应用-四则运算表达式求值

7.1 后缀（逆波兰）表示法定义

不需要括号的后缀表达法，我们把它成为逆波兰表示。
9+(3−1)∗3+10/2$9+(3-1)\ast 3+10/2$
使用逆波兰表达式：
9 3 1 - 3 * + 10 2 / +

7.2 后缀表达式计算结果

9 3 1 - 3 * + 10 2 / +

7.3 中缀表达式转后缀表达式

规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素一次出栈并输出，并将当前符号进栈，一直到最终数组后缀表达式为止。
9 + (3 - 1) * 3 + 10 / 2

8. 队列的定义

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

9. 队列的抽象数据类型

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

10. 循环队列

10.1 队列顺序存储的不足

当使用顺序存储时，在做出队操作时，需要将所有数据向前移动一位，时间复杂度为O(n)，效率很低。

10.2 循环队列定义

我们把队列的这种头尾相接的顺序存储结构称为循环队列。

若队列的最大尺寸为QueueSize，那么队列满的条件是(rear + 1) % QueueSize == front

11. 队列的链式存储结构及其实现

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为连队列。

空队列时：

链队列的结构为：

typedef int QElemType;

typedef struct QNode {
    QElemType data;
    struct QNode *next;
}QNode, *QueuePtr;

typedef struct {
    QueuePtr front, rear;
}LinkQueue;

11.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;
    Q->rear->next = s;
    Q->rear = s;
    return OK;
}

11.2 出队操作

/* 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR */
Status DeQueue(LinkQueue *Q, QElemType *e) {
    QueuePtr p;
    if(Q->front == Q->rear)
        return ERROR;
    p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if(Q->rear == p)
        Q->rear = Q->front;
    free(p);
    return OK;
}

12. 总结