栈与队列
栈
栈(Stack)是先进后出的数据结构,我们可以将其想象为一个杯子,入栈就是不断往杯子中放入大小合适的小球,出栈时需要将小球从上至下一个个取出。
由此带来的访问入栈(push)、栈顶元素(top)、弹出栈顶(pop)时间复杂度都是.
栈的常见应用场景
- 程序内存管理:函数栈,用于记录函数的上下文信息;
- 撤销与重做:撤销操作时将操作入栈,重做时将撤销的操作一个个出栈。
栈的两种实现方式
我们可以使用数组或链表来实现栈,两种实现方式可以完成的栈功能都是一致的,但由于两种基本数据结构特性的不同,在部分操作的性能上存在差异。
使用数组实现时,为避免手动处理扩容问题,应使用动态数组实现。
两种实现方式的简单对比:
数组实现(数组尾部作栈顶) | 链表实现(链表头节点作栈顶) | |
---|---|---|
入栈(push ) |
添加尾部元素(push_back ) |
添加头节点(new->next = head;head = new->next ) |
访问栈顶(top ) |
访问尾部元素(back ) |
访问头节点(head->val ) |
出栈(pop ) |
删除尾部元素(pop_back ) |
删除头节点(head = head->next;delete ) |
时间效率 | 出入栈操作涉及到的内存均已预先分配,操作效率较高;但入栈时若超出数组容量会触发数组扩容,导致该次入栈操作时间复杂度变为,不过由于扩容是低频操作,平均效率较高。 | 链表不存在数组扩容的问题,但元素入栈需要初始化节点对象并修改指针,效率较低,若入栈元素本身就是节点对象则可省去初始化操作,提高效率。平均效率表现更稳定。 |
空间效率 | 初始化数组的空间可能是超出需求的,扩容机制按2倍或其它倍率扩容时也可能导致过多的空间浪费。 | 链表节点需要额外存储指针。两者具体空间效率要具体情况具体分析。 |
STL stack
C++STL stack容器提供如下操作:
STL 函数 | 描述 | 操作时间复杂度 |
---|---|---|
empty() | 判断栈是否为空 | |
size() | 返回栈中元素的个数 | |
top() | 返回栈顶元素 | |
push(element) | 将元素压入栈顶 | |
pop() | 弹出栈顶元素 |
队列
队列(Queue)是先进先出的数据结构,如同排队一样,我更喜欢将其想象为两端开口的管道,入队便是向管道入口放入小球,出队便是从管道出口取出小球,管道两端分别是只允许入或出的队尾和队首。
由此带来的入队(push)、访问队首(front)、出队(pop)时间复杂度均为.
队列的常见应用场景
- 进程调度:例如,就绪队列中存储着处于就绪状态等待被调度执行的进程,当 CPU 空闲时,操作系统从就绪队列中选择一个进程进行执行;
- 消息队列:在分布式 Web 服务架构中,不同的服务组件之间可以通过消息队列进行通信。例如,订单服务在处理完一个订单后,可以将订单处理完成的消息放入消息队列。
队列的两种实现方式
使用链表实现队列的思路比较常规,初始化头(front)尾(rear)节点,指向队列的头尾,并且规定队尾仅可添加,队首仅可删除,记录出入队记录队列长度(size)即可。
但Hello-algo中使用数组实现就比较妙了,它采用的方式是环形数组,所以这里着重讲一下环形数组实现队列的方法。示例实现这一方法时采用了queCapacity
描述队列容量,即数组上限,当然也可采用动态数组的形式进行扩容。
环形数组实现队列
使用数组实现队列时需要考虑解决这两个问题:
- 在数组中删除首元素的时间复杂度为(删除并移动元素),可以使用队首指针front和长度size对队列有效范围进行规定,然后定义队尾
rear = front + size
,如此数组中队列的有效区间便为; - 在不断的出入队过程中,front和rear移动到数组的尾部时将无法继续移动,解决方案是将数组视为首尾相接的环形数组。具体操作是让front或rear越过数组尾部时回到数组头部继续遍历,方法是取余。
// 基于环形数组实现的队列
class ArrayQueue {
private:
int* nums; // 用于存储队列元素的数组
int front; // 队首指针,指向队首元素
int queSize; // 队列长度
int queCapacity; // 队列容量
public:
ArrayQueue(int capacity) {
// 初始化队列
nums = new int[capacity];
front = 0;
queSize = 0;
queCapacity = capacity;
}
~ArrayQueue() {
delete[] nums;
}
// 队列容量
int capacity() {
return queCapacity;
}
// 队列大小
int size() {
return queSize;
}
// 队列是否为空
bool empty() {
if (queSize == 0) return true;
else return false;
}
// 访问队首
int front() {
if (empty()) {
std::cout << "队列为空" << std::endl;
return;
}
return nums[front];
}
// 访问队尾
int back() {
if (empty()) {
std::cout << "队列为空" << std::endl;
return;
}
return nums[front + queSize - 1];
}
// 入队
void push(int num) {
if (queSize == queCapacity) {
std::cout << "队列已满" << std::endl;
return;
}
int rear = (front + queSize) % queCapacity; // 取余:rear越过数组尾部回到头部
nums[rear] = num;
queSize++;
}
// 出队
int pop() {
if (empty()) {
std::cout << "队列为空" << std::endl;
return;
}
front = (front + 1) % queCapacity; // 取余:front越过数组尾部回到头部
queSize--;
}
};
STL queue
C++ STL queue容器提供如下操作:
STL 函数 | 描述 | 操作时间复杂度 |
---|---|---|
empty() | 判断队列是否为空 | |
size() | 返回队列中元素的个数 | |
front() | 返回队首元素 | |
back() | 返回队尾元素 | |
push(element) | 将元素压入队尾 | |
pop() | 弹出队首元素。 |
双向队列
不同于队列仅允许单进单出,双向队列(double-ended queue)允许在头部和尾部执行添加或删除操作,提供了更高的灵活性。
双向队列支持在队列的两端执行常数级别的增删操作,即时间复杂度为.
双向队列常见应用场景
- 滑动窗口算法:例如,在求解数组中连续子数组的最大和问题时,可以使用双向队列来存储当前窗口内的元素,通过不断地调整窗口的大小和更新队列中的元素,找到最大的子数组和;
- 设定上限的撤销与重做:考虑到系统资源限制,软件的撤销步数通常是有上限的,即软件需要在撤销队列的最底部(队首、栈底)删除最远的步数,但栈无法做到这一操作,这时便可以使用双向队列替代栈。
双向队列的两种实现方式
对应地,双向队列可以使用双向链表进行实现,在两端同时设计添加和删除节点功能。
数组实现则可参考队列的环形数组实现方案,在单向队列的基础上增加头节点(队尾)的删除和尾节点(队首)的添加功能。
STL deque
C++ STL deque容器提供如下操作:
STL 函数 | 描述 | 操作时间复杂度 |
---|---|---|
empty() | 判断双向队列是否为空 | |
size() | 返回双向队列中元素的个数 | |
front() | 返回双向队列的第一个元素的引用 | |
back() | 返回双向队列的最后一个元素的引用 | |
push_front(element) | 在双向队列的头部插入元素 | |
push_back(element) | 在双向队列的尾部插入元素 | |
pop_front() | 删除双向队列的第一个元素 | |
pop_back() | 删除双向队列的最后一个元素 |