使用栈Stack实现队列Queue

最新推荐文章于 2025-03-26 22:04:22 发布

彩虹之西

最新推荐文章于 2025-03-26 22:04:22 发布

阅读量2.5k

点赞数

文章标签：栈队列模拟

本文链接：https://blog.csdn.net/cjllife/article/details/39581645

版权

本文介绍了如何仅使用栈（Stack）来模拟队列（Queue）的功能。通过两个栈，一个作为入队栈（inStack），另一个作为出队栈（outStack），实现了队列的FIFO特性。入队操作直接将元素压入inStack，而出队时如果outStack为空，则将inStack所有元素转移至outStack后再出队。提供了具体的Java代码实现和测试案例。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

如何只使用stack实现queue呢？由于stack是现进后出（FILO），而queue是先进先出的（FIFO）。也就是说stack进行了一次反向，进行两次反向就能实现queue的功能，所以可以用两个stack实现queue。

假设两个栈inStack和outStack，且都为空。可以认为onStack提供入队的功能，栈outStack提供出队的功能。下面是入队和出队的具体算法：

（1）如果栈outStack不为空，直接弹出栈outStack顶部的数据；

（2）如果栈outStack为空，则依次弹出栈inStack的数据，放入栈outStack中，再弹出栈outStack顶部的数据；

实现的代码：

/**
	 * 使用两个栈来模拟队列
	 * 
	 * @param <T>
	 * 
	 */
	public  class SimulationQueue<T> {
		private Stack<T> inStack;
		private Stack<T> outStack;

		public SimulationQueue() {
			inStack = new Stack<T>();
			outStack = new Stack<T>();
		}

		/**
		 * 入队
		 * 
		 * @param t
		 */
		public void enqueue(T t) {
			inStack.push(t);
		}

		/**
		 * 出队
		 */
		public T dequeue() {
			T temp = null;
			if (!outStack.isEmpty()) {
				temp = outStack.pop();
			} else {
				
				while (!inStack.isEmpty()) {
					temp = inStack.pop();
					outStack.push(temp);
				}

				if (!outStack.isEmpty()) {
					temp = outStack.pop();
				}
			}
			return temp;
		}

		/**
		 * 队列是否为空
		 * 
		 * @return
		 */
		public boolean isEmpty() {
			return inStack.isEmpty() && outStack.isEmpty();
		}

		/**
		 * 清空队列
		 */
		public void clear() {
			inStack.clear();
			outStack.clear();
		}
	}

测试代码：

public static void main(String[] args) {
		SimulationQueue<String> queue = new SimulationQueue<String>();
		queue.enqueue("a");
		queue.enqueue("b");
		queue.enqueue("c");
		queue.enqueue("d");
		while(!queue.isEmpty()){
			System.out.println("当前出队元素："+queue.dequeue());
		}
	}

输出：