计算机系统应用教程网站

网站首页 > 技术文章 正文

力扣算法题-如何使用两个栈来实现一个FIFO的队列?

btikc 2024-10-20 04:59:46 技术文章 5 ℃ 0 评论

如何使用两个栈操作来模拟出先进先出的队列呢?可以按照如下的思路来进行分析。

分析思路

创建两个栈

首先需要创建两个栈Stack1和Stack2,其中Stack1主要用来管理入队操作,而Stack2则是用来模拟出队操作。

入队操作模拟

入队操作用栈来模拟其实就是压栈的操作,使用push方法。

出队操作模拟

出队操作需要对Stack2进行判空,如果Stack2不为空的时候,需要从Stack2中取出相应的元素,那么如果Stack2为空,那么根据先进先出的原则,需要将Stack1中的所有元素都按照相反的顺序依次的进入到Stack2中。

这样做的目的就是将Stack1中的元素全部逆序的添加到Stack2中,这样就可以保证先进先出的操作。如果中途有数据进入的话那么按照之前的上面的操作,此时Stack1中的元素已经是空的了,可以直接按照入栈的方式进入。

查看队首元素

根据上面的分析如果Stack2不为空的情况下,按照顺序应该依次的取出Stack2中的元素,如果Stack2为空,需要将Stack1中的元素依次进行添加。

检查队列是否满了

根据上面的分析,队列满了如何进行判断?因为在入栈的时候,按照Stack1的长度,其实就可以看做是队列的长度,如果Stack1满了之后,那么就可以判断队列满了,这个时候如果有数据继续进入的话,就需要设置拒绝策略了。

检查队列是否为空

如果Stack1和Stack2都为空,那么就表示队列为空,反之,则队列不为空。

具体实现

在Java中,可以通过Stack来直接进行模拟,代码如下所示。

模拟队列操作

import java.util.Stack;  
  
public class MyQueue<T> {  
    private Stack<T> stack1; // 用于入队操作  
    private Stack<T> stack2; // 用于出队操作  
  
    public MyQueue() {  
        stack1 = new Stack<>();  
        stack2 = new Stack<>();  
    }  
  
    // 入队操作  
    public void push(T item) {  
        stack1.push(item);  
    }  
  
    // 出队操作  
    public T pop() {  
        // 如果stack2为空,则将stack1中的元素转移到stack2  
        if (stack2.isEmpty()) {  
            while (!stack1.isEmpty()) {  
                stack2.push(stack1.pop());  
            }  
        }  
        // 此时stack2的栈顶元素即为最早入队的元素,执行出队操作  
        return stack2.pop();  
    }  
  
    // 查看队首元素  
    public T peek() {  
        // 如果stack2为空,则将stack1中的元素转移到stack2  
        if (stack2.isEmpty()) {  
            while (!stack1.isEmpty()) {  
                stack2.push(stack1.pop());  
            }  
        }  
        // 返回stack2的栈顶元素,不进行出队操作  
        return stack2.peek();  
    }  
  
    // 检查队列是否为空  
    public boolean empty() {  
        return stack1.isEmpty() && stack2.isEmpty();  
    } 
}

测试出入队操作

// 测试代码  
public static void main(String[] args) {  
    MyQueue<Integer> queue = new MyQueue<>();  

    // 入队操作  
    queue.push(1);  
    queue.push(2);  
    queue.push(3);  

    // 查看队首元素  
    System.out.println("Peek: " + queue.peek()); // 输出:Peek: 1  

    // 出队操作  
    System.out.println("Pop: " + queue.pop()); // 输出:Pop: 1  
    System.out.println("Pop: " + queue.pop()); // 输出:Pop: 2  

    // 检查队列是否为空  
    System.out.println("Empty: " + queue.empty()); // 输出:Empty: false  

    // 继续出队操作  
    System.out.println("Pop: " + queue.pop()); // 输出:Pop: 3  

    // 再次检查队列是否为空  
    System.out.println("Empty: " + queue.empty()); // 输出:Empty: true  
}  

总结

利用栈来模拟队列,属于是面试中的基础操作,主要考察的是面试者对于栈和队列两种数据结构的理解。通过栈的先进后出操作,来模拟出队列了先进先出操作,同时需要判断队列是否满了。队列是否为空等操作。

本文暂时没有评论,来添加一个吧(●'◡'●)

欢迎 发表评论:

最近发表
标签列表