栈与队列

栈：

一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。不含任何元素的栈称为空栈，栈又称为后进先出（LIFO）的线性表。

栈的分类：

• 顺序表
  顺序栈与顺序表数据成员不同，不同之处：顺序栈的入栈和出栈操作只允许对当前栈顶进行操作
  顺序栈所有的操作时间复杂度为O（1）
• 链式栈（双向链表）
  
  栈的应用
  
  1. 括号匹配问题
  2. 逆波兰表达式（后缀表达式）
  3. 迷宫

队列：

只允许在一端进行插入数据操作，另一端进行删除数据操作的特殊线性表

• 进行插入操作的一端称为队尾（入队列）
• 进行删除操作的一端称为队头（出队列）
• 队列具有先进先出（FIFO）的特性

队列的分类：

• 顺序队列

  1. 操作时如果出队列比较多，要搬移大量元素（队头不动，出队列时对头后的所有元素向前移动）
  2. 可能出现假溢出问题（队头移动，出队列时对头向后移动一个位置）

• 循环队列
  能够解决顺序队列进行入队列和出队列时时间性能不是很好的问题，但又面临数组可能溢出的问题

   面试题：循环队列如何判断队列空和满呢？
   1.少用一个存储单元
   2.设置一个标记位
  

• 链式队列
  特殊的单链表，只在单链表上进行头删尾插的操作

• 优先级队列
  优先级队列的出队列操作不是直接将对头元素出队列，而是把队列中优先级最高的元素出队列

队列的应用
1. 生产者消费者模型
2. 消息队列
3. 排队现象
4. 网络数据传输