栈与队列

栈

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

栈的顺序存储结构

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

进栈操作push：

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

出栈操作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)$。

两栈共享空间

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

数组有两个端点，两个栈有两个栈底，一个栈的栈底为数组的始端，即下标为0处，另一个栈为栈的末端，即下标为数组长度n-1处。
栈1 为空时，top1等于-1；栈2 为空时，top2等于n。
当top1 + 1 == top2 时为栈满。

push

/* 插入元素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;
}

pop

/* 若栈不为空，则删除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)    /* 说明栈2已经是空栈，溢出 */
            return ERROR;
        *e = S->data[S->top2++];   /* 将栈1的栈顶元素出栈 */
    }
    return OK;
}

两栈共享空间适用于相同数据类型，如果是不相同数据类型的栈，这种办法不但不能更好地处理问题，反而会使问题变得更复杂。

栈的链式存储结构

栈的链式存储结构，简称为链栈。
通常对于链栈来说，是不需要头结点的。
空栈，链表原定义是头指针指向空，链栈就是top=NULL。

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

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

push入栈

/* 插入元素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;
}

pop出栈

/* 若栈不空，则删除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);
    S->count--;
    return OK;
}

对比顺序栈和链栈

1. push和pop时间复杂度上均为$O(1)$。
2. 顺序栈需要确定一个长度，可能存在内存空间的浪费。
3. 链栈要求每个元素都有指针域，增加了内存开销，但对于长度无限制。

所以它们的区别和线性表中讨论的一样，如果栈的使用过程中元素变化不可预料，那么最好使用链栈，反之，如果它的变化在可控范围内，使用顺序栈会更好一些。

递归

斐波那契数列

1，1，2，3，5，8，13，21，34，55，89，144

int Fbi(int i)  /* 斐波那契的递归函数 */{
    if( i < 2 )
        return i == 0 ? 0 : 1;
    return Fbi(i - 1) + Fbi(i - 2);
}
int main(){
    for(i = 0;i < 40;i++)
        printf("%d ", Fbi(i));
    return 0;
}

递归定义

把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称作为递归。

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

后缀表达法（逆波兰）

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

中缀表达式转后缀表达式

平时用的标准四则运算表达式，叫做中缀表达式。
规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号，则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式。

队列

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

循环队列

解决假溢出的办法是后边满了，就再从头开始，也就是头尾相接的循环，把队列的这种头尾相接的顺序存储结构称为循环队列。

如果队列为空时，front（指向队头元素）等于rear（指向队尾元素的下一个位置）。
如果队列满时，保留一个元素空间，如下图：

如果队列的最大尺寸为QueueSize，那么队列满的条件是$(rear+1) % QueueSize == front$。
如上边的例子，QueueSize=5，左图front=0，rear=4，(4+1)%5 = 0，所以此时队列满。右图，front=2，rear=1，(1+1)%5=2，所以此时队列满。

当rear>front时，队列长度为rear-front。当rear<front时，队列长度一段为QueueSize-front，另一段0+rear，加一起为rear-front+QueueSize。
因此计算队列长度的公式为：$$(rear-front+QueueSize) % QueueSize$$

循环队列的顺序存储结构

typedef int QElemType;
typedef struct {
    QElemType data[MAXSIZE];
    int front; /* 头指针 */
    int rear;  /* 尾指针，如果队列不为空，指向队列尾元素的下一个位置 */
}

循环队列初始化代码

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

队列的链式存储结构

队头指针指向链队列的头结点，队尾指针指向终端结点。

空队列时，front和rear都指向头结点。

入队：在链表尾部插入结点

出队：①头结点的后继结点出队，②将头结点的后继改为它后面的结点，③若链表除头结点外只剩下一个元素，则需将rear指向头结点。