数据结构/队列实现栈

2023-08-01 33

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构/队列实现栈

前言

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