栈与队列

栈与队列

一、栈

栈（stack）是限定仅在表尾（栈顶）进行插入和删除操作的线性表。
后进先出(LIFO)：

进栈、出栈

栈的抽象数据类型

栈的顺序储存结构（数组）

栈的结构定义

两栈共享空间

关键思路：它们是数组两端，向中间靠拢。top1和top2分别是栈1和栈2的栈顶指针。
栈1为空，top1 = -1,;栈2为空，top2 = n;
判断栈满，top1+1 == top2

两栈共享空间结构

栈的链式储存：链栈

栈顶指针在头部，单链表中的比较常用的头结点失去意义，通常链栈无需头节点。

//单链表基础结构
template<class DataType>
struct Node{
  DataType data;
  Node<DataType> *next;
};
//使用时需多声明一个栈顶指针top
Node<DataType> *top = new Node<DataType>;

image.png

栈的应用——递归

斐波那锲数列：前面相邻两项之和，构成后一项。

Fibonacci数学定义

执行过程

递归与栈

递归：函数直接或间接调用自身（反复调用，建立大量函数副本；但结构清晰、简洁）。

迭代：无需反复调用和占用额外内存。

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

后缀（逆波兰）表示法：

将中缀表达式转化为后缀表达式（栈用来进出运算的符号）；
将后缀表达式进行运算得出结果（栈用来进出运算的数字）

二、队列（queue）

队列：先进先出（FIFO）

入队（插入）：新元素始终添加在队列的末尾；
出队（删除）：发生在队头，只能移除第一个元素；

应用非常频繁：键盘输入“god”,若使用栈，输出“dog”;使用队列，输出“god”

为避免队头、队尾处理麻烦：front指针指向队头元素，rear指针指向超尾元素。

左图为队列空，右图为元素入队后

存在问题：“假溢出”现场，队尾满了，但队头还是空闲。

尾指针溢出，但队列仍未满

循环队列：头尾相接的顺序储存结构。

循环队列及指针重合问题

存在问题：当front与rear指针重合时，队列存在空或满两种情况。
解决方法：

设标志变量flag，当front==rear,flag=0,队列为空；当front==rear,flag=1,队列满，

队列空时，front==rear；队列满时，保留一个元素空间。

★:- 队列满的条件是(rear+1)%QueueSize == front；
★:- 通用计算队列长度公式:(rear - front + QueueSize)%QueueSize
☆:-采用%QueueSize防止长度溢出——最多一整圈。