【数据结构】栈和队列相互实现
目录
栈实现队列
思路
栈的特点是 先进后出， 队列的特点是 先进新出，这就意味着我们无法通过一个栈来实现队列，那两个栈呢？
事实上，两个栈是可以实现队列的，stack1和stack2 思路如下：
入队列：先把所有元素都放到stack1中。
出队列：判断stack2是否为空
- 为空则把stack1中元素按照出栈顺序放到stack2中，同时返回stack2栈顶元素。
- 不为空则直接返回stack2栈顶元素。
定义基础变量
class MyQueue { public ArrayDeque<Integer> stack1; public ArrayDeque<Integer> stack2; public MyQueue() { stack1 = new ArrayDeque<>(); stack2 = new ArrayDeque<>(); } }入队列
offer方法
根据上面思路，新元素放在stack1中。
public void offer(int x) { stack1.push(x); } 出队列
poll方法
在实现具体内容之前，我们要先判断两个栈是否都为空。
这里需要写个empty方法，判断条件是：两个栈是否为空。
public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); }根据上面的思路，来完成出队列。
出队列：判断stack2是否为空为空则把stack1中元素按照出栈顺序放到stack2中，同时返回stack2栈顶元素不为空则直接返回stack2栈顶元素。
public int poll() { if(empty()){ return -1; } if(stack2.isEmpty()){ while(!stack1.isEmpty()){ //第一个栈的所有元素 放到第二个栈当中 stack2.push(stack1.pop()); } } return stack2.pop(); }获取队头元素
peek方法
思路和pop方法一样，不过返回的是stack2.peek();
public int peek() { if(empty()){ return -1; } if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.peek(); }
队列实现栈
思路
这里也是用两个队列实现栈，分别为qu1和qu2。
入栈：把元素放到不为空的队列中。如果都为空，放在qu1中。
出栈：把 不为空的队列 中的 size-1个元素放到另一个队列当中，最后剩下的元素模拟出栈。
定义基础变量
class MyStack { public Queue<Integer> qu1; public Queue<Integer> qu2; public MyStack() { this.qu1 = new LinkedList<>(); this.qu2 = new LinkedList<>(); } }入栈
push方法
根据上面的思路：把元素放到不为空的队列中。如果都为空，放在qu1中。
//入栈 public void push(int x) { if(!qu1.isEmpty()){ qu1.offer(x); }else if(!qu2.isEmpty()){ qu2.offer(x); }else{ qu1.offer(x); } }出栈
pop方法
根据上面的思路：把 不为空的队列 中的 size-1个元素放到另一个队列当中，最后剩下的元素模拟出栈。
同时还要考虑两个队列是否都为空，都为空将无法向下进行。所以可以写个empty方法来判断。
public boolean empty() { return qu1.isEmpty() && qu2.isEmpty(); }pop方法完整如下：
//出栈 public int pop() { if(empty()){ return -1; } if(qu1.isEmpty()){ int size = qu2.size(); for(int i = 0; i < size - 1; i++){ qu1.offer(qu2.poll()); } return qu2.poll(); }else{ int size = qu1.size(); for(int i = 0; i < size - 1; i++){ qu2.offer(qu1.poll()); } return qu1.poll(); } } 获取栈顶元素
peek方法
获取栈顶元素和pop方法的思路相似， 不过这里不需要删除栈顶元素，而是把size给元素全部放到另一个队列中，同时需要定义一个中间值 val 来记录数据。
//获取栈顶元素 public int top() { if(empty()){ return -1; } if(!qu1.isEmpty()){ int size = qu1.size(); int val = 0; for(int i = 0; i < size; i++){ val = qu1.poll(); qu2.offer(val); } return val; }else { int size = qu2.size(); int val = 0; for(int i = 0; i < size; i++){ val = qu2.poll(); qu1.offer(val); } return val; } }完整代码
栈实现队列
class MyQueue { public ArrayDeque<Integer> stack1; public ArrayDeque<Integer> stack2; public MyQueue() { stack1 = new ArrayDeque<>(); stack2 = new ArrayDeque<>(); } public void offer(int x) { stack1.push(x); } public int poll() { if(empty()){ return -1; } if(stack2.isEmpty()){ while(!stack1.isEmpty()){ //第一个栈的所有元素 放到第二个栈当中 stack2.push(stack1.pop()); } } return stack2.pop(); } public int peek() { if(empty()){ return -1; } if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.peek(); } public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); } } 队列实现栈
class MyStack { public 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++){ qu2.offer(qu1.poll()); } return qu1.poll(); }else { int size = qu2.size(); for(int i = 0; i < size-1; i++){ qu1.offer(qu2.poll()); } return qu2.poll(); } } //在队列里面找中间值 存放移动的数据 public int peek() { if(empty()){ return -1; } if(!qu1.isEmpty()){ int size = qu1.size(); int val = 0; for(int i = 0; i < size; i++){ val = qu1.poll(); qu2.offer(val); } return val; }else { int size = qu2.size(); int val = 0; for(int i = 0; i < size; i++){ val = qu2.poll(); qu1.offer(val); } return val; } } public boolean empty() { return qu1.isEmpty() && qu2.isEmpty(); } } 
