隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其實(shí)現(xiàn)

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.

隊(duì)列是項(xiàng)目的集合，由此其操作以FIFO(先進(jìn)先出)的方式工作。 與之相關(guān)的兩個(gè)主要操作是入隊(duì)和出隊(duì) 。

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上 發(fā)布 ，我 在 那里維護(hù)技術(shù)面試課程，并為雄心勃勃的開發(fā)人員撰寫思想著作。

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

課程目標(biāo) ：在本課程結(jié)束時(shí)，您將能夠：

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

了解隊(duì)列數(shù)據(jù)結(jié)構(gòu)是什么，并了解它的實(shí)際用例。

Learn how queues work and their operations.

了解隊(duì)列如何工作及其操作。

Know and implement queues with two different approaches.

用兩種不同的方法了解和實(shí)現(xiàn)隊(duì)列。

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.

我敢肯定，我們所有人以前都在排隊(duì)-也許在計(jì)費(fèi)柜臺(tái)，購物中心或咖啡館。 通常首先為該行中的第一個(gè)人提供服務(wù)，然后為第二，第三等提供服務(wù)。

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.

我們?cè)谟?jì)算機(jī)科學(xué)中也有這個(gè)概念。 以打印機(jī)為例。 假設(shè)我們有一臺(tái)共享打印機(jī)，并且要一次打印多個(gè)作業(yè)。 打印機(jī)在內(nèi)部維護(hù)打印“隊(duì)列”，并根據(jù)先到的順序依次打印作業(yè)。

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.

隊(duì)列被廣泛使用的另一個(gè)實(shí)例是我們機(jī)器的操作系統(tǒng)。 操作系統(tǒng)為每個(gè)進(jìn)程維護(hù)多個(gè)隊(duì)列，例如作業(yè)隊(duì)列，就緒隊(duì)列和設(shè)備隊(duì)列。 如果您有興趣，請(qǐng)參考此鏈接以進(jìn)一步了解它們。

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

我希望我們對(duì)什么是隊(duì)列有深入的了解。 讓我們繼續(xù)前進(jìn)，了解它們?nèi)绾喂ぷ?#xff01;

隊(duì)列如何工作？ (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.

考慮一下管道，也許是您的浴室或房屋其他地方的金屬管。 自然，它有兩個(gè)開放的末端。 想象一下，我們?cè)诠艿乐杏幸恍┰?#xff0c;而我們正在努力將它們淘汰。 我們將插入元素的一端，而將它們?nèi)〕龅牧硪欢恕?如下圖所示，這正是隊(duì)列數(shù)據(jù)結(jié)構(gòu)的整形方式。

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.

與我們最初想到的帶有一個(gè)“開放端”的堆棧數(shù)據(jù)結(jié)構(gòu)不同，隊(duì)列具有兩個(gè)開放端： 前和后 。 它們具有不同的用途- 后方是插入點(diǎn)， 前部是拆卸點(diǎn)。 但是，在內(nèi)部，前后均被視為指針。 我們將在后面的部分中以編程方式了解有關(guān)它們的更多信息。

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).

請(qǐng)注意，首先進(jìn)入的元素是要提供服務(wù)的第一個(gè)元素，并已從隊(duì)列中刪除。 因此，名稱為：先進(jìn)先出(FIFO)。

隊(duì)列操作和隊(duì)列的實(shí)現(xiàn) (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操作的方式，隊(duì)列也具有兩個(gè)成對(duì)操作：

Enqueue: To add elements

排隊(duì)：添加元素

Dequeue: To remove elements.

出隊(duì)：刪除元素。

Let’s move on and cover each.

讓我們繼續(xù)進(jìn)行介紹。

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

單擊此處查看有關(guān)堆棧數(shù)據(jù)結(jié)構(gòu)的課程！

1.入隊(duì) (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操作從后端將元素添加到您的隊(duì)列中。 最初，當(dāng)queue為空時(shí)，我們的front (有時(shí)稱為head )和后 (有時(shí)稱為tail )指針都是NULL 。

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

現(xiàn)在，讓我們向隊(duì)列添加一個(gè)元素(例如'a' 。 無論我們的前部和后部現(xiàn)在點(diǎn)'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.

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

2.出隊(duì) (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意味著從隊(duì)列中刪除或刪除元素。 這是從隊(duì)列的前端發(fā)生的。 在處理或提供服務(wù)后，會(huì)將特定元素從隊(duì)列中刪除。 我們不能dequeue空隊(duì)列，我們需要至少一個(gè)元素出現(xiàn)在隊(duì)列中，當(dāng)我們要dequeue 。 下圖說明了我們之前的隊(duì)列的出隊(duì)。

實(shí)作 (Implementation)

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

讓我們使用python來實(shí)現(xiàn)。 在python ，可以使用python庫中的三個(gè)不同模塊來實(shí)現(xiàn)隊(duì)列。

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

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

• 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類可能是一件昂貴的事情，因?yàn)樗婕暗矫看翁砑踊騽h除時(shí)元素的移動(dòng)。 這需要O(n)時(shí)間。 取而代之的是，我們可以使用'deque'類，它是'Double-ended queue'的簡寫，并且需要O(1)時(shí)間，效率更高。

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:

首先，我們可以使用大多數(shù)語言的list或array快速實(shí)現(xiàn)queue ！ 鑒于它們都是線性數(shù)據(jù)結(jié)構(gòu)，因此這很直觀，我們只需要對(duì)數(shù)據(jù)流施加一些約束：

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

為了enqueue隊(duì)列中的一個(gè)項(xiàng)目，我們可以使用列表功能append 。

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

要從隊(duì)列中dequeue項(xiàng)目，我們可以使用列表函數(shù)pop(0) 。

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.

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

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)

使用隊(duì)列類實(shí)現(xiàn)隊(duì)列 (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中使用隊(duì)列的另一種方法是通過Queue模塊中可用的隊(duì)列類。 它具有許多功能，并且與線程一起廣泛用于多線程操作。 它還具有FIFO，LIFO和優(yōu)先級(jí)隊(duì)列。 但是，我們將使用python庫的queue類實(shí)現(xiàn)一個(gè)簡單的隊(duì)列。

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模塊中導(dǎo)入的。 使用Queue()構(gòu)造函數(shù)初始化Queue() 。 請(qǐng)注意，它接受maxsize()參數(shù)，該參數(shù)指定隊(duì)列大小的上限以限制內(nèi)存使用量。

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

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

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

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

You can find more functions on deque collections here.

您可以在此處找到關(guān)于雙端隊(duì)列的更多功能。

# 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

使用雙端隊(duì)列類實(shí)現(xiàn)隊(duì)列 (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!

讓我們繼續(xù)使用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.

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

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

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

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

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

出隊(duì)后，我們的最終隊(duì)列如下所示：

Final queue
deque(['d'])

You can find more functions on deque collections here.

您可以在此處找到有關(guān)雙端隊(duì)列的更多功能。

# 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)

結(jié)論 (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.

在本文中，我們從隊(duì)列的基礎(chǔ)開始，然后學(xué)習(xí)了隊(duì)列操作，后來擴(kuò)展為使用python實(shí)現(xiàn)隊(duì)列的兩種不同方法。 我們了解了FIFO方法在隊(duì)列中的工作方式，以及使用集合在時(shí)間復(fù)雜度方面如何有效。 我建議您仔細(xì)閱讀與文章內(nèi)聯(lián)的資源，以進(jìn)一步了解隊(duì)列。

翻譯自: https://medium.com/swlh/understanding-the-queue-data-structure-and-its-implementations-59685f0112c

隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其實(shí)現(xiàn)

總結(jié)

以上是生活随笔為你收集整理的队列的链式存储结构及其实现_了解队列数据结构及其实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。