数据结构：栈(Stack)和队列(Queue)—面试题（二）

1. 用队列实现栈。

习题链接https://leetcode.cn/problems/implement-stack-using-queues/description/描述：

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

根据题意，他要我们用两个队列来实现一个栈，我们知道栈和队列的出数据的方式是不同的，栈是后进先出，队列是先进后出，那么我们该如何用两个队列实现后进先出呢？

 

我们知道当这两个队列都为空是，所代表我们要创建的栈也为空。

我们要进行入栈时，如果我们的栈为空。就将数据放到队列1中，如果栈不为空，代表两个队列都都不为空或者有一个队列不为空，此时是队列1不为空，将数据放入队列1中，如果是队列2不为空，将数据放入队列2中

我们要进行出栈时，如果栈为空不能出数据，如果栈不为空，我们知道队列是先进先出，而栈是先进后出，此时要出的数据应该是我们队列的最后一个数据才是，因此我们可以将我们队列不为空的数据除最后一个数据外全部弹出放入到此时为空的队列当中，并让剩最后一个数的队列将最后一个数弹出，此时弹出的数就是我们栈要出的数据。

我们要获得栈顶元素时，我们可以像出栈方式一样，最后我们让最后一位数据进行队列的查找即可，这样就没有删除最后一个元素，但是这种方式是有问题的，我们发现如果我们将除最后一个元素都放到另一个队列当中了，而最后一个元素依然在另一个队列，但是，栈的查找是不改变数据的形式的，如果我们还用这种方式就改变了他的形式，因此我们可以创建一个变量，将一个队列的所有元素都经过这个变量，然后在将这个变量的值放到另一个队列中，这时我们变量的最后一个值就是我们要查找的栈顶元素

完整代码 

class MyStack {

    Queue<Integer> que1;
    Queue<Integer> que2;

    public MyStack() {
        que1 = new LinkedList<>();
        que2 = new LinkedList<>();
    }
    
    public void push(int x) {
        if(empty()){
            que1.offer(x);
            return;
        }

        if(!que1.isEmpty()){
            que1.offer(x);
        }else{
            que2.offer(x);
        }
    }
    
    public int pop() {
        if(empty()){
            return -1;
        }
        if(!que1.isEmpty()){
            int count = que1.size();
            while(count-1 != 0){
                que2.offer(que1.poll());
                count--;
            }
            return que1.poll();
        }else{
            int count = que2.size();
            while(count-1 != 0){
                que1.offer(que2.poll());
                count--;
            }
             return que2.poll();
        }
        
    }
    
    public int top() {
        if(empty()){
            return -1;
        }
        if(!que1.isEmpty()){
            int count = que1.size();
            int tmp = -1;
            while(count != 0){
                tmp = que1.poll();
                que2.offer(tmp);
                count--;
            }
            return tmp;
        }else{
            int count = que2.size();
            int tmp = -1;
            while(count != 0){
                tmp = que2.poll();
                que1.offer(tmp);
                count--;
            }
            return tmp;
        }
        
    }
    
    public boolean empty() {
        return que1.isEmpty() && que2.isEmpty();
    }
}

2. 用栈实现队列。

描述：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

根据题意，他要我们用两个栈实现一个队列，这会我们要用两个栈实现一个先进先出的队列

我们知道当这两个栈都为空是，所代表我们要创建的队列也为空。

我们要进行入队列时，我们让栈1专门作为入数据的栈.

我们要进行出队列时，如果队列为空，就不能删除，如何不为空，同时栈2为空我们就将栈1的所有数据都放到栈2中，由于栈是后进先出，这就让栈的数据都颠倒了过来，这时我们再让栈2出栈，此时出栈的次序就是我们队列的出数据顺序

我们要进行查找队头元素时，我们还是出队的方法，最后让栈进行栈顶元素的查找即可，因为我们上述的出队方式并没有改变数据的形式没有 

完整代码 

class MyQueue {

    Stack<Integer> stack1;
    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.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();
    }
}

好了今天的分享就到这里了，还请大家多多关注，我们下一篇见！