STL

棧：std::stack<int> S;
S.top() S.empty() S.push(x) S.pop() S.size()
隊列：std:queue<int> Q;
Q.empty()、Q.front()、Q.back()、Q.pop()、Q.push()、Q.size()

題225 用隊列實現棧

用時：0ms 100% 內存 7MB 100%

class MyStack { public:/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {std::queue<int> temp_queue;temp_queue.push(x);while(!data_queue.empty()){int a = _data.front();temp_queue.push(a);_data.pop();}while(!temp_queue.empty()){data_queue.push(temp_queue.front());temp_queue.pop();}}/** Removes the element on top of the stack and returns that element. */int pop() {int x = data_queue.front();data_queue.pop();return x;}/** Get the top element. */int top() {return data_queue.front();}/** Returns whether the stack is empty. */bool empty() {return data_queue.empty();} private:std::queue<int> data_queue; };/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/

題232 用棧實現隊列

用時：0ms 100% 內存 7.2MB 100%

class MyQueue { public:/** Initialize your data structure here. */MyQueue() {}/** Push element x to the back of queue. */void push(int x) {std::stack<int> temp_stack;while(!data_stack.empty()){temp_stack.push(data_stack.top());data_stack.pop();}temp_stack.push(x);while(!temp_stack.empty()){data_stack.push(temp_stack.top());temp_stack.pop();}}/** Removes the element from in front of queue and returns that element. */int pop() {int x = data_stack.top();data_stack.pop();return x;}/** Get the front element. */int peek() {return data_stack.top();}/** Returns whether the queue is empty. */bool empty() {return data_stack.empty();} private:std::stack<int> data_stack; };/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/

題155 最小棧

用時：40ms 43.19% 內存：15.2MB 100%

class MinStack { public:/** initialize your data structure here. */std::stack<int> data;std::stack<int> min_data;MinStack() {}void push(int x) {data.push(x);if(min_data.empty()){min_data.push(x);}else{if(x < min_data.top()){min_data.push(x);}else{min_data.push(min_data.top());}}}void pop() {data.pop();min_data.pop();//最小值棧中最小值的位置和原來棧中位置是一致的//所以可以同時彈出}int top() {return data.top();}int getMin() {return min_data.top();} };/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(x);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

題946 驗證棧序列

給定 pushed 和 popped 兩個序列，每個序列中的 值都不重復，只有當它們可能是在最初空棧上進行的推入 push 和彈出 pop 操作序列的結果時，返回 true；否則，返回 false 。
示例 1：
輸入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
輸出：true
解釋：我們可以按以下順序執行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
輸入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
輸出：false
解釋：1 不能在 2 之前彈出。
提示：
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。

用 $j$ 指針指向數組 $popped$ 可以模擬隊列，數 組$pushed$ 存在棧中。如果棧頂元素和隊列元素，則同時彈出。如果棧空，則合法。否則，不合法。

class Solution { public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {std::stack<int> s;int n = pushed.size();int j = 0;//poped索引//將pushed壓棧for(int i = 0; i < n; i++){s.push(pushed[i]);while(!s.empty()&&s.top()==popped[j]){s.pop();j++;}}return s.empty();} };

總結

以上是生活随笔為你收集整理的【LeetCode】分类刷题 之 栈和队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。