双队列实现栈？双栈实现队列？

目录

双队列实现栈

最容易理解的办法

单队列实现栈

双栈实现队列

最容易理解的办法

---

双队列实现栈

如下分析（例如出栈）

注意：

• 哪个队列不为空就放入哪个将元素放入哪个队列
• 若两个都为空，任选一个队列放入即可 

如下代码：

class MyStack {
    public Queue<Integer> q1;
    public Queue<Integer> q2;
    public int usedSize;
    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    //压栈
    public void push(int x) {
        //哪个队列不为空，往那里里面放，都为空就放q1
        if(!q1.isEmpty()){
            q1.offer(x);
        }
        else if(!q2.isEmpty()){
            q2.offer(x);
        }
        else{
            q1.offer(x);
        }
        usedSize++;
    }
    //出栈
    public int pop() {
        //哪个队列不为空，就从哪里取元素放到另一个队列里
        if(empty()){
            return -1;
        }
        if(!q1.isEmpty()){
            //转移usedSize - 1个元素到另一个队列
            //for(int i = 0; i < usedSize - 1; i++)//不能这样写，usedSize会随着出栈不断减少
            int size = usedSize;
            for(int i = 0; i < size - 1; i++){
                q2.offer(q1.poll());
            }
            usedSize--;
            return q1.poll();
        }
        else{
            int size = usedSize;
            for(int i = 0; i < size - 1; i++){
                q1.offer(q2.poll());
            }
            usedSize--;
            return q2.poll();
        }
    }
    
    public int top() {
        //哪个队列不为空，就从哪里取元素放到另一个队列里
        if(empty()){
            return -1;
        }
        int tmp = 0;
        if(!q1.isEmpty()){
            int size = usedSize;
            for(int i = 0; i < size - 1; i++){
                q2.offer(q1.poll());
            }
            tmp = q1.peek();
            q2.offer(q1.poll());
        }
        else{
            int size = usedSize;
            for(int i = 0; i < size - 1; i++){
                q1.offer(q2.poll());
            }
            tmp = q2.peek();
            q1.offer(q2.poll());
        }
        return tmp;
    }
    //判空
    public boolean empty() {
        return usedSize == 0;
    }
}

最容易理解的办法

画个图就清楚啦~

class MyStack {
 
    private Queue<Integer> queue1 = new LinkedList<>(); 
    private Queue<Integer> queue2 = new LinkedList<>(); 
 
    public MyStack() {
        
    }
    
    public void push(int x) {
        while(!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        queue1.offer(x);
        while(!queue2.isEmpty()) {
            queue1.offer(queue2.poll());
        }
    }
    
    public int pop() {
        return queue1.poll();
    }
    
    public int top() {
        return queue1.peek();
    }
    
    public boolean empty() {
        return queue1.isEmpty();
    }
}

单队列实现栈

实际上，单个队列也可以实现栈，每次入栈前都需要看一下栈里有多少个元素，然后先把需要入栈的元素入栈后，按顺序弹出之前记录的元素个数，就可以维持一个栈结构了.

    class MyStack {
 
        private Queue<Integer> queue;
 
        public MyStack() {
            this.queue = new LinkedList<>();
        }
 
        public void push(int x) {
            queue.offer(x);
            for(int i = 0; i < queue.size() - 1; i++) {
                queue.offer(queue.poll());
            }
        }
 
        public int pop() {
            return queue.poll();
        }
 
        public int top() {
            return queue.peek();
        }
 
        public boolean empty() {
            return queue.isEmpty();
        }
    }

---

双栈实现队列

单个栈是无法实现队列的，双栈是可以的，如下分析（例如出队）

 注意：

• 出队之前一定要先检查s2中是否有元素，若有直接弹出即可，若没有再将s1全部压入s2中
• 检查队列首元素也是如此(peek)

代码如下：

class MyQueue {
    public Stack<Integer> s1;//入栈
    public Stack<Integer> s2;//出栈
    public MyQueue() {
        this.s1 = new Stack<>();
        this.s2 = new Stack<>();
    }
    //进队
    public void push(int x) {
        s1.push(x);
    }
    //出队
    public int pop() {
        if(empty()) {
            return -1;
        }
        //s2如同蓄水池，一旦要出队列，就全压s1
        //前提一定要是s2为空！若不为空，再压入s2，顺序就不一样！
        if(s2.empty()){
            while(!s1.empty()) {
                s2.push(s1.pop());
            }
            return s2.pop();
        }
        //如果s2里有元素，就直接弹出
        return s2.pop();
    }
    public int peek() {
        if(empty()) {
            return -1;
        }
        //s2如同蓄水池，一旦要出队列，就全压s1
        //前提一定要是s2为空！若不为空，再压入s2，顺序就不一样！
        if(s2.empty()){
            while(!s1.empty()) {
                s2.push(s1.pop());
            }
            return s2.peek();
        }
        //如果s2里有元素，就直接弹出
        return s2.peek();
    }
    
    public boolean empty() {
        return s1.empty() && s2.empty();
    }
}

最容易理解的办法

画个图就知道了~

class MyQueue {
 
    private Stack<Integer> stack1 = new Stack<>();
    private Stack<Integer> stack2 = new Stack<>();
 
    public MyQueue() {
        
    }
    
    public void push(int x) {
        while(!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        stack1.push(x);
        while(!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
    }
    
    public int pop() {
        return stack1.pop();
    }
    
    public int peek() {
        return stack1.peek();
    }
    
    public boolean empty() {
        return stack1.isEmpty();
    }
}

---