队列&栈（数据结构与算法）

怼烎@ 2021-12-24 03:09 409阅读 0赞

### ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODIwMTkzNg_size_16_color_FFFFFF_t_70][] ###

### 队列 ###

### **192.描述一下队列？** ###

队列是一种先进先出(FIFO)的数据结构，从队尾进，从队头出

![20190521215434655.png][]

在 FIFO 数据结构中，将**`首先处理添加到队列中的第一个元素`**。

如上图所示，队列是典型的 FIFO 数据结构。插入（insert）操作也称作入队（enqueue），新元素始终被添加在**`队列的末尾`**。 删除（delete）操作也被称为出队（dequeue)。 你只能移除**`第一个元素`。**

**示例 - 队列**

**如下图所示**

**1.入队，将6插入**

![20190626181004351.png][]![2019062618101357.png][]

2.出队，删除5

![20190626181108584.png][]![20190626181117247.png][]

为了实现队列，我们可以使用**动态数组**和指向队列头部的**索引**。

如上所述，队列应支持两种操作：**入队和出队**。入队会向队列追加一个新元素，而出队会删除第一个元素。 所以我们需要一个索引来指出起点。

这是一个供你参考的实现：

class MyQueue {
        // store elements
        private List<Integer> data;         
        // a pointer to indicate the start position
        private int p_start;            
        public MyQueue() {
            data = new ArrayList<Integer>();
            p_start = 0;
        }
        /** Insert an element into the queue. Return true if the operation is successful. */
        public boolean enQueue(int x) {
            data.add(x);
            return true;
        };    
        /** Delete an element from the queue. Return true if the operation is successful. */
        public boolean deQueue() {
            if (isEmpty() == true) {
                return false;
            }
            p_start++;
            return true;
        }
        /** Get the front item from the queue. */
        public int Front() {
            return data.get(p_start);
        }
        /** Checks whether the queue is empty or not. */
        public boolean isEmpty() {
            return p_start >= data.size();
        }     
    };
    
    public class Main {
        public static void main(String[] args) {
            MyQueue q = new MyQueue();
            q.enQueue(5);
            q.enQueue(3);
            if (q.isEmpty() == false) {
                System.out.println(q.Front());
            }
            q.deQueue();
            if (q.isEmpty() == false) {
                System.out.println(q.Front());
            }
            q.deQueue();
            if (q.isEmpty() == false) {
                System.out.println(q.Front());
            }
        }
    }

### 缺点 ###

上面的实现很简单，但在某些情况下效率很低。 随着起始指针的移动，浪费了越来越多的空间。 当我们有空间限制时，这将是难以接受的。

### **193.描述一下循环队列？** ###

循环队列。 具体来说，我们可以使用**`固定大小的数组`**和**`两个指针`**来指示起始位置和结束位置。 目的是**`重用`**我们之前提到的**`被浪费的存储`。**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODIwMTkzNg_size_16_color_FFFFFF_t_70]: /images/20211223/66091e70f88f40559f5bcff65e8c4271.png
[20190521215434655.png]: /images/20211223/de6ee14fdbd94103a008c4b2dc6b14c8.png
[20190626181004351.png]: https://img-blog.csdnimg.cn/20190626181004351.png
[2019062618101357.png]: /images/20211223/c064a609949c4911aa8e019b09a66870.png
[20190626181108584.png]: https://img-blog.csdnimg.cn/20190626181108584.png
[20190626181117247.png]: /images/20211223/2af475a5f3ce4374a10a4f49f860366b.png