数据结构与算法:堆栈和队列 - 双向队列
最编程
2024-03-14 13:41:23
...
双向队列(double‑ended queue)允许在头部和尾部执行元素的添加或删除操作
双向队列常用操作
/**
* File: deque.cpp
* Created Time: 2022-11-25
* Author: Krahets (krahets@163.com)
*/
#include "../utils/common.hpp"
/* Driver Code */
int main() {
/* 初始化双向队列 */
deque<int> deque;
/* 元素入队 */
deque.push_back(2);
deque.push_back(5);
deque.push_back(4);
deque.push_front(3);
deque.push_front(1);
cout << "双向队列 deque = ";
printDeque(deque);
/* 访问元素 */
int front = deque.front();
cout << "队首元素 front = " << front << endl;
int back = deque.back();
cout << "队尾元素 back = " << back << endl;
/* 元素出队 */
deque.pop_front();
cout << "队首出队元素 popFront = " << front << ",队首出队后 deque = ";
printDeque(deque);
deque.pop_back();
cout << "队尾出队元素 popLast = " << back << ",队尾出队后 deque = ";
printDeque(deque);
/* 获取双向队列的长度 */
int size = deque.size();
cout << "双向队列长度 size = " << size << endl;
/* 判断双向队列是否为空 */
bool empty = deque.empty();
cout << "双向队列是否为空 = " << empty << endl;
return 0;
}
双向队列实现
基于双向链表的实现
们将双向链表的头节点和尾节点视为双向队列的队首和队尾,同时实现在两端添加和删除节点的功能。
基于数组的实现
可以使用环形数组来实现双向队列。
双向队列应用
双向队列兼具栈与队列的逻辑,因此它可以实现这两者的所有应用场景,同时提供更高的*度。
软件的“撤销”功能通常使用栈来实现:系统将每次更改操作 push 到栈中,然后通过 pop 实现撤销。然而,考虑到系统资源的限制,软件通常会限制撤销的步数(例如仅允许保存 50 步)。当栈的长度超过50 时,软件需要在栈底(队首)执行删除操作。但栈无法实现该功能,此时就需要使用双向队列来替代栈。
学习地址:https://github.com/krahets/hello-algo
重新复习数据结构,所有的内容都来自这里。