1.两个栈实现一个队列
class CQueue { stack<int> s1; stack<int> s2; public: CQueue() { } void appendTail(int value) { s1.push(value); } int deleteHead() { int res; if (s2.empty()) { if (s1.empty()) { return -1; } else { while (!s1.empty()) { s2.push(s1.top()); s1.pop(); } res = s2.top(); s2.pop(); } } else { res = s2.top(); s2.pop(); } return res; } };2.包含min函数的栈:
class MinStack { stack<int> s; stack<int> mins; public: /** initialize your data structure here. */ MinStack() { } void push(int x) { if (s.empty()) { s.push(x); mins.push(x); return; } s.push(x); if (x > mins.top()) { mins.push(mins.top()); } else { mins.push(x); } } void pop() { s.pop(); mins.pop(); } int top() { return s.top(); } int min() { return mins.top(); } }; 验证栈序列(leetcode 946) 给定 pushed 和 popped 两个序列,每个序列中的 值都不重复,只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时,返回 true;否则,返回 false 。 bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { if (pushed.size() != popped.size()) { return false; } stack<int> s; int j =0; for (int i = 0; i < pushed.size(); i++) { s.push(pushed[i]); while (!s.empty() && s.top() == popped[j]) { s.pop(); j++; } } return s.empty(); }4.用队列实现栈
class MyStack { queue<int> q; public: /** Initialize your data structure here. */ MyStack() { } /** Push element x onto stack. */ void push(int x) { queue<int> tmp; tmp.push(x); while (!q.empty()) { int temp = q.front(); q.pop(); tmp.push(temp); } while (!tmp.empty()) { int temp = tmp.front(); tmp.pop(); q.push(temp); } } /** Removes the element on top of the stack and returns that element. */ int pop() { int res = q.front(); q.pop(); return res; } /** Get the top element. */ int top() { return q.front(); } /** Returns whether the stack is empty. */ bool empty() { return q.empty(); } };