1. 用队列实现栈
题目解析:
题目链接:. - 力扣（LeetCode）
我们需要俩个队列来实现栈的入栈和出栈操作;
首先我们创建俩个队列qu1和qu2并且我们生成相应的构造方法;
解题步骤:
1. 哪个队列不为空,我就把元素放到哪个队列里面去(如果俩个都是空的,那就指定放到第一个里面去)
2. 出栈的时候,哪个不为空,我们就往这个队列放size - 1个元素
3. 当俩个队列都为空的时候,我们模拟的栈就是空的
及具体代码:
class MyStack {//先生成俩个队列private Queue<Integer> qu1;public Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}public void push(int x) {if(!qu1.isEmpty()) {qu1.offer(x);}else if(!qu2.isEmpty()) {qu2.offer(x);}else {//俩个队列都是空的 指定存放到第一个队列当中qu1.offer(x);}}public int pop() {if(empty()) {return -1;}if(!qu1.isEmpty()) {int size = qu1.size();for (int i = 0; i < size - 1; i++) {//qu1.size()是一个变量,每次循环一次它都会变化//从队列1把元素取出来int x = qu1.poll();//放到que2里面去qu2.offer(x);}//返回qu1里面剩下的元素return qu1.poll();}else {int size = qu2.size();for (int i = 0; i < size - 1; i++) {//从队列2把元素取出来int x = qu2.poll();//放到que1里面去qu2.offer(x);}//返回qu2里面剩下的元素return qu2.poll();}}
//TODO 获取栈顶元素public int top() {if(empty()) {return -1;}if(!qu1.isEmpty()) {int size = qu1.size();int x = -1;for (int i = 0; i < size; i++) {//qu1.size()是一个变量,每次循环一次它都会变化//从队列1把元素取出来x = qu1.poll();//放到que2里面去qu2.offer(x);}//返回qu1里面最后一个元素return x;}else {int size = qu2.size();int x = -1;for (int i = 0; i < size; i++) {//从队列2把元素取出来x = qu2.poll();//放到que1里面去qu2.offer(x);}//返回qu2里面剩下的元素return x;}}public boolean empty() {//俩个队列同时为空的时候 说明模拟实现的栈是空的return qu2.isEmpty() && qu1.isEmpty();}
}2. 用栈实现队列
题目解析:
题目链接:. - 力扣（LeetCode）
我们需要俩个栈来实现队列的入队和出队操作;
首先我们先创建俩个栈:s1,s2,并且创建一个构造方法,生成俩个栈
解题的话分别分为以下俩个步骤:
1. 入队的时候,全部放在第一个栈里面
也就是s1.push(要放入的元素)
2. 出队的时候 我们在第二个栈里面出队,当第二个栈里面没有元素的时候,把第一个栈里面的元素全部放进来
其他方法介绍:
判断队空 empty()
我们只有当s1和s2没有元素的时候才是队空.
观察队头元素
我们直接在pop的基础上返回s2的栈顶元素即可
具体代码:
class MyQueue {//设置俩个栈//1. 入队的时候放在第一个栈里面//2. 出队的时候放在第二个栈里面,当第二个栈里面没有元素的时候.把第一个栈里面的元素全部移过来private Stack<Integer> s1;private Stack<Integer> s2;public MyQueue() {s1 = new Stack<>();s2 = new Stack<>();}public void push(int x) {//我们先把元素都放在第一个栈里面s1.push(x);}public int pop() {if(empty()) {return -1;}//如果不为空,我们先把s1所有的元素放到s2中去if (s2.empty()) {while (!s1.empty()){int tmp = s1.pop();s2.push(tmp);}}//然后我们就返回s2的栈顶元素return s2.pop();}public int peek() {if(empty()) {return -1;}//如果不为空,我们先把s1所有的元素放到s2中去if (s2.empty()) {while (!s1.empty()){int tmp = s1.pop();s2.push(tmp);}}//然后我们就返回s2的栈顶元素return s2.peek();}
//俩个栈同时为空才是队空public boolean empty() {return s1.empty() && s2.empty();}
}
