数据结构===队列

概要

队列，就像现实中的排队一样，这样的数据结构，一说很多人都熟悉。

队列，就是像我们排队一样，有2个操作，入队，出队；先进先出；现实中也是一样的。不过，毕竟是数据结构，我们学过数组，链表，从这边分，又衍生出顺序队列，链式队列。接下来看看具体的。

操作

操作有2种，入队和出队。

队列，对数据的操作有2种，入队，出队；时间复杂度都是O(1)。简单看下吧。

入队

入队就是往队列尾部中插入一个数据。

入队操作，就是插入一个元素。队列这种数据结构，只能是尾部插入。想想我们排队，肯定都是排在尾部的，相对于那个队列来说。参考对象别选错了。很重要。

出队

出队就是把队列中的头元素删除掉。

队列是先进先出的。前边说过，出队，肯定也是头部元素先出去的。这个还好理解吧，实在不理解可以画个图看看。

顺序队列

前边说过，从我们学过的最基础的数组和链表的角度看，队列可以分为顺序队列和链式队列。先看看顺序队列，数组的话，支持随机访问下标，插入，删除效率低，涉及到其他元素的位移，插入还涉及到扩容。来看看代码实现。

代码Python

class ArrayQueue:
    
    def __init__(self, capacity: int):
        self._items = []
        self._capacity = capacity
        self._head = 0
        self._tail = 0

    def enqueue(self, item: str) -> bool:
        if self._tail == self._capacity:
            if self._head == 0:
                return False
            else:
                for i in range(0, self._tail - self._head):
                    self._items[i] = self._items[i + self._head]
                self._tail = self._tail - self._head
                self._head = 0
        
        self._items.insert(self._tail, item)
        self._tail += 1
        return True
    
    def dequeue(self) -> Optional[str]:
        if self._head != self._tail:
            item = self._items[self._head]
            self._head += 1
            return item
        else:
            return None
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

链式队列

链式队列是基于链表实现的。

链式队列，这个是基于链表实现的；链表的特点，插入，删除效率高，查找效率低。这些都知道了。来看看代码实现。

代码Python

class Node:
    
    def __init__(self, data: str, next=None):
        self.data = data
        self._next = next

class LinkedQueue:

    def __init__(self):
        self._head: Optional[Node] = None
        self._tail: Optional[Node] = None
    
    def enqueue(self, value: str):
        new_node = Node(value)
        if self._tail:
            self._tail._next = new_node
        else:
            self._head = new_node
        self._tail = new_node
    
    def dequeue(self) -> Optional[str]:
        if self._head:
            value = self._head.data
            self._head = self._head._next
            if not self._head:
                self._tail = None
            return value
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

小结

队列，一种常见的数据结构。

对列，一种常见的数据结构；我们都很熟悉，毕竟经常见到。当然，数据结构中又基于数组的顺序队列，基于链表的链式队列；还有一些其他的，像环式队列等等。这里不在一一列举。其实，还是最基础的特点，先进先出，入队，出队；然后基于不同的其他数据结构实现的，看看特点，时间复杂度。就这么多了。翻篇。