【Java--数据结构】队列与栈的相互成就

欢迎关注个人主页：逸狼

---

创造不易，可以点点赞吗~

如有错误，欢迎指出~

---

---

目录

 用队列实现栈

用栈实现队列

---

 用队列实现栈

oj链接

一个队列是无法实现栈的

入栈push：把数据放到不为空的队列当中。

注意：第一次入栈时，两个队列都为空，规定放到第一个队列中。 

出栈pop：把一个队列的n-1个元素放到另一个队列中，此时第一个队列中的元素就是要出栈的元素

判空empty：两个队列同时为空时为空。

获取栈顶元素top:与出栈类似，将队列中n个元素放到另一个中，并且用ret接收每一个元素的值（会覆盖前一个值），直到队列为空时，最后一个ret的值为栈顶元素。

top示意图： 

import java.util.LinkedList;
import java.util.Queue;
class MyStackUsQueue {
    public Queue queue1;
    public Queue queue2;
    public MyStackUsQueue() {
        queue1=new LinkedList();
        queue2=new LinkedList();
    }
    //入栈
    public void push(int x) {
        if (empty()){
            queue1.offer(x);
            return;
        }
        if (!queue1.isEmpty()){
            queue1.offer(x);
        }else{
            queue2.offer(x);
        }
    }
    //出栈
    public int pop() {
        if (empty()) {
            return -1;
        }
            if(!queue1.isEmpty()){
                int size=queue1.size();
                for (int i = 0; i  
用栈实现队列
 
oj链接
 
 
 
入队列：直接放到s1栈中。 
 
出队列：
 
入栈，放到s1栈中
出栈，把s1中所有元素全部放入s2栈中，将s2的元素出栈
如果s2里面是空的，就要把s1中的元素放入s2。
import java.util.Stack;
class MyQueueUsStack {
    public Stack stack1;
    public Stack stack2;
    public MyQueueUsStack() {
        stack1=new Stack();
        stack2=new Stack();
    }
    
    public void push(int x) {
        stack1.push(x);
    }
    
    public int pop() {
        if (empty()){//队列为空
            return -1;
        }
        //走到这里，说明s1中一定有元素
        if(stack2.empty()){
            while(!stack1.empty()){//将s1中的所有元素放入s2中
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
    
    public int peek() {
        if (empty()){//队列为空
            return -1;
        }
        //走到这里，说明s1中一定有元素
        if(stack2.empty()){
            while(!stack1.empty()){//将s1中的所有元素放入s2中
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
    
    public boolean empty() {
        return stack1.empty()&&stack2.empty();
    }
}