栈与队列

栈

栈是一种特殊的线性表，只能在一端进行操作

往栈中添加元素的操作，一般叫做 push，入栈

从栈中移除元素的操作，一般叫做 pop，出栈（只能移除栈顶元素，也叫做：弹出栈顶元素）

后进先出的原则，Last In First Out，LIFO

栈接口设计

int size(); // 元素的数量 
boolean isEmpty(); // 是否为空 
void push(E element); // 入栈 
E pop(); // 出栈 E 
top(); // 获取栈顶元素 
void clear(); // 清空

栈的应用：

• 浏览器
• 剪切板

栈练习：

20. 有效的括号

856. 括号的分数

150. 逆波兰表达式求值

224. 基本计算器

队列

队列是一种特殊的线性表，只能在头尾两端进行操作

队尾（rear）：只能从队尾添加元素，一般叫做 enQueue，入队

队头（front）：只能从队头移除元素，一般叫做 deQueue，出队

先进先出的原则，First In First Out，FIFO

队列的实现优先使用双向链表，因为队列主要是往头尾操作元素

队列接口设计

int size(); // 元素的数量 
boolean isEmpty(); // 是否为空 
void clear(); // 清空 
void enQueue(E element); // 入队 
E deQueue(); // 出队 
E front(); // 获取队列的头元素

双端队列

双端队列是能在头尾两端添加、删除的队列

相对普通队列变更

void enQueueRear(E element); // 从队尾入队
E deQueueFront(); // 从队头出队 
void enQueueFront(E element); // 从队头入队 
E deQueueRear(); // 从队尾出队 
E front(); // 获取队列的头元素 
E rear(); // 获取队列的尾元素

循环队列

使用动态数组实现，并且各项接口也可以优化到 O(1) 的时间复杂度 。这个用数组实现并且优化之后的队列也叫做：循环队列

循环双端队列

可以进行两端添加、删除操作的循环队列

队列练习

232. 用栈实现队列

225. 用队列实现栈