栈与队列
2023-01-31 本文已影响0人
iOS小洁
栈
栈是一种特殊的线性表，只能在一端进行操作
往栈中添加元素的操作，一般叫做 push，入栈
从栈中移除元素的操作，一般叫做 pop，出栈（只能移除栈顶元素，也叫做：弹出栈顶元素）
后进先出的原则，Last In First Out，LIFO
栈接口设计
int size(); // 元素的数量
boolean isEmpty(); // 是否为空
void push(E element); // 入栈
E pop(); // 出栈 E
top(); // 获取栈顶元素
void clear(); // 清空
栈的应用：
- 浏览器
- 剪切板
栈练习：
队列
队列是一种特殊的线性表，只能在头尾两端进行操作
队尾（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) 的时间复杂度 。这个用数组实现并且优化之后的队列也叫做：循环队列
循环双端队列
可以进行两端添加、删除操作的循环队列
