【算法】使用队列制作一个栈-蒲公英云

【算法】使用队列制作一个栈

文章目录

前言
两个队列形成一个栈
一个队列形成一个栈

前言

栈是一种后进先出的数据结构，元素从顶端入栈，然后从顶端出栈。

队列是一种先进先出的数据结构，元素从后端入队，然后从前端出队。

方法一：两个队列
为了满足栈的特性，即最后入栈的元素最先出栈，在使用队列实现栈时，应满足队列前端的元素是最后入栈的元素。可以使用两个队列实现栈的操作，其中pushQueue用于存储栈内的元素，popQueue作为入栈操作的辅助队列。

入栈操作时，首先将元素入队到 pushQueue ，然后将 popQueue的全部元素依次出队并入队到
pushQueue，此时pushQueue 的前端的元素即为新入栈的元素，再将 pushQueue和 popQueue互换，则popQueue的元素即为栈内的元素，popQueue的前端和后端分别对应栈顶和栈底。
由于每次入栈操作都确保popQueue的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除 popQueue的前端元素并返回即可，获得栈顶元素操作只需要获得popQueue的前端元素并返回即可（不移除元素）。
由于 popQueue用于存储栈内的元素，判断栈是否为空时，只需要判断popQueue是否为空即可。

两个队列形成一个栈

package com.base.learn.queue;
import java.util.LinkedList;
import java.util.Queue;
/**
 * @author: 张锦标
 * @date: 2023/6/10 10:33
 * QueueMakeStack类
 */
public class TwoQueueMakeStack {
    //每次最新元素都插入到pushQueue中
    private Queue<Integer> pushQueue;
    //出栈的时候使用这个popQueue，用于存放老旧元素
    private Queue<Integer> popQueue;
    public TwoQueueMakeStack() {
        pushQueue = new LinkedList<Integer>();
        popQueue = new LinkedList<Integer>();
    }
    public void push(int x) {
        //pushQueue.offer(x);
        //while(!popQueue.isEmpty()){
        //    pushQueue.offer(popQueue.poll());
        //}
        //Queue<Integer> temp = popQueue;
        //popQueue = pushQueue;
        //pushQueue = temp;
        //一个队列也可以实现栈
        int size = popQueue.size();
        popQueue.offer(x);
        for(int i=0;i<size;i++){
            popQueue.offer(popQueue.poll());
        }
    }
    public int pop() {
        return popQueue.poll();
    }
    public int top() {
        return popQueue.peek();
    }
    public boolean empty() {
        return popQueue.isEmpty();
    }
}

一个队列形成一个栈

方法一使用了两个队列实现栈的操作，也可以使用一个队列实现栈的操作。

使用一个队列时，为了满足栈的特性，即最后入栈的元素最先出栈，同样需要满足队列前端的元素是最后入栈的元素。

入栈操作时，首先获得入栈前的元素个数 n，然后将元素入队到队列，再将队列中的前
n 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底。

由于每次入栈操作都确保队列的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除队列的前端元素并返回即可，获得栈顶元素操作只需要获得队列的前端元素并返回即可（不移除元素）。

由于队列用于存储栈内的元素，判断栈是否为空时，只需要判断队列是否为空即可。

package com.base.learn.queue;
import java.util.LinkedList;
import java.util.Queue;
/**
 * @author: 张锦标
 * @date: 2023/6/10 10:44
 * OneQueueMakeStack类
 */
public class OneQueueMakeStack {
    private Queue<Integer> queue ;
    public OneQueueMakeStack(){
        queue = new LinkedList<Integer>();
    }
    public void push(int x){
        int size = queue.size();
        queue.offer(x);
        for(int i=0;i<size;i++){
            queue.offer(queue.poll());
        }
    }
    public int pop(){
        return queue.poll();
    }
    public int top(){
        return queue.peek();
    }
    public boolean empty(){
        return queue.isEmpty();
    }
}