【数据结构面试题】栈与队列的相互实现

目录

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();}
}

---

以上为我个人的小分享，如有问题，欢迎讨论！！！ 

都看到这了，不如关注一下，给个免费的赞