数据结构：栈(stack)与队列(queue)

1. 栈（stack）

线性表的特例

1.1 定义

栈（stack）是限定仅在表尾进行插入和删除操作的线性表

Last in First Out

栈顶（top）：允许插入和删除的一端
栈底（bottom）：不允许插入和删除的一端
LIFO结构：栈又称为后进先出（Last In First Out）的线性表
栈的插入操作，叫进栈，也称压栈、入栈
栈的删除操作，叫出栈，也称弹栈

1.2 栈的抽象数据类型

ADT
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

1.3 顺序存储结构

####　1.3.1 栈的顺序存储结构

栈的顺序存储结构是线性表顺序存储的简单结构：顺序栈
使用数组来表达时，栈底在下标为0的位置；
- StackSize 为数组长度，标识栈的长度
- top 为栈顶游标，小于 StackSize
- 空栈时 top=-1

1.3.2 栈的顺序存储结构 - 进栈操作

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

1.3.3 栈的顺序存储结构 - 出栈操作

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

1.3.4 两栈共享空间

用同一个数据构建两个栈，共享空间
一个栈用下标为 0 做栈底，另一个栈用下标为 MAXSIZE - 1 作为栈底
两个栈的 top 相遇则为栈满

1.4 链式存储结构

栈的链式存储：链栈
栈顶放在链的头部（只有栈顶进行数据操作）
在内存足够的情况下不存在栈满的情况
空栈即链的头部指针指向空

1.4.1 栈的链式存储结构

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

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

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

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

1.4.3 栈的链式存储结构 - 出栈操作

c
/* 若栈不空，则删除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;
}

1.5 栈的作用

1.5.1 递归

1.5.1.1 斐波那契数列（Fibonacci）

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。公式如下：

F(n) = \begin{cases} 0, 当 n=0 \\ 1, 当 n=1 \\ F(n-1) + F(n-2), 当 n>1 \end{cases}

1.5.1.2 递归的定义

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

1.5.2 四则运算表达式求值

1.5.2.1 中缀表达式转后缀表达式

我们常见的标准四则运算表达式，就是中缀表达式；如： 9+(3-1)*3+10/2;
后缀表达式是后缀计算的关键;
规则：
- 从左到右遍历中缀表达式的数字和符号
- 遇到数字就输出，成为后缀表达式到的一部分
- 遇到符号，先和栈顶符号对比优先级
  - 如果是右括号或者优先级低于栈顶符号，则栈内元素依次出栈并输出，并吧当前符号进栈
  - 如果是左括号或者优先级高于栈顶符号，这继续入栈

*举例：9+(3-1)3+10/2

-> 输出：9 3 1 - 3 * + 10 2 / +

rpn

1.5.2.2 后缀（逆波兰）表示法定义（Reverse Polish Notation,RPN）

使用后缀表达式计算公式结果

规则：
- 从左到右遍历数字和符号
- 遇到数字进栈
- 遇到符号则将处于栈顶的两个数字出栈，计算结果，结果进栈

举例：9 3 1 - 3 * + 10 2 / +

rpn result

2. 队列（queue）

队列是只准许在一端进行插入操作，而在另一端进行删除操作的线性表

First In First Out

允许插入的一端称为队尾
允许删除的一端称为队头

2.1 队列的抽象数据类型

text
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

2.2 循环队列

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

2.2.1 队列顺序存储的不足

2.2.1.1 第一种存储实现

使用数组来做队列存储，用下标 0 一端做队头，查入数据是直接往数组添加数据，所以时间复杂度是 O(1)，队头删除数据时，所有数据往前移动，时间复杂度为O(n);

2.2.1.2 第二种存储实现

使用数组来做队列存储，front 指针指向队头下标， rear 指针指向队尾的下一个下标，当 front == rear 时为空队列，添加一个元素，rear 加 1，删除一个元素 front 加 1。这样删除和插入时间复杂度都为O(n)。

这种实现存在一个假溢出问题，当数组数据不满，但是队列不停插入和删除，导致 rear 超过了数组的 size ( front ！= 0)。

2.2.2 循环队列

2.2.2.1 定义

解决假溢出的问题就是，当后面满了重头开始，我们把队列的这种头尾相接的顺序存储结构称为循环队列。

循环队列出现一个问题就是 front == rear 是不知道是队满还是队空，解决这个问题有以下方法：
- 设置一个 flag，当 front == rear 且 flag == 0 时，为队空，当 front == rear 且 flag == 1 时，为队满
- 队满预留一个单元，即 front == rear 为队空， (rear+1)%QueueSize == front 为队满
通用长度计算公式为 （rear - front + QueueSize ) % QueueSize

2.3 队列的链式存储结构

其实就是线性表的单链表，只不过只准许尾进头出。

目录