档案网站 内容建设上海推广seo
目录
1.队列实现栈
1.1创建栈
1.2判断是否为空
1.3入栈
1.4出栈
1.5获取栈顶元素
1.6完整代码
2. 用栈实现队列
2.1创建队列
2.2判断是否为空
2.3入队列
2.4出队列
2.5获取队头元素
2.6完整代码
1.队列实现栈
用队列实现栈
https://leetcode.cn/problems/implement-stack-using-queues/
描述：
方法：我们用两个队列来实现栈
整体思路：
1.1创建栈
代码：
public class MyStack {private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack(){qu1=new LinkedList<>();qu2=new LinkedList<>();}}1.2判断是否为空
只要qu1与qu2都为null时，栈就为空
代码：
public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}1.3入栈
（1）我们对两个队列进行检查，那个队列不为空，我们就把元素放在那个队里
（2）若元素都为空，则我们把元素放在qu1里
代码：
public void push(int x) {if (!qu1.isEmpty()) {qu1.offer(x);} else if (!qu2.isEmpty()) {qu2.offer(x);} else {qu1.offer(x);}}1.4出栈
（1）我们对两个队列进行检查，若都为空，返回-1。
（2）只要不是（1）则先检查qu1,再先检查qu2，将不为空的队列出size-1个元素到另一个队列里
代码：
public int pop() {if (empty()) {return -1;}if(!qu1.isEmpty()){int size=qu1.size() ;for (int i = 0; i <size-1; i++) {int val=qu1.poll();qu2.offer(val);}return qu1.poll();} else {int size=qu2.size() ;for (int i = 0; i <size-1; i++) {int val=qu2.poll();qu1.offer(val);}return qu2.poll();}}1.5获取栈顶元素
与出栈方法类似
public int top() {if (empty()) {return -1;}if(!qu1.isEmpty()){int val=-1;int size=qu1.size() ;for (int i = 0; i <size; i++) {val=qu1.poll();qu2.offer(val);}return val;} else {int val=-1;int size=qu2.size() ;for (int i = 0; i <size; i++) {val=qu2.poll();qu1.offer(val);}return val;}}1.6完整代码
import java.util.LinkedList;
import java.util.Queue;public class MyStack {private Queue<Integer> qu1;private 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++) {int val=qu1.poll();qu2.offer(val);}return qu1.poll();} else {int size=qu2.size() ;for (int i = 0; i <size-1; i++) {int val=qu2.poll();qu1.offer(val);}return qu2.poll();}}public int top() {if (empty()) {return -1;}if(!qu1.isEmpty()){int val=-1;int size=qu1.size() ;for (int i = 0; i <size; i++) {val=qu1.poll();qu2.offer(val);}return val;} else {int val=-1;int size=qu2.size() ;for (int i = 0; i <size; i++) {val=qu2.poll();qu1.offer(val);}return val;}}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}
2. 用栈实现队列
描述：
用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/
方法：两个栈来实现队列
2.1创建队列
public class MyQueue {private Stack<Integer> stack1;private Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}
}2.2判断是否为空
只要stack1与stack2都为null时，队列就为空
public boolean empty() {return stack1.empty()&&stack2.empty();}2.3入队列
入栈的元素全部放入stack1中
public void push(int x) {stack1.push(x);}2.4出队列
出栈时，检查stack2是否为null，若为null，则直接将stack1的元素出栈后入到stack2里
然后弹出栈顶元素即可
public int pop() {if (empty()){return -1;}if(stack2.empty()){while(!stack1.empty()) {stack2.push(stack1.pop());}}return stack2.pop();}2.5获取队头元素
public int peek() {if (empty()){return -1;}if(stack2.empty()){while(!stack1.empty()) {stack2.push(stack1.pop());}}return stack2.peek();}2.6完整代码
import java.util.Stack;public class MyQueue {private Stack<Integer> stack1;private Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack1.push(x);}public int pop() {if (empty()){return -1;}if(stack2.empty()){while(!stack1.empty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if (empty()){return -1;}if(stack2.empty()){while(!stack1.empty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.empty() && stack2.empty();}
}
以上为我个人的小分享，如有问题，欢迎讨论！！！
都看到这了，不如关注一下，给个免费的赞 
