一、队列的应用 只要满足先来先服务特性的应用均可采用队列作为其数据组织方式或中间数据结构
调度或缓冲 消息缓冲器 邮件缓冲器 计算机硬设备之间的通信也需要队列作为数据缓冲 操作系统的资源管理 宽度优先搜索 广度优先搜索：搜索该步的所有可能状态，再进一步考虑后面的各种情况；（队列应用）
树的层次遍历 深度优先搜索：沿某一状态走下去，不行再回头。（栈应用）
树的先序、中序、后续遍历 二、农夫过河问题 问题抽象：
“人狼羊菜”乘船过河 只有人能撑船，船只有两个位置（包括人） 狼羊、羊菜不能在没有人时共处 数据抽象：
对每个角色的位置进行描述，农夫、狼、羊和菜，四个目标依次各用一位，目标在起始岸位置：0，目标岸：1。如 0110 表示农夫、白菜在起始岸，而狼、羊在目标岸（此状态为不安全状态） 用整数 status 表示上述四位二进制描述的状态，如整数 0x08 表示的状态 1000，整数 0x0F 表示的状态 1111 如何从上述状态中得到每个角色所在位置？ bool farmer(int status){ return ((status & 0x08) != 0); } bool wolf(int status){ return ((status & 0x04) !...
栈的物理实现有 顺序队列 和 链式队列
一、顺序队列 用向量存储队列元素，用两个变量分别指向队列的前端(front)和尾端(rear)
关键是如何防止假溢出 队列溢出
上溢 下溢 假溢出：当 rear = mSize-1 时，再作插入运算就会产生溢出，如果这时队列的前端还有许多空位置，这种现象称为假溢出 循环队列
为了解决假溢出的问题，需要采用循环队列的方式： % mSize 另外一个问题就是如何区分空队列还是满队列？空一个队列空间，空队列状态时，令 front = rear，若 (rear + 1) % mSize == front，我们认为此时队列已满，但实际上 rear 指向的空间并没有被利用 循环队列类定义
template <class T> class arrQueue: public Queue<T> { private: int mSize; // 存放队列的数组的大小 int front; // 表示队头所在位置的下标 int rear; // 表示待入队元素所在位置的下标 T *qu; // 存放类型为T的队列元素的数组 public: // 队列的运算集 arrQueue(int size) { // 创建队列的实例 mSize = size + 1; // 浪费一个存储空间，以区别队列空和队列满 qu = new T[mSize]; front = rear = 0; } ~arrQueue() { // 消除该实例，并释放其空间 delete[] qu; } } // 入队操作 template<class T> bool arrQueue<T> :: enQueue(const T item) { // item入队，插入队尾 if (((rear + 1 ) % mSize) == front) { cout << "队列已满，溢出" << endl; return false; } qu[rear] = item; rear = (rear + 1) % mSize; // 循环后继 return true; } // 出队操作 bool arrQueue<T> :: deQueue(T& item) { // 返回队头元素并从队列中删除 if ( front == rear) { cout << "队列为空" << endl; return false; } item = qu[front]; front = (front + 1) % mSize; // 这里并没有真的删除队列空间的元素，而是把头指针循环后移 return true; } 二、链式队列 用单链表方式存储，队列中每个元素对于链表中的一个结点...
一、队列 队列特点
访问受限的线性表 先进先出 插入在一端进行，删除在另一端进行 主要元素
队头 队尾 主要操作
入队列 出队列 取队首元素 判断队列是否为空 二、队列的抽象数据类型 template <class T> class Queue { // 队列的运算集 public: // 变为空队列 void clear(); // 将item插入队尾，成功则返回真，否则返回假 bool enQueue(const T item); // 返回队头元素并将其从队列中删除，成功则返回真 bool deQueue(T & item); // 返回队头元素，但不删除，成功则返回真 bool getFront(T & item); // 返回真，若队列已空 bool isEmpty(); // 返回真，若队列已满 bool isFull(); }; 三、队列的实现方式 队列的物理实现又分为顺序队列和链式队列
栈的特点是后进先出，所以常用来处理具有递归结构的数据
深度优先搜索 表达式求值 子程序 / 函数调用的管理 消除递归 表达式的递归定义
基本符号集：${0，1，…，9，+，-，*，/，（，）}$ 语法成分集：{<表达式> , <项> , <因子> , <常数>, <数字> } 中缀表达式：$23\ +\ (34\ *\ 45)\ /\ (5\ +\ 6\ +\ 7)$ 后缀表达式：$23\ 34\ 45\ *\ 5\ 6\ +\ 7\ +\ /\ +$
中缀表达式
运算符在中间 需要括号改变优先级 例如：$4\ *\ x\ *\ (2\ *\ x\ +\ a)\ –\ c$
后缀表达式...
栈的物理实现有 顺序栈 和 链式栈
一、顺序栈（Array-based Stack） 使用向量实现，本质上是顺序表的简化版 栈有固定大小 关键是确定哪一端作为栈顶 注意上溢、下溢问题 类定义：
template <class T> class arrStack : public Stack <T> { private: // 栈的顺序存储 int mSize; // 栈中最多可存放的元素个数 int top; // 栈顶位置，应小于mSize T *st; // 存放栈元素的数组 public: // 栈的运算的顺序实现 arrStack(int size) { // 创建一个给定长度的顺序栈实例 mSize = size; top = -1; st = new T[mSize]; } arrStack() { // 创建一个顺序栈的实例 top = -1; } ~arrStack() { delete [] st; } void clear() { top = -1; } // 清空栈 }; bool arrStack<T>::push(const T item) { // 入栈 if (top == mSize-1) { // 栈已满 cout << "栈满溢出" << endl; return false; } else { // 新元素入栈并修改栈顶指针 st[++top] = item; return true; } } bool arrStack<T>::pop(T& item) { // 出栈 if (top == -1) { // 栈为空 cout << "栈为空，不能执行出栈操作"<< endl; return false; } else { item = st[top--]; // 返回栈顶，并缩减1 return true; } } 二、链式栈（Linked Stack） 用单链表方式存储，其中指针的方向是从栈顶向下链接 理论上没有大小限制 类定义：...