# 栈栈上一种遵循陷入后出的线性数据结构。 ## 栈的常用操作 | 方法 | 描述 | 时间复杂度 | | ------ | ------------ | ---------- | | push() | 元素入栈 | O(1) | | pop() | 栈顶元素出栈 | O(1) | | peek() | 访问栈顶元素 | O(1) | ```cpp stack stack; stack.push(1); stack.push(3); stack.push(2); stack.push(5); stack.push(4); int top = stack.top(); stack.pop(); int size = stack.size() bool empty = stack.empty(); ``` ## 栈的实现栈遵循先入后出的原则，因此只能在栈顶添加或删除元素。然而，数组和链表都可以在任意位置添加和删除元素，因此栈可以被视作一种受限制的数组或链表。也就是是栈可以给予数组或链表实现。 ### 基于链表实现的栈 ```cpp class LinkedListStack { private: ListNode *stackTop; int stkSize; public: LinkedListStack() { stackTop = nullptr; stkSize = 0; } ~LinkedListStack() { // 便利删除节点，释放内存 freeMemoryLinkedList(stackTop); } int size() { return stkSize; } bool isEmpty() { return size() == 0; } void push(int num) { ListNode *node = new ListNode(num); node->next = stackTop; stackTop = node; stkSize++; } int pop() { int num = top(); ListNode *tmp = stackTop; stackTop = stackTop->next; delete tmp; stkSize--; return num; } int top(){ if(isEmpty()) throw out_of_range("栈为空"); return stackTop->val; } vector toVector(){ ListNode *node = stackTop; vector res(size()); for(int i = res.size() - 1; i >= 0; i--){ res[i] = node->val; node = node->next; } return res; } } ``` ### 基于数组实现的栈 ```cpp class ArrayStack { private: vector stack; public: int size() { return stack.size(); } bool isEmpty(){ return stack.size() == 0; } void push(int num){ stack.push_back(num); } int pop(){ int num = top(); stack.pop_back(); return num; } int top(){ if(isEmpty()) throw out_of_range("栈为空"); return stack.back(); } vector toVector(){ return stack; } } ``` # 队列队列是一种先入先出的规则线性数据结构，顾名思义，队列就是模拟排队的现象。 ## 队列的常用操作 | 方法名 | 描述 | 时间复杂度 | | ------ | ---------------------------- | ---------- | | push() | 元素入队，即将元素添加至队尾 | O(1) | | pop() | 队首元素出队 | O(1) | | peek() | 访问队首元素 | O(1) | ```cpp queue queue; queue.push(1); queue.push(3); queue.push(2); queue.push(5); queue.push(4); int front = queue.front(); queue.pop(); int size = queue.size(); bool empty = queue.empty(); ``` ## 队列实现队列的实现可以通过链表或数组来实现 ### 基于链表的实现 ```cpp class LinkedListQueue { private: ListNode *front, *rear; int queSize; public: LinkedListQueue() { front = nullptr; rear = nullptr; queSize = 0; } ~LinkedListQueue() { freeMemoryLinkedList(front); } int size(){ return queSize; } bool isEmpty() { return queSize == 0; } void push(int num){ ListNode *node = new ListNode(num); if(front == nullptr) { front = node; rear = node; }else { rear->next = node; rear = node; } queSize++; } int pop(){ int num = peek(); ListNode *tmp = front; front = front->next; delete tmp; queSize--; return num; } int peek() { if(size() == 0); throw out_of_range("队列为空"); return front->val; } vector toVector() { ListNode *node = front; vector size(size()); for(int i = 0; i < res.size(); i++){ res[i] = node->val; node = node->next; } return res; } } ``` ### 基于数组实现 ```cpp class ArrayQueue{ private: int *nums; int front; int queSize; int queCapacity; public: ArrayQueue(int capacity){ nums = new int[capacity]; queCapacity = capacity; front = queSize = 0; } ~ArrayQueue(){ delete[] nums; } int capacity(){ return queCapacity; } int size() { return queSize; } bool isEmpty() { return size() == 0; } void push(int num){ if(queSize == queCapacity){ cout << "队列已满" << endl; return; } int rear = (front + queSize) % queCapacity; nums[rear] = num; queSize++; } void pop(){ int num = peek(); front = (front + 1) % queCapacity; queSize--; return num; } int peek(){ if(isEmpty()) throw out_of_range("队列为空"); return nums[front]; } vector toVector() { vector arr(queSize); for(int i = 0; j = front; i < queSize; i++, j++){ arr[i] = nums[j % queCapacity]; } return arr; } } ``` # 双向队列队列简单来说就和排队一样，先进先出。双向队列顾名思义就是可以在首尾都可以进行操作的一个数据结构。双向队列的常用操作如下： | 方法名 | 描述 | 时间复杂度 | | ------------ | ---------------- | ---------- | | push_first() | 将元素添加至队首 | O(1) | | push_last() | 将元素添加至队尾 | O(1) | | pop_first() | 删除队首元素 | O(1) | | pop_last() | 删除队尾元素 | O(1) | | peek_first() | 访问队首元素 | O(1) | | peek_last() | 访问队尾元素 | O(1) | ```cpp deque deque; deque.push_back(2); deque.push_back(5); deque.push_back(4); deque.push_front(3); deque.push_front(1); int front = deque.front(); int back = deque.back(); deque.pop_front(); deque.pop_back(); int size = deque.size(); bool empty = deque.empty(); ``` ## 双向队列实现双向队列的实现与队列类似，可以选择链表或数组作为底层的数据结构。 ### 基于双向链表的实现 ``` cpp struct DoublyListNode { int val; DoublyListNode *next; DoublyListNode *prev; DoublyListNode(int val) : val(val), prev(nullptr), next(nullptr) {} } class LinkedListDeque { private: DoublyListNode *front, *rear; int queSize = 0; public: LinkedListDeque() : front(nullptr), rear(nullptr) {} ~LinkedListDeque() { DoublyListNode *pre, *cur = front; while(cur != nullptr){ pre = cur; cur = cur->next; delete pre; } } int size(){ return queSize; } bool isEmpty() { return size() == 0; } void push(int num, bool isFront) { DoublyListNode *node = new DoublyListNode(num); if(isEmpty()) front = rear = node; else if(isFront){ front->prev = node; node->next = front; front = node; } else { rear->next = node; node->prev = rear; rear = node; } queSize++; } void pushFirst(int num){ push(num, true); } void pushLast(int num){ push(num, false); } int pop(bool isFront){ if(isEmpty()) throw out_of_range("列队为空"); int val; if(isFront){ val = front->val; DoublyListNode *fNext = front->next; if(fNext != nullptr){ fNext->prev = nullptr; front->next = nullptr; } delete front; front = fNext; } else { val = rear->val; DoublyListNode *rPrev = rear->prev; if(rPrev != nullptr) { rPrev->next = nullptr; rear->prev = nullptr; } delete rear; rear = rPrev; } queSize--; return val; } int popFirst(){ return pop(true); } int popLast(){ return pop(false); } int peekFirst(){ if(isEmpty()) throw out_of_range("双向队列为空"); return front->val; } int peekLast() { if(isEmpty()) throw out_of_range("双向队列为空"); return rear->val; } vector toVector(){ DoublyListNode *node = front; vector res(size()); for(int i = 0; i < res.size(); i++) { res[i] = node->val; node = node->next; } return res; } } ``` ### 基于数组的实现 ```cpp class ArrayDeque { private: vector nums; int front; int queSize; public: ArrayDeque(int capacity){ nums.resize(capacity); front = queSize = 0; } int capacity() { return nums.size(); } int size(){ return queSize; } bool isEmpty(){ return queSize == 0; } int index(int i){ return (i + capacity()) % capacity(); } void pushFirst(int num){ if(queSize == capacity){ cout << "双向队列已满" << endl; return; } front = index(front - 1); nums[front] = num; queSize++; } void pushLast(int num) { if(queSize == capacity()){ cout << "双向队列已满" << endl; return; } int rear = index(front + queSize); nums[rear] = num; queSize++ } int popFirst() { int num = peekFirst(); front = index(front + 1); queSize--; return num; } int popLast() { int num = peekLast(); queSize--; return num; } int peekFirst(){ if(isEmpty()) throw out_of_range("双向队列为空"); return nums[front]; } int peekLast(){ if(isEmpty()) throw out_of_range("双向队列为空"); int last = index(front + queSize - 1); return nums[last]; } vector toVector() { vector res(queSize); for(int i = 0, j = front; j< queSize; i++, j++){ res[i] = nums[index(j)]; } return res; } } ```