A queue is a collection of items whereby its operations work in a FIFO — First In First Out manner. The two primary operations associated with them are enqueue and dequeue.

隊列是項目的集合，由此其操作以FIFO(先進先出)的方式工作。 與之相關的兩個主要操作是入隊和出隊 。

This lesson was originally published at https://algodaily.com, where I maintain a technical interview course and write think-pieces for ambitious developers.

本課程最初在 https://algodaily.com上 發布 ，我 在 那里維護技術面試課程，并為雄心勃勃的開發人員撰寫思想著作。

Lesson Objectives: At the end of this lesson, you will be able to:

課程目標 ：在本課程結束時，您將能夠：

1. Know what the queue data structure is and appreciate it’s real-world use cases.

   了解隊列數據結構是什么，并了解它的實際用例。

2. Learn how queues work and their operations.
   了解隊列如何工作及其操作。
3. Know and implement queues with two different approaches.
   用兩種不同的方法了解和實現隊列。

I’m sure all of us have been in queues before — perhaps at billing counters, shopping centers, or cafes. The first person in the line is usually serviced first, then the second, third, and so forth.

我敢肯定，我們所有人以前都在排隊-也許在計費柜臺，購物中心或咖啡館。 通常首先為該行中的第一個人提供服務，然后為第二，第三等提供服務。

We have this concept in computer science as well. Take the example of a printer. Suppose we have a shared printer, and several jobs are to be printed at once. The printer maintains a printing “queue” internally, and prints the jobs in sequence based on which came first.

我們在計算機科學中也有這個概念。 以打印機為例。 假設我們有一臺共享打印機，并且要一次打印多個作業。 打印機在內部維護打印“隊列”，并根據先到的順序依次打印作業。

Another instance where queues are extensively used is in the operating system of our machines. An OS maintains several queues such as a job queue, a ready queue, and a device queue for each of the processes. If you’re interested, refer to this link to know more about them.

隊列被廣泛使用的另一個實例是我們機器的操作系統。 操作系統為每個進程維護多個隊列，例如作業隊列，就緒隊列和設備隊列。 如果您有興趣，請參考此鏈接以進一步了解它們。

I hope we’ve got a solid high-level understanding about what queues are. Let’s go ahead and understand how they work!

我希望我們對什么是隊列有深入的了解。 讓我們繼續前進，了解它們如何工作！

隊列如何工作？ (How do queues work?)

Consider a pipe, perhaps a metal one in your bathroom or elsewhere in the house. Naturally, it has two open ends. Imagine that we have some elements in the pipe, and we’re trying to get them out. There will be one end through which we have inserted the elements, and there’s another end from which we’re getting them out. As seen in the figure below, this is precisely how the queue data structure is shaped.

考慮一下管道，也許是您的浴室或房屋其他地方的金屬管。 自然，它有兩個開放的末端。 想象一下，我們在管道中有一些元素，而我們正在努力將它們淘汰。 我們將插入元素的一端，而將它們取出的另一端。 如下圖所示，這正是隊列數據結構的整形方式。

Unlike the stack data structure that we primarily think of with one “open end”, the queue has two open ends: the front and rear. They have different purposes — with the rear being the point of insertion and the front being that of removal. However, internally, the front and rear are treated as pointers. We’ll learn more about them in the subsequent sections programmatically.

與我們最初想到的帶有一個“開放端”的堆棧數據結構不同，隊列具有兩個開放端： 前和后 。 它們具有不同的用途- 后方是插入點， 前部是拆卸點。 但是，在內部，前后均被視為指針。 我們將在后面的部分中以編程方式了解有關它們的更多信息。

Note that the element that got inside first is the initial one to be serviced, and removed from the queue. Hence the name: First In First Out (FIFO).

請注意，首先進入的元素是要提供服務的第一個元素，并已從隊列中刪除。 因此，名稱為：先進先出(FIFO)。

隊列操作和隊列的實現 (Queue operations and Implementation of queues)

Similar to how a stack has push and pop operations, a queue also has two pairwise operations:

類似于堆棧具有push和pop操作的方式，隊列也具有兩個成對操作：

1. Enqueue: To add elements
   排隊：添加元素
2. Dequeue: To remove elements.
   出隊：刪除元素。

Let’s move on and cover each.

讓我們繼續進行介紹。

Click here to check out our lesson on the stack data structure!

單擊此處查看有關堆棧數據結構的課程！

1.入隊 (1. Enqueue)

The enqueue operation, as said earlier, adds elements to your queue from the rear end. Initially, when the queue is empty, both our front (sometimes called head) and rear (sometimes called tail) pointers are NULL.

如前所述，入enqueue操作從后端將元素添加到您的隊列中。 最初，當queue為空時，我們的front (有時稱為head )和后 (有時稱為tail )指針都是NULL 。

Now, let’s add an element — say, 'a'-- to the queue. Both our front and rear now point to 'a'.

現在，讓我們向隊列添加一個元素(例如'a' 。 無論我們的前部和后部現在點'a' 。

Let’s add another element to our queue — 'b'. Now, our front pointer remains the same, whereas the rear pointer points to 'b'. We'll add another item 'c' and you'll see that that element is also added at the rear end.

讓我們向隊列添加另一個元素-'b 'b' 。 現在，我們的前指針保持不變， 而后指針指向'b' 。 我們將添加另一個項目'c' ，您將看到該元素也添加在后端 。

2.出隊 (2. Dequeue)

To dequeue means to remove or delete elements from the queue. This happens from the front end of the queue. A particular element is removed from a queue after it is done being processed or serviced. We cannot dequeue an empty queue, and we require at least one element to be present in the queue when we want to dequeue. The following figure explains the dequeuing of our previous queue.

dequeue意味著從隊列中刪除或刪除元素。 這是從隊列的前端發生的。 在處理或提供服務后，會將特定元素從隊列中刪除。 我們不能dequeue空隊列，我們需要至少一個元素出現在隊列中，當我們要dequeue 。 下圖說明了我們之前的隊列的出隊。

實作 (Implementation)

Let’s use python for our implementation. In python, queues can be implemented using three different modules from the python library.

讓我們使用python來實現。 在python ，可以使用python庫中的三個不同模塊來實現隊列。

• list (using a list or array is generalizable to most languages)

  列表(使用list或array可推廣到大多數語言)

• collections.deque (language-specific)
  collections.deque(特定于語言)
• queue.Queue (language-specific)
  queue.Queue(特定于語言)

Using the list class can be a costly affair since it involves shifting of elements for every addition or deletion. This requires O(n) time. Instead, we can use the 'deque' class, which is a shorthand for 'Double-ended queue' and requires O(1) time, which is much more efficient.

使用list類可能是一件昂貴的事情，因為它涉及到每次添加或刪除時元素的移動。 這需要O(n)時間。 取而代之的是，我們可以使用'deque'類，它是'Double-ended queue'的簡寫，并且需要O(1)時間，效率更高。

So first — we can quickly implement a queue using a list or array in most languages! This is intuitive given that they're both linear data structures, and we just need to enforce some constraints on data flow:

首先，我們可以使用大多數語言的list或array快速實現queue ！ 鑒于它們都是線性數據結構，因此這很直觀，我們只需要對數據流施加一些約束：

1. To enqueue an item in the queue, we can use the list function append.

   為了enqueue隊列中的一個項目，我們可以使用列表功能append 。

2. To dequeue an item from the queue, we can use the list function pop(0).

   要從隊列中dequeue項目，我們可以使用列表函數pop(0) 。

3. If we want the “top-most” (or last element to be processed) item in the queue, we can get the last index of the list using the [-1] index operator.

   如果我們想要隊列中“最頂層”(或最后一個要處理的元素)項，則可以使用[-1]索引運算符獲取列表的最后一個索引。

This is by far the easiest approach, but not necessarily the most performant.

到目前為止，這是最簡單的方法，但不一定是性能最高的方法。

# Initialize a queue list
queue = [] 
  
# Add elements 
queue.append(1) 
queue.append(2) 
queue.append(3) 
  
print("Initial queue state:") 
print(queue) 
  
# Removing elements from the queue 
print("Elements dequeued from queue") 
print(queue.pop(0)) 
print(queue.pop(0)) 
print(queue.pop(0)) 
  
print("Queue after removing elements") 
print(queue)

使用隊列類實現隊列 (Implementation of queue using queue class)

Another way of using queues in python is via the queue class available in Queue module. It has numerous functions and is widely used along with threads for multi-threading operations. It further has FIFO, LIFO, and priority types of queues. However, we’ll implement a simple queue using the queue class of python library.

在python中使用隊列的另一種方法是通過Queue模塊中可用的隊列類。 它具有許多功能，并且與線程一起廣泛用于多線程操作。 它還具有FIFO，LIFO和優先級隊列。 但是，我們將使用python庫的queue類實現一個簡單的隊列。

The queue class is imported from the Queue module. The queue is initialized using the Queue() constructor. Note that it accepts a maxsize() argument, specifying an upper boundary of queue size to throttle memory usage.

queue類是從“ Queue模塊中導入的。 使用Queue()構造函數初始化Queue() 。 請注意，它接受maxsize()參數，該參數指定隊列大小的上限以限制內存使用量。

We use the put() function to add elements to the queue, and the get() function to remove elements from the queue. Since we have a maxsize check here, we have two other functions to check empty and full conditions. The unction empty() returns a boolean true if the queue is empty and false if otherwise. Likewise, the full() function returns a boolean true if the queue is full and false if otherwise.

我們使用put()函數將元素添加到隊列中，使用get()函數從隊列中刪除元素。 由于這里有一個maxsize檢查，因此我們還有另外兩個功能可以檢查空和滿條件。 如果隊列為空，則unction empty()返回布爾值true，否則返回false 。 同樣，如果隊列已滿，則full()函數返回布爾值true，否則返回false 。

Here, we added elements to the queue and checked for the full condition using q.full(). Since the maxsize is four and we added four elements, the boolean is set to true.

在這里，我們將元素添加到隊列中，并使用q.full().檢查是否已滿q.full(). 由于maxsize為四個，并且我們添加了四個元素，因此布爾值設置為true 。

Later, we removed three elements, leaving one element in the queue. Hence the q.empty() function returned boolean false.

后來，我們刪除了三個元素，在隊列中保留了一個元素。 因此， q.empty()函數返回布爾值false。

You can find more functions on deque collections here.

您可以在此處找到關于雙端隊列的更多功能。

# Python program to demonstrate the implementation of a queue using the queue modulefrom queue import Queue# Initializing a queue with maxsize 4 
q = Queue(maxsize = 4)# Add/enqueue elements to queue 
q.put('a') 
q.put('b') 
q.put('c') 
q.put('d')# Return Boolean for Full Queue 
print("\nFull: ", q.full())# Remove/dequeue elements from queue 
print("\nElements dequeued from the queue") 
print(q.get()) 
print(q.get()) 
print(q.get())# Return Boolean for Empty Queue 
print("\nEmpty: ", q.empty()) 
print("\nQueue size:", q.qsize()) # prints size of the queue

使用雙端隊列類實現隊列 (Implementation of queue using deque class)

Let’s go ahead and utilize a queue along with its operations in python language using the deque class!

讓我們繼續使用deque類在Python語言中使用deque及其操作！

The deque class is imported from the collections module. We use append() function to add elements to the queue and popleft() function to remove elements from the queue.

雙端隊列類是從collections模塊導入的。 我們使用append()函數將元素添加到隊列中，并使用popleft()函數從隊列中刪除元素。

We can see that after enqueuing, our initial queue looks like this:

我們可以看到，入隊后，我們的初始隊列如下所示：

Initial queue:
deque(['a', 'b', 'c', 'd'])

And after dequeuing, our final queue looks something like this:

出隊后，我們的最終隊列如下所示：

Final queue
deque(['d'])

You can find more functions on deque collections here.

您可以在此處找到有關雙端隊列的更多功能。

# Python program to demonstrate queue implementation using collections.dequeuefrom collections import deque# Initializing a deque with deque() constructor
q = deque()# Adding/Enqueueing elements to a queue 
q.append('a') 
q.append('b') 
q.append('c') 
q.append('d')print("Initial queue:") 
print(q)# Removing/Dequeuing elements from a queue 
print("\nElements dequeued from the queue:") 
print(q.popleft()) 
print(q.popleft()) 
print(q.popleft())print("\nFinal queue") 
print(q)

結論 (Conclusion)

In this article, we began right from the basics of queues then learned the queue operations later scaled to two different approaches in implementing queues using python. We saw how the FIFO approach works in queues and how using collections is effective in terms of time complexity. I recommend you to go through the resources linked in-line with the article for further reading on queues.

在本文中，我們從隊列的基礎開始，然后學習了隊列操作，后來擴展為使用python實現隊列的兩種不同方法。 我們了解了FIFO方法在隊列中的工作方式，以及使用集合在時間復雜度方面如何有效。 我建議您仔細閱讀與文章內聯的資源，以進一步了解隊列。