使用堆栈实现队列功能

[编程题]使用堆栈实现队列功能

热度指数：30 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

请使用堆栈这一个数据结构实现简单FIFO（先入先出）队列，队列要实现两个方法： push、pop。

为自动测试方便，使用每行输入模拟操作：

1） push 1 表明向队列里面新增一个元素 1 , push 和元素之间用空格表示；

2） pop 表明输出当前队列里面的第一个元素，如果当前队列为空请输出null

请将每个输出以英文逗号拼接到一个字符串中。

示例1

输入

["push 1","push 2","pop","pop","pop","push 3"]

输出

"1,2,null"

算法知识视频讲解

wonderson

    static class MyQueue {
        int[] queue;
        int lo, hi, size, capacity;

        public MyQueue(int n) {
            this.lo = this.hi = this.size = 0;
            this.capacity = n;
            this.queue = new int[n];
        }

        public MyQueue() {
            this(10);
        }

        public void push(int val) {
            if (hi == capacity) {
                if (lo > 0) {
                    int idx = 0;
                    for (int i = lo; i < hi; i++) {
                        queue[idx++] = queue[i];
                    }
                    lo = 0;
                    hi = idx;
                } else {
                    //扩容
                    int[] newQueue = new int[capacity * 2];
                    System.arraycopy(queue, 0, newQueue, 0, capacity);
                    this.queue = newQueue;
                }
            }
            this.queue[hi++] = val;
        }

        public int pop() {
            if (lo == hi) return -1;
            else {
                return this.queue[lo++];
            }
        }

    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // int[] nums = Arrays.stream().mapToInt(Integer::parseInt).toArray();
        String[] ss = scanner.nextLine().split(",");
        YuewenJavaTest.MyQueue myQueue = new YuewenJavaTest.MyQueue();
        for (String s: ss) {
            if (s.startsWith("push")) {
                myQueue.push(Integer.parseInt(s.split(" ")[1]));
            } else {
                System.out.println(myQueue.pop());
            }
        }

        scanner.close();
    }

发表于 2021-09-07 15:03:24 回复(0)