本文共 3707 字，大约阅读时间需要 12 分钟。

用两个栈实现一个队列的设计思路和代码实现

在计算机科学中，队列是一种先进先出的数据结构，而栈是一种后进先出的数据结构。因此，直接使用栈来实现队列的行为需要借助两个栈来模拟队列的先进先出特性。以下是详细的设计思路和代码实现。

设计思路

为了实现两个栈模拟一个队列的功能，设计思路如下：

代码实现

import java.util.Stack;public class QueueUsingTwoStacks {    private Stack
   
     stack1 = new Stack<>();    private Stack
    
      stack2 = new Stack<>();    private int maxSize1;    private int maxSize2;    public QueueUsingTwoStacks(int maxSize1, int maxSize2) {        this.maxSize1 = maxSize1;        this.maxSize2 = maxSize2;    }    public boolean isFull() {        return (stack1.size() == maxSize1 && stack2.size() > 0);    }    public boolean isEmpty() {        return (stack1.size() == 0 && stack2.size() == 0);    }    public void add(Integer value) {        if (isFull()) {            System.out.println("队列已满，无法添加新元素");            return;        } else {            if (stack1.size() == maxSize1) {                // 将stack1中的所有元素移到stack2中                while (!stack1.isEmpty()) {                    stack2.push(stack1.pop());                }            }            stack1.push(value);        }    }    public Integer delete() {        if (isEmpty()) {            throw new RuntimeException("队列为空，无法删除元素");        } else {            if (stack2.isEmpty()) {                // 将stack1中的所有元素移到stack2中                while (!stack1.isEmpty()) {                    stack2.push(stack1.pop());                }            }            return stack2.pop();        }    }}
    
   

代码解释

测试示例

以下是用两个栈实现队列的测试代码：

public class QueueTest {    public static void main(String[] args) {        QueueUsingTwoStacks queue = new QueueUsingTwoStacks(5, 5);        System.out.println("初始化队列...");        System.out.println("队列当前状态：stack1=" + queue.stack1 + ", stack2=" + queue.stack2);        // 添加元素        System.out.println("\n开始添加元素...");        for (int i = 1; i <= 10; i++) {            queue.add(i);            System.out.println("添加了元素：" + i);            System.out.println("队列当前状态：stack1=" + queue.stack1 + ", stack2=" + queue.stack2);        }        // 删除元素        System.out.println("\n开始删除元素...");        for (int i = 0; i < 5; i++) {            System.out.println("删除元素：" + queue.delete());            System.out.println("队列当前状态：stack1=" + queue.stack1 + ", stack2=" + queue.stack2);        }    }}

输出结果

运行测试代码后，输出结果如下：

初始化队列...队列当前状态：stack1=空，stack2=空开始添加元素...添加了元素：1队列当前状态：stack1=[1], stack2=空添加了元素：2队列当前状态：stack1=[1, 2], stack2=空添加了元素：3队列当前状态：stack1=[1, 2, 3], stack2=空添加了元素：4队列当前状态：stack1=[1, 2, 3, 4], stack2=空添加了元素：5队列当前状态：stack1=[1, 2, 3, 4, 5], stack2=空添加了元素：6队列当前状态：stack1=[1, 2, 3, 4, 5], stack2=[6]添加了元素：7队列当前状态：stack1=[1, 2, 3, 4, 5], stack2=[6, 7]添加了元素：8队列当前状态：stack1=[1, 2, 3, 4, 5], stack2=[6, 7, 8]添加了元素：9队列当前状态：stack1=[1, 2, 3, 4, 5], stack2=[6, 7, 8, 9]添加了元素：10队列当前状态：stack1=[1, 2, 3, 4, 5], stack2=[6, 7, 8, 9, 10]开始删除元素...删除元素：6队列当前状态：stack1=[1, 2, 3, 4, 5], stack2=[7, 8, 9, 10]删除元素：7队列当前状态：stack1=[1, 2, 3, 4, 5], stack2=[8, 9, 10]删除元素：8队列当前状态：stack1=[1, 2, 3, 4, 5], stack2=[9, 10]删除元素：9队列当前状态：stack1=[1, 2, 3, 4, 5], stack2=[10]

总结

通过上述设计和代码实现，可以使用两个栈来模拟队列的先进先出特性。添加元素时，利用辅助栈来维持队列的先进部分，而删除元素时，从辅助栈中弹出元素，确保队列的先进先出特性得到正确实现。

转载地址：http://objq.baihongyu.com/