栈和队列的练习题

​1. 用两个栈实现队列

用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

数据范围：n≤1000

要求：存储n个元素的空间复杂度为 O(n) ，插入与删除的时间复杂度都是 O(1)

解题思路：

借助栈的先进后出规则模拟实现队列的先进先出。想用用栈实现队列，需要把一个栈中的元素挨个pop 出来，然后再 push 进另一个栈中。题中的 push 方法中就直接将元素插入 stack1 中。pop 方法中，当 stack2 不为空时，弹出 stack2 的栈顶元素；如果 stack2 为空时，将 stack1 中的元素先pop 出去，然后再 push 到 stack2 中。

代码实现：

import java.util.*;
import java.util.Stack;
 
public class Solution {
    Stack stack1 = new Stack();
    Stack stack2 = new Stack();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        // 如果 stack2 为空，先让 stack1 pop出栈顶元素
        if(stack2.size() <= 0) {
            while(stack1.size() != 0) {
                stack2.push(stack1.pop());
            }
        }
        // 如果 stack2 不为空，直接弹出栈顶元素
        return stack2.pop();
    }
}

---

2. 包含min函数的栈 

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有：

push(value):将value压入栈中

pop():弹出栈顶元素

top():获取栈顶元素

min():获取栈中最小元素

数据范围：操作数量满足 0≤n≤300  ，输入的元素满足 ∣val∣≤10000 
进阶：栈的各个操作的时间复杂度是 O(1)  ，空间复杂度是 O(n)

解题思路：

使用双栈，一个栈中正常 push 元素进行 pop、top 操作，另一个栈记录每次 push 的最小值。第一个栈 push 元素时，当另一个栈中没有元素时将当前插入的元素 push 进去，然后每一次插入元素时两个栈中的栈顶元素进行比较。如果当前插入的元素小于第二个栈的栈顶元素，就将当前元素 push 到第二个栈中，否则就将第二个栈中的栈顶元素重新入栈。这样第二个栈顶元素仍然是最小值。

画图理解：

代码实现：

import java.util.*;
import java.util.Stack;
 
public class Solution {
    Stack stack1 = new Stack<>();
    // stack2 中存放最小值
    Stack stack2 = new Stack<>();
    
    public void push(int node) {
        stack1.push(node);
        // 如果 stack2 为空，stack2的栈顶元素大于当前插入的值
        if(stack2.isEmpty() || stack2.peek() > node) {
            // 就将当前插入的元素入栈
            stack2.push(node);
        } else  {
            // 如果 stack2 不为空，且当前栈顶元素小于当前插入的值
            // 就将 stack2 当前栈顶元素重新入栈
            stack2.push(stack2.peek());
        }
    }
    
    public void pop() {
        stack1.pop();
        stack2.pop();
    }
    
    public int top() {
        return stack1.peek();
    }
    
    public int min() {
        return stack2.peek();
    }
}

---

3. 有效括号序列 

给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。

解题思路：

括号的有效是指 "( )[ ]{ }"或者这种“( [ ] )”，也就是符合先进后出的原理，最左出现的括号对应的括号一定在最右。所以就可以使用栈来完成，遇到左括号就将相应匹配的右括号加入栈中，后续如果是合法的，右括号的顺序就是栈中弹出的顺序。

public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        // write code here
        Stack  stack = new Stack<>();
        for(char c : s.toCharArray()) {
            if(c == '(') {
                stack.push(')');
            } else if(c == '{') {
                stack.push('}');
            } else if(c == '[') {
                stack.push(']');
            } else if(stack.isEmpty() || c != stack.pop()) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

---

4. 表达式求值 

请写一个整数计算器，支持加减乘三种运算和括号。

数据范围：1000≤∣s∣≤100，保证计算结果始终在整型范围内

要求：空间复杂度： O(n)，时间复杂度 O(n)

解题思路：

使用双栈存放数字和运算符，其中需要考虑的是运算符优先级和括号的处理问题。对于优先级问题，乘法优先，加减法最后。当遇到乘法时，把前一个数和后一个数相乘，遇到加减法，把这些数字都暂存起来，最后再相加。处理括号问题，就是将括号中的部分看成一个整体，每次遇到左括号，将括号放入栈中，直到遇到右括号，再计算括号中的部分。

代码实现：

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        // 存放所有的运算符
        Stack ops = new Stack<>();
        // 存放所有的数字
        Stack nums = new Stack<>();
        if(s.length() < 2) {
            return (int)s.charAt(0);
        }
        // 由于第一个数可能是负数，为了减少边界判断，第一个数放0
        nums.push(0);
        for(int i = 0; i < s.length();) {
            // 如果是左括号，将左括号放入到 ops 栈中
            if(s.charAt(i) == '(') {
                ops.push(s.charAt(i++));
            } else if(s.charAt(i) == ')') {
                while(ops.peek() != '(') {
                    // 计算括号中的数
                    nums.push(calculate(ops.pop(), nums.pop(), nums.pop()));
                }
                // 弹出右括号
                ops.pop();
                i++;
            } else if(s.charAt(i) == '*') {
                ops.push('*');
                i++;
            } else if(s.charAt(i) == '+' || s.charAt(i) == '-') {
                if(ops.isEmpty()) {
                    ops.push(s.charAt(i++));
                } else if(ops.peek() == '*' || ops.peek() == '-' || ops.peek() == '+') {
                    nums.push(calculate(ops.pop(), nums.pop(), nums.pop()));
                } else ops.push(s.charAt(i++));
            } else {
                // 如果不是运算符，判断是否是数字，将连续的数字字符转化为数字
                int num = 0;
                while(i < s.length() && isNum(s.charAt(i))) {
                    num = 10 * num + s.charAt(i++) - '0';
                }
                nums.push(num);
            }
        }
        int res = 0;
        // 如果运算符不为空，将所有的中间值计算
        while(!ops.isEmpty()) {
            res = res + nums.push(calculate(ops.pop(), nums.pop(), nums.pop()));
        }
        return res;
    }
    
    // 加减乘除计算
    public int calculate(char op, int b, int a) {
        if(op == '+') {
            return a + b;
        }
        if(op == '-') {
            return a - b;
        }
        if(op == '*') {
            return a * b;
        }
        return 0;
    }
    
    // 判断是否是数字
    public boolean isNum(char num) {
        if('0' <= num && num <= '9') {
            return true;
        } else {
            return false;
        }
    }
}

---

5. 两个队列实现栈

请你仅使用两个队列实现一个后入先出的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty），输入数据保证 pop、top函数操作时，栈中一定有元素。

void push(int element) 将元素 element 压入栈顶。

int pop() 移除并返回栈顶元素。

int top() 返回栈顶元素。

bool empty() 如果栈是空的，返回 true ；否则，返回 false 。

解题思路：

根据栈和队列各自的特性，栈是先进后出，队列是先进先出，用队列模拟实现栈，这里需要两个队列，q1 是主栈，q2 是辅助栈，当需要插入元素时，总是将新元素插入到空的队列中，然后再将另一个有数据的队列中的数据，取出插入到存放新元素的队列中，即可完成栈的功能。

 画图理解：

插入元素时，如果 q1 为空，就直接插入元素。

 如果 q1 不为空，将 q1 中的元素加入到 q2 中，然后在 q1 中插入新元素，再将 q2 中的元素插入到 q1 中，这样就符合栈的弹出顺序。

弹出元素时，直接弹出。

代码实现：

import java.util.*;
 
public class Solution {
    Queue queue1 = new LinkedList();
    Queue queue2 = new LinkedList();
    
    public void push(int element) {
        while(!queue1.isEmpty()) {
            queue2.add(queue1.poll());
        }
        queue1.add(element);
        while(!queue2.isEmpty()) {
            queue1.add(queue2.poll());
        }
    }
    
    public int pop() {
        return queue1.poll();
    }
    
    public int top() {
        return queue1.peek();
    }
    
    public boolean empty() {
        return queue1.isEmpty();
    }
}

活动地址：CSDN21天学习挑战赛

​