数据结构/栈实现队列

用户10788736

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

1080

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

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

前言

在学习数据结构的过程当中，我们会学到栈和队列，在本篇文章中，重点讲解的是栈实现队列，故关于栈和队列的讲解只是简单带过。

一、栈

栈是一种后进先出的线性表，即只能在固定的一端进行插入和删除。

栈方法

Stack()	构造一个空的栈
E push(E e)	将e入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

二、队列

队列是一种先进先出的线性表，即只能在一端进行插入，另一端进行删除。

队列方法

boolean offer(E e)	入队列
E poll()	出队列
E peek()	获取队头元素
int size()	获取队列中有效元素个数
boolean isEmpty()	检测队列是否为空

三、栈实现队列

结合栈和队列的简单示意图

不难发现一个栈难以实现队列，故使用两个栈演示尝试。

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

故代码如下：

class MyQueue {
    Stack<Integer> queue1;//入
    Stack<Integer> queue2;//出
    public MyQueue() {
        queue1 = new Stack<>();
        queue2 = new Stack<>();
    }

    public void push(int x) {
        queue1.push(x);
    }

    public int pop() {
        int x = 0;
        if(queue2.isEmpty()){
            while(!queue1.isEmpty()){
                queue2.push(queue1.pop());
            }
        }
        x = queue2.pop();
        return x;
    }

    public int peek() {
        int x = 0;
        if(queue2.isEmpty()){
            while(!queue1.isEmpty()){
                queue2.push(queue1.pop());
            }
        }
        x = queue2.peek();
        return x;
    }

    public boolean empty() {
        return queue1.isEmpty()&&queue2.isEmpty();
    }
}
}