双端队列(deque)和双端栈(double ended stack)
组别：提高组
难度：5
双端队列(deque)和双端栈（Double-ended Stack）是一种特殊的数据结构，它允许在两端进行操作。双端栈结合了栈和队列的特性，使得在头部和尾部都可以进行插入和删除的操作，适用于需要双向访问的场景。
常用函数：
| 成员函数 | 功能 |
| dq.front() | 返回双端队列中的第一个元素的引用 |
| dq.back() | 返回双端队列中的最后一个元素的引用 |
| dq.push_front(value) | 头部添加元素 |
| deq.push_back(value) | 末尾添加元素 |
| deq.insert(pos, value) | 在pos迭代器之前插入一个值为value的元素 |
| deq.pop_front() | 头部删除元素 |
| deq.pop_back() | 末尾删除元素 |
deque的C++实现示例。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | /**************************************************************** * Description: double ended stack * Author: Alex Li * Date: 2024-06-24 11:54:08 * LastEditTime: 2024-06-24 12:02:03 ****************************************************************/ #include <iostream> #include <deque> std::deque<int> deq; // 检查栈是否为空 bool isEmpty(){ return deq.empty(); } // 从头部入栈 void pushFront(int value) { deq.push_front(value); } // 从尾部入栈 void pushBack(int value) { deq.push_back(value); } // 从头部出栈 int popFront() { if (!deq.empty()) { int value = deq.front(); deq.pop_front(); return value; } else { throw std::out_of_range("Stack is empty"); } } // 从尾部出栈 int popBack() { if (!deq.empty()) { int value = deq.back(); deq.pop_back(); return value; } else { throw std::out_of_range("Stack is empty"); } } // 获取头部元素 int front(){ if (!deq.empty()) { return deq.front(); } else { throw std::out_of_range("Stack is empty"); } } // 获取尾部元素 int back(){ if (!deq.empty()) { return deq.back(); } else { throw std::out_of_range("Stack is empty"); } } // 获取栈的大小 size_t size(){ return deq.size(); } int main() { // 测试双端栈功能 pushFront(10); pushBack(20); pushFront(5); pushBack(25); std::cout << "Front element: " <<front() << std::endl; // 输出 5 std::cout << "Back element: " << back() << std::endl; // 输出 25 std::cout << "Popping from front: " <<popFront() << std::endl; // 输出 5 std::cout << "Popping from back: " << popBack() << std::endl; // 输出 25 std::cout << "Stack size: " <<size() << std::endl; // 输出 2 return 0; } |