数据结构/队列实现栈-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构/队列实现栈。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

在学习数据结构的过程当中，我们会学到栈和队列，在本篇文章中，重点讲解的是队列实现栈，在上篇文章中已经简单介绍过栈和队列的使用说明，以及栈实现队列。(2条消息) 数据结构/栈实现队列_Y君的进化史的博客-CSDN博客

队列实现栈

关于一个队列的简单使用方式：

数据结构/队列实现栈

关于一个栈的简单使用方式：

数据结构/队列实现栈

很显然一个队列无法实现栈，我们使用两个队列：

数据结构/队列实现栈

此时思路依旧很难被想到，我们跌倒一个队列试试：

数据结构/队列实现栈

我们可以发现，使用一个队列入栈，另一个出栈可以实现我们的想法。

例如：

数据结构/队列实现栈

当第一个队列全部往第二个队列中输入时，最后一个元素即为出栈的第一个元素；当需要第二个出栈的元素时，再将不为空的队列往另一个空队列输入元素，末尾元素即为出栈元素；几次往返即可实现栈。

代码：

import java.util.LinkedList;
import java.util.Queue;


class MyStack {

    Queue<Integer> stack1;
    Queue<Integer> stack2;

    public MyStack() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();

    }

    public void push(int x) {
        if(!stack1.isEmpty()){
            stack1.offer(x);
        }else{
            stack2.offer(x);
        }
    }

    public int pop() {
        int x = 0;
        if(!stack1.isEmpty()){
            x = stack1.poll();
            while(!stack1.isEmpty()){
                stack2.offer(x);
                x = stack1.poll();
            }
        }else if(!stack2.isEmpty()){
            x = stack2.poll();
            while(!stack2.isEmpty()){
                stack1.offer(x);
                x = stack2.poll();
            }
        }
        return x;
    }

    public int top() {
        int x = 0;
        if(!stack1.isEmpty()){
            x = stack1.poll();
            while(!stack1.isEmpty()){
                stack2.offer(x);
                x = stack1.poll();
            }
            stack2.offer(x);
        }else if(!stack2.isEmpty()){
            x = stack2.poll();
            while(!stack2.isEmpty()){
                stack1.offer(x);
                x = stack2.poll();
            }
            stack1.offer(x);
        }
        return x;
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}