教你用栈实现队列怎么写 |
您所在的位置：网站首页 › 变量该怎么写 › 教你用栈实现队列怎么写 |
教你用栈实现队列怎么写
|
大家好，我是三叔，很高兴这期又和大家见面了，一个奋斗在互联网的打工人。 队列（Queue）和栈（Stack）是两个基本的数据结构。队列是一种先进先出（First-In-First-Out, FIFO）的数据结构，而栈是一种后进先出（Last-In-First-Out, LIFO）的数据结构。有时候，我们需要使用栈来实现队列的功能，即将栈转化为队列。在本篇博客中，笔者将介绍如何使用栈实现队列，并给出相应的Java代码示例。 队列先进先出，很好理解，栈的话是先入后出的结构，如果用栈实现队列，就要使用两个栈，将入栈的元素取出来放进另一个栈中，这样先进去的元素也能先出来。 实现原理： 要使用栈实现队列，我们可以借助两个栈来实现。一个栈用于存储入队的元素，另一个栈用于存储出队的元素。当需要执行入队操作时，将元素压入入队栈中。当需要执行出队操作时，首先检查出队栈是否为空，如果不为空，则直接从出队栈中弹出元素；如果为空，则将入队栈的元素逐个弹出并压入出队栈中，然后再从出队栈中弹出元素。这样，就可以实现队列的先进先出特性。 队列如图所示：放入元素依次是 1 2 3 4 … 如果弹出来，依次是：1 2 3 4 … 上代码！ class MyQueue {// 用栈实现队列 // 由于栈是先进的后出来，队列是先进的先出，所以这里需要用两个栈来模拟一个进栈，一个出栈 Stack stackIn; Stack stackOut; public MyQueue() { stackIn = new Stack(); stackOut = new Stack(); } // 模拟队列，push向队尾放元素 public void push(int x) { stackIn.push(x); } // 取元素，把所有的入栈元素取出来放进出栈中，模拟队列先进先出 public int pop() { changePlace();// 改变了入栈的顺序 return stackOut.pop(); } // 返回队列开头的元素 public int peek() { // 确定是不是出栈的元素，如果为空，或者入栈还有元素，进行处理，再调用changePlace() 改变顺序 changePlace(); return stackOut.peek(); // 现在返回的就是队列的第一个元素 } // peek()方法还可以这么写： /* public int peek() { int result = this.pop(); // 调用pop弹出元素 stackOut.push(result);// 然后再放回去 return result;// 返回弹出的元素，这样也可以保证只是查看第一个元素 } */ public boolean empty() { // 判断出栈 和 入栈的元素都为空，才是真的为空 return stackIn.isEmpty() && stackOut.isEmpty(); } // 改变出栈和入栈的位置，如果出栈有元素，直接返回，如果出栈为空，再把入栈元素放进出栈，避免出栈还有数据的时候，把入栈放进去，位置变乱 private void changePlace() { if(!stackOut.isEmpty()) { return ; } // 取出入栈的元素放进出栈，这样出栈的元素就能正确让先入栈的元素按先入先出的顺序出来 while(!stackIn.isEmpty()) { // 入栈弹出的元素：stackIn.pop stackOut.push(stackIn.pop()); } } } /** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */ 最后在这个构造方法中，我们创建了两个Stack类型的对象：stackIn和stackOut。通过调用new Stack()来实例化这两个栈对象。stackIn = new Stack()的作用是将新创建的Stack对象分配给stackIn变量，以便在整个类的范围内都可以使用该变量引用栈对象。这样，在创建MyQueue类的对象时，构造方法将会被调用，并且stackIn和stackOut栈对象将被初始化为空栈。通过这样的构造方法，我们为MyQueue类的实例提供了初始状态，并确保在使用栈对象之前它们已经被实例化。 将 new Stack() 放在构造方法内部的好处是，它可以确保每个 MyQueue 对象都有自己的独立的 stackIn 和 stackOut 实例。这样，即使创建多个 MyQueue 对象，它们之间的栈对象不会共享，每个对象都有自己独立的栈用于存储数据。 如果将 new Stack() 放在类的成员变量声明处（即放在外面），这意味着所有的 MyQueue 对象将共享同一个 Stack 对象，而不是每个对象都有自己的独立实例。这可能导致在并发环境中出现问题，因为多个对象之间共享同一个栈可能会导致数据混乱或错误的行为。 因此，为了确保每个 MyQueue 对象都有自己独立的栈对象，一般会将 new Stack() 放在构造方法内部，这样每个对象都有自己的栈实例来存储数据。这样做可以保证对象之间的隔离性和数据的正确性。 |
那么如果用栈来实现队列，则需要两个，如图所示： 将第一个栈的元素依次弹出来放进另一个栈中，这样，另一个栈中取出来的元素就和队列的顺序一模一样了，切记：入栈的所有元素要一次性全部取出，这样才能保证出栈入栈的顺序和队列一致！ 
【本文地址】