数据结构【队列】（十二）：队列实现栈

淡淡的烟草味﹌ 2022-02-28 04:16 319阅读 0赞

## 问题描述 ##

使用两个队列实现栈，要满足后入先出，比如输入：1 2 3 4 5，那么输出就应该是：5 4 3 2 1

## 解题思路 ##

使用两个队列，分别是数据队列和辅助队里，

1、数据添加到数据队列中

2、元素出栈时，将有数据的队列元素（保留最后一个元素）移动到无数据的队列

3、将最后一个元素出队，正式所需要的出栈数据

## 代码实现 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA2NDcwMzU_size_16_color_FFFFFF_t_70]

public class QueueImplamentStack {
        //数据队列
        private static Queue originalQueue = new LinkedList();
        //辅助队列
        private static Queue helpQueue = new LinkedList();
    
        public static void main(String[] args) {
            System.out.println("入栈的元素：");
            //添加数据到数据队列
            for (int i = 1; i < 6; i++) {
                System.out.print(i + " ");
                originalQueue.add(i);
            }
            System.out.println();
            System.out.println("出栈的元素：");
            for (int i = 1; i < 6; i++) {
                //获取元素
                System.out.print(popElement() + " ");
            }
        }
    
        /**
         * 获取元素
         */
        private static Object popElement() {
            if (originalQueue.isEmpty()) {
                return popElementFromOriginalQueue();
            } else {
                return popElementFromHelpQueue();
            }
        }
    
        /**
         * 将辅助队列的元素放入数据队列，并将辅助队列的最后一个元素出队
         */
        private static Object popElementFromOriginalQueue() {
            int size = helpQueue.size();
            for (int i = 1; i < size; i++) {
                originalQueue.add(helpQueue.poll());
            }
            return helpQueue.poll();
        }
    
        /**
         * 将数据队列的元素放入辅助队列，并将数据队列的最后一个元素出队
         */
        private static Object popElementFromHelpQueue() {
            int size = originalQueue.size();
            for (int i = 1; i < size; i++) {
                helpQueue.add(originalQueue.poll());
            }
            return originalQueue.poll();
        }
    
    }

输出结果：

入栈的元素：
    1 2 3 4 5 
    出栈的元素：
    5 4 3 2 1

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA2NDcwMzU_size_16_color_FFFFFF_t_70]: /images/20220228/0420aed1f54b47ec80a702616f81abc1.png