数据结构===队列

文章目录

概要
操作
- 入队
- 出队
顺序队列
- 代码Python
链式队列
- 代码Python
小结

概要

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

队列，就是像我们排队一样，有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

链式队列

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

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

代码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