栈 - acgtyrant/Algorithm-and-Data-Structure GitHub Wiki
自初战来，连续九次 submit 全 accepted. 最终第十次 submit 栽在这题上，大意失荆州啊，谁叫我对栈的掌握还不够深呢。
C++ 实现，第一次用上了传说中的 std::stack, 奇的是，虽然 C++ Primer 说它是一种「适配器」，然而也可以当独立的容器用。此外，我吃惊的发现 STL 中的 pop 和 pop_back 都不返回值，人神共愤！原因参见STL中的stack的pop函数为什么不返回值?
class Solution {
public:
bool isValid(string s) {
stack<char> brackets;
for (auto bracket: s) {
// C++11 特性，够时髦吧！
if (bracket == '(' || bracket == '{' || bracket == '[') {
brackets.push(bracket);
continue;
}
if (brackets.size() == 0) return false;
// 陷阱！如果 brackets 是空的，那么下面的 top() 就会发生异常。
// 所以我们需要判断 size, 当为零时直接返回 false.
// 此外在函数开头判断 size 是否为奇偶，没用，毕竟哪怕 size 为偶数时
// 也有可能不合法，比如 "]]".
if (bracket == ')' && brackets.top() != '(') return false;
if (bracket == '}' && brackets.top() != '{') return false;
if (bracket == ']' && brackets.top() != '[') return false;
// 直接用 && 来保证在前一个判断括号的表达式为真时才继续执行后一种表达式
brackets.pop();
}
return brackets.size() == 0; // 直接返回判断 size 的表达式即可
}
};戒记戒记，在调用 top 或 pop 前，要判断 size 是否为零！
class MinStack {
public:
void push(int x) {
normal_stack_.push(x);
// 当 x 不大于 minimum_stack_.top(), push, 一来成功记录了当前栈依次递减的最小值
// 二来也保存了重复的最小值
// 别忘了判断 minimum_stack_.size() 为零的极端情况
if (minimum_stack_.size() == 0 || x <= minimum_stack_.top()) {
minimum_stack_.push(x);
}
}
void pop() {
// 当 normal_stack_ 所要 pop 的值正好是当前最小值时，
// 也一并把 minimum_stack_ 给 pop 了
if (normal_stack_.top() == minimum_stack_.top()) {
minimum_stack_.pop();
}
normal_stack_.pop();
}
int top() {
return normal_stack_.top();
}
int getMin() {
return minimum_stack_.top();
}
private:
// 直接用 `std::stack` 创建两个栈，一个照常用，另一个专门 push 前者的当时最小值。
stack<int> normal_stack_;
stack<int> minimum_stack_;
};queue 是 LIFO, 所以在 pop 或 top 函数里先把最尾部元素前的统统 OUT 再依次 IN 进去就行了。
class Stack {
public:
// Push element x onto stack.
void push(int x) {
stack_.push(x);
}
// Removes the element on top of the stack.
void pop() {
int temporary_value;
for (int i = 1; i < stack_.size(); ++i) {
temporary_value = stack_.front();
stack_.pop();
stack_.push(temporary_value);
}
stack_.pop();
}
// Get the top element.
int top() {
int temporary_value;
for (int i = 1; i <= stack_.size(); ++i) {
temporary_value = stack_.front();
stack_.pop();
stack_.push(temporary_value);
}
return temporary_value;
}
// Return whether the stack is empty.
bool empty() {
return stack_.empty();
}
private:
queue<int> stack_;
};正好与 ## LeetCode 225 对称，然而不像 queue 直接把首元素 push 到尾部，我们必须建立临时的 stack 以接收颠倒了的 stack. 既然要接收到临时 stack, 干脆一劳永逸把它设为正式的 stack, 专门用于 pop 和 peek 上，方便了得。
class Queue {
public:
// Push element x to the back of queue.
void push(int x) {
if (!is_stack_down_) {
StackSwap(up_, down_);
is_stack_down_ = true;
}
down_.push(x);
}
// Removes the element from in front of queue.
void pop(void) {
if (is_stack_down_) {
StackSwap(down_, up_);
is_stack_down_ = false;
}
up_.pop();
}
// Get the front element.
int peek(void) {
if (is_stack_down_) {
StackSwap(down_, up_);
is_stack_down_ = false;
}
return up_.top();
}
// Return whether the queue is empty.
bool empty(void) {
return is_stack_down_ ? down_.empty() : up_.empty();
}
private:
void StackSwap(stack<int> &source, stack<int> &destination) {
while (!source.empty()) {
destination.push(source.top());
source.pop();
}
}
stack<int> up_;
stack<int> down_;
bool is_stack_down_ = true;
};此外我曾把 StackSwap 错写成：
void StackSwap(stack<int> &source, stack<int> &destination) {
int temporary_value;
for (int i = 0; i < source.size(); ++i) {
temporary_value = source.top();
source.pop();
destination.push(temporary_value);
}
}殊不知 source.size() 在循环里会变，看来不光要留意迭代器，还要对 size 长心眼。