栈和队列是常用的两种数据结构，逻辑结构与线性表相同。
特点：栈“后进先出”，队列“先进先出''。
（一）栈的定义
栈：称为先进后出（FILO）或后进先出（LIFO）线性表。是只能通过访问一端来实现数据存储和检索的线性数据结构。
修改原则：“先进后出”。
栈顶（top）：在栈中进行插入和删除操作的一端
栈底（bottom）：另一端。
空栈：不含数据元素的栈。
（二）栈的基本运算
①初始化栈initStack（S）：创建一个空栈S。
②判栈空isEmpty（S）：当栈S为空栈时，返回“真”值，否则返回“假”值。
③入栈push（S，x）：将元素x加入栈顶，并更新栈顶指针。
④出栈pop（S）：将栈顶元素从栈中删除，并更新栈顶指针。若需得到栈顶元素值，可将pop（S）定义为一个函数，它返回栈顶元素的值.
⑤读栈顶元素top（S）：返回栈顶元素的值，但不修改栈顶指针。
（三）栈的存储结构
存储结构 | 说明 | |
1 | 栈的顺序存储 | 用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针top指示栈顶元素位置。 顺序栈：采用顺序存储结构的栈。 顺序存储时，栈空间容量有限，需要预先定义或申请栈的存储空间。 当一个元素入栈时，需要判断是否栈满（栈空间中没有空闲单元），若栈满，则元素入栈会发生上溢现象。 |
2 | 栈的链式存储 | 顺序存储的栈可能存在上溢，所以用链表存储栈中的元素。 链栈：用链表作为存储结构的栈。 栈中元素的插入和删除仅在栈顶一端进行，不必设置头结点，链表头指针就是栈顶指针。 |
（四）栈的应用
（1）典型应用
- 表达式求值
- 括号匹配
（2）将表达式转换为后缀形式
计算后缀表达式时，从左至右扫描后缀表达式：若遇到运算对象，则压入栈中；遇到运算符，则从栈中弹出相应运算对象进行计算，并将运算结果压入栈中。重复以上过程，直到后缀表达式结束。
举例：表达式46+5*(120-37)的后缀表达式形式为46 5 120 37-*+
计算过程：
①依次将46、5、120、37压入栈中。
②遇到-，弹出37、120，计算120-37，得83，将其压入栈中。
③遇到*，弹出83、5，计算5*83，得415，将其压入栈中。
④遇到+，弹出415、46，计算46+415，得461，将其压入栈中。
⑤表达式结束，则计算过程完成。
（五）队列定义
队列：是一种先进先出（FIFO）的线性表，只允许在表的一端插入元素，而另一端删除元素。
队尾（rear）：允许插入元素的一端。
队头（front）：允许删除元素的一端。
（六）队列基本运算
①初始化队列initQueue（Q）:创建一个空队列Q。
②判队空isEmpty（Q）：当队列为空时返回“真"值，否则返回“假"值。
③入队enQueue（Q，x）：将元素x加入到队列Q的队尾，并更新队尾指针。
④出队deQueue（Q）：将队头元素从队列Q中删除，并更新队头指针。
⑤读队头元素frontQueue（Q）：返回队头元素的值，但不更新队头指针。
（七）队列存储结构
存储结构 | 说明 | |
1 | 队列的顺序存储 | 又称顺序队列。 利用一组地址连续的存储单元存放队列中的元素。 队中元素的插入和删除限定在表的两端进行，设置队头和队尾指针，分别指示出当前队首元素和队尾元素。 |
2 | 队列的链式存储 | 也称链队列。 给链队列添加一个头结点，并令头指针指向头结点，队列为空的判定条件是头指针和尾指针的值相同，且均指向头结点。 |
（八）队列应用
队列常用于处理需要排队的场合，如处理打印任务的打印队列、离散事件的计算机模拟等。