数据结构/队列实现栈

用户10788736

发布于 2023-10-16 08:32:45

1290

发布于 2023-10-16 08:32:45

文章被收录于专栏：CSDN搬移文章

前言

在学习数据结构的过程当中，我们会学到栈和队列，在本篇文章中，重点讲解的是队列实现栈，在上篇文章中已经简单介绍过栈和队列的使用说明，以及栈实现队列。(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();
    }
}