有两个地方会讨论到栈一个是程序运行的栈空间一个是数据结构中的栈本文中讨论的是后者。栈是一个先入后出后入先出的数据结构只能操作栈顶。栈有两个操作push 和 poppush压栈pop出栈。栈还有一个操作 top这个操作可以查看栈顶的元素不会出栈。汉诺塔、摞起来的盘子、摞起来的书本就是现实中的栈。队列是一种先入先出后入后出的数据结构。队列也可以通过front来读取队列头pop来出队与栈类似。用队列实现栈每次都可以做转移用栈实现队列是条件转移之后pop栈是空的时候才可以转移。1 用队列实现栈leetcode 链接用队列实现栈用队列实现栈队列先入先出以及栈先入后出的语义不能改变。关键是怎么在压栈的时候将数据放到队列头这就需要两个队列进行配合。两个队列配合的方式有两种这两种方式均可以解答这个问题1入栈的时候进行元素移动① 两个队列始终保持一个队列是空的假设是队列 A压栈的时候将元素放入这个队列。这样最后入队的放到了队列头所以下次出栈的时候就是第一个出队的。满足先进后出后进先出的要求也就是栈的语义。② 然后将另一个队列(假设是队列 B)里边的元素都移动到这个队列中。这样元素都移动到了队列 A 中队列 B 成为了空队列。下一个元素入队的时候将元素入队到队列 B将元素 A 中的元素移动到 B 中。以此类推。每个元素入队的时候都做这个操作。第一个元素 10入队 AB 中没有元素不需要操作第二个元素 20入队 BA 中的 10 移动到 B第 3 个元素 30 入队 AB 中元素移动到 A2出栈的时候进行元素移动① 压栈的时候将元素入队到有元素的这个队列里边② 出栈的时候将元素移动到另一个队列中同时进行判断当队列剩余 1 个元素的时候这个元素就是出栈的元素不用移动到另一个队列中了。方法 1 的主要逻辑在 push函数中实现方法 2 的主要逻辑在 top和 pop 函数中都要实现。两个方法都可以通过两个队列来实现也可以通过一个队列也是可以实现的。1.1 入队时处理双队列class MyStack { public: MyStack() { } void push(int x) { if (q_master_.empty()) { q_master_.push(x); while (!q_slave_.empty()) { q_master_.push(q_slave_.front()); q_slave_.pop(); } } else { q_slave_.push(x); while (!q_master_.empty()) { q_slave_.push(q_master_.front()); q_master_.pop(); } } } int pop() { if (!q_master_.empty()) { int data q_master_.front(); q_master_.pop(); return data; } else { int data q_slave_.front(); q_slave_.pop(); return data; } } int top() { if (!q_master_.empty()) { return q_master_.front(); } else { return q_slave_.front(); } } bool empty() { return q_master_.empty() q_slave_.empty(); } private: std::queueint q_master_; std::queueint q_slave_; };1.2 入队时操作单队列关键是 push() 函数中的操作将元素入队之后然后将新元素之外的元素出队再重新入队。这样保证了新入队的元素移动到了队列头的位置下次出栈的时候直接出队就可以。class MyStack { public: MyStack() { } void push(int x) { q_.push(x); int size q_.size(); for (int i 0; i size - 1; i) { q_.push(q_.front()); q_.pop(); } } int pop() { int data q_.front(); q_.pop(); return data; } int top() { return q_.front(); } bool empty() { return q_.empty(); } private: std::queueint q_; };1.3 出队时操作双队列class MyStack { public: MyStack() { } void push(int x) { if (!q_master_.empty()) { q_master_.push(x); } else { q_slave_.push(x); } } int pop() { if (!q_master_.empty()) { int size q_master_.size(); for (int i 0; i size - 1; i) { q_slave_.push(q_master_.front()); q_master_.pop(); } int data q_master_.front(); q_master_.pop(); return data; } else { int size q_slave_.size(); for (int i 0; i size - 1; i) { q_master_.push(q_slave_.front()); q_slave_.pop(); } int data q_slave_.front(); q_slave_.pop(); return data; } } int top() { if (!q_master_.empty()) { int size q_master_.size(); for (int i 0; i size - 1; i) { q_slave_.push(q_master_.front()); q_master_.pop(); } int data q_master_.front(); q_master_.pop(); q_slave_.push(data); return data; } else { int size q_slave_.size(); for (int i 0; i size - 1; i) { q_master_.push(q_slave_.front()); q_slave_.pop(); } int data q_slave_.front(); q_slave_.pop(); q_master_.push(data); return data; } } bool empty() { return q_master_.empty() q_slave_.empty(); } private: std::queueint q_master_; std::queueint q_slave_; };1.4 出队时操作单队列class MyStack { public: MyStack() { } void push(int x) { q_.push(x); } int pop() { int size q_.size(); for (int i 0; i size - 1; i) { q_.push(q_.front()); q_.pop(); } int data q_.front(); q_.pop(); return data; } int top() { int size q_.size(); for (int i 0; i size - 1; i) { q_.push(q_.front()); q_.pop(); } int data q_.front(); q_.pop(); q_.push(data); return data; } bool empty() { return q_.empty(); } private: std::queueint q_; };2 用栈实现队列leetcode 链接用栈实现队列用栈实现队列需要在出队的时候进行操作。在入队的时候进行操作算法不好实现不像队列中的元素比如元素顺序是 E1、E2、E3、E4、E5那么元素在移动之后还是这样的顺序移动多次之后还是保持这样的顺序。但是对于栈来说每移动一次就会导致顺序翻转所以在入队的时候进行操作的算法不好实现。使用栈实现队列需要使用两个栈。只使用一个栈算法也不好实现。两个栈 A 和 B在入队的时候只往 A 压栈出队的时候只从 B 出栈。当 B 是空的时候那么将 A 中所有的元素都移动到 B。class MyQueue { public: MyQueue() { } void push(int x) { s_in_.push(x); } int pop() { if (s_out_.empty()) { while (!s_in_.empty()) { s_out_.push(s_in_.top()); s_in_.pop(); } } int ret s_out_.top(); s_out_.pop(); return ret; } int peek() { if (s_out_.empty()) { while (!s_in_.empty()) { s_out_.push(s_in_.top()); s_in_.pop(); } } return s_out_.top(); } bool empty() { return s_out_.empty() s_in_.empty(); } private: std::stackint s_in_; std::stackint s_out_; };3用栈判断括号表达式的合法性判断括号表达式的合法性是典型的使用栈的题目。([)]像这样的表达式虽然小括号和大括号都是成对出现的并且都是先出现的左括号后出现的右括号也不是合法的表达式。所以针对这个题目使用最基本的思路来判断是无法实现的无法处理括号交叉嵌套的情况。使用栈的特性一旦配对就把这一层的括号弹出来处理括号交叉嵌套的情况。templatetypename T class Stack { public: void push(T const element) { data_.push_back(element); } void pop() { data_.pop_back(); } T top() { return data_.back(); } bool empty() { return data_.size() 0; } int size() { return data_.size(); } private: std::vectorT data_; }; class Solution { public: bool isValid(string s) { Stackchar stack; for (char c : s) { switch (c) { case (: case [: case {: { stack.push(c); break; } case ):{ if (stack.empty()) { return false; } char tmp stack.top(); if (tmp () { stack.pop(); }else{ return false; } break; } case ]:{ if (stack.empty()) { return false; } char tmp stack.top(); if (tmp [) { stack.pop(); }else { return false; } break; } case }: { if (stack.empty()) { return false; } char tmp stack.top(); if (tmp {) { stack.pop(); }else { return false; } } default:{ break; } } } if (!stack.empty()) { return false; } return true; } };
