常见的栈与队列算法题
1. 使用队列实现栈
2. 使用栈实现队列
3. 包含最小值函数的栈
4. 合法的出栈序列
5. 简单计算器
1. 队列实现栈
- class MyStack {
- public:
- /** Initialize your data structure here. */
- MyStack() {
- }
- /** Push element x onto stack. */
- void push(int x) {
- int len=data.size();
- data.push(x);
- while(len>0){
- data.push(data.front());
- data.pop();
- len--;
- }
- }
- /** Removes the element on top of the stack and returns that element. */
- int pop() {
- int res=data.front();
- data.pop();
- return res;
- }
- /** Get the top element. */
- int top() {
- return data.front();
- }
- /** Returns whether the stack is empty. */
- bool empty() {
- return data.empty();
- }
- private:
- std::queue<int> data;
- };
- /**
- * 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();
- */
主要是 push 函数的编写. x 进队后, 让之前的元素 一 一 出队再入队.
2. 栈实现队列
- class MyQueue {
- public:
- /** Initialize your data structure here. */
- MyQueue() {
- }
- /** Push element x to the back of queue. */
- void push(int x) {
- while(s.size()){
- s_temp.push(s.top());
- s.pop();
- }
- s.push(x);
- while(s_temp.size()){
- s.push(s_temp.top());
- s_temp.pop();
- }
- }
- /** Removes the element from in front of queue and returns that element. */
- int pop() {
- int res=s.top();
- s.pop();
- return res;
- }
- /** Get the front element. */
- int peek() {
- return s.top();
- }
- /** Returns whether the queue is empty. */
- bool empty() {
- return s.empty();
- }
- private:
- std::stack<int> s,s_temp;
- };
- /**
- * 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();
- */
缺点是, 入队所需时间太长, 操作步数为 2n 步. 其他为常数.
改进
- class MyQueue {
- public:
- /** Initialize your data structure here. */
- MyQueue() {
- }
- void transfer(){
- while(!in.empty()){
- out.push(in.top());
- in.pop();
- }
- }
- /** Push element x to the back of queue. */
- void push(int x) {
- in.push(x);
- }
- /** Removes the element from in front of queue and returns that element. */
- int pop() {
- int res=peek();
- out.pop();
- return res;
- }
- /** Get the front element. */
- int peek() {
- if(out.size()==0)
- transfer();
- return out.top();
- }
- /** Returns whether the queue is empty. */
- bool empty() {
- return (in.empty() && out.empty());
- }
- private:
- std::stack<int> in,out;
- };
- /**
- * 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();
- */
pop 和 peek 平均都为 n/2 步, 总步数 n 步. 略微简化了一些.
3. 最小值栈
设计一个支持 push,pop,top 操作, 并能在常数时间内检索到最小元素的栈.
push(x) -- 将元素 x 推入栈中.
pop() -- 删除栈顶的元素.
top() -- 获取栈顶元素.
getMin() -- 检索栈中的最小元素.
- class MinStack {
- public:
- /** initialize your data structure here. */
- MinStack() {
- }
- void push(int x) {
- s.push(x);
- if(sMin.empty() || x <= sMin.top()){
- sMin.push(x);
- }
- }
- void pop() {
- if(s.top()==sMin.top()){
- s.pop();
- sMin.pop();
- }else{
- s.pop();
- }
- }
- int top() {
- return s.top();
- }
- int getMin() {
- return sMin.top();
- }
- private:
- std::stack<int> s,sMin;
- };
- /**
- * 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();
- */
用另一个栈 sMin 记录最小值. 空间复杂度 O(n).
4. 合法的出栈序列
- class Solution {
- public:
- bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
- stack<int> s;
- int len=pushed.size();
- int i=0,j=0;
- while(i<len){
- s.push(pushed[i++]);
- while(!s.empty()){
- if(s.top()==popped[j]){
- s.pop();
- j++;
- }else{
- break;
- }
- }
- }
- return s.empty();
- }
- };
借助一个栈 s, 模拟进出栈顺序. 遍历 pushed 数组, 先将元素进栈. 然后再开一个出栈循环, 若栈不空, 将栈顶与 popped 数组元素比较, 相同则出栈, 继续下一个循环; 不同则跳出出栈循环, 继续外面的进栈操作. 最后返回是否栈空. 以上应该是最为清晰的思路了, 之前我也写过两个, 一个暴力法判断, 时间复杂度较高, 逻辑也很复杂; 另一个也是模拟进出栈, 但是思路太乱, 代码逻辑冗余混乱, 简单来说就是模拟的不够真实, 反而导致自己思路不畅.
5. 简单计算器
实现一个基本的计算器来计算一个简单的字符串表达式的值.
字符串表达式可以包含左括号 ( , 右括号 ), 加号 + , 减号 -, 非负整数和空格 .
- class Solution {
- public:
- int calculate(string s) {
- int len = s.length();
- if (len == 0) return 0;// 长度为 0 直接返回 0
- int num1 = 0, num2 = 0;// 存储运算数
- bool flag = false;// 是否能进行运算
- stack<int> num;// 数字栈
- stack<char> op;// 运算符栈
- int temp = 0;// 存储数字
- for (int i = 0; i <len; i++) {
- if (s[i] == ' ') continue;
- if (s[i]>= '0' && s[i] <= '9') {
- temp = temp * 10 + s[i] - '0';
- if (i + 1 == len || s[i + 1]<'0' || s[i + 1]>'9') {
- num.push(temp);
- temp = 0;// 清 0
- }else {
- continue;// 继续入栈求该数字
- }
- }else if (s[i] == '(') {
- flag = false;// 设置无法运算
- continue;
- }else if (s[i] == '+' || s[i] == '-') {
- op.push(s[i]);
- flag = true;// 可以运算
- continue;
- }else if(s[i]==')'){
- flag = true;// 可以运算
- }
- if (flag && !op.empty()) { // 运算栈不为空才可以运算
- num2 = num.top(); num.pop();
- num1 = num.top(); num.pop();
- if (op.top() == '+') {
- num.push(num1 + num2);
- }
- else {
- num.push(num1 - num2);
- }
- op.pop();// 不要忘记出栈
- }
- }
- return num.top();
- }
- };
重点在于 flag, 表示是否能进行运算. 数字入数字栈, 运算符入运算符栈, 且设 flag=true. 左括号使得 flag=false, 右括号使得 false=true.flag 为 true 且运算栈不为空则进行运算, 运算完不要忘记出栈
来源: http://www.bubuko.com/infodetail-2921136.html