Python Hàng đợi: FIFO, LIFO Ví dụ

Là gì Python Xếp hàng?

Hàng đợi là nơi chứa dữ liệu. Dữ liệu được nhập trước sẽ bị xóa trước và do đó hàng đợi còn được gọi là “First in First Out” (FIFO). Hàng đợi có hai đầu phía trước và phía sau. Các mục được nhập từ phía sau và loại bỏ từ phía trước.

Làm thế nào để Python Công việc xếp hàng?

Có thể dễ dàng so sánh hàng đợi với ví dụ thực tế về dòng người xếp hàng chờ ở quầy bán vé, người đứng trước sẽ nhận được vé trước, tiếp theo là người tiếp theo, v.v. Logic tương tự cũng áp dụng cho cấu trúc dữ liệu hàng đợi.

Dưới đây là sơ đồ biểu diễn hàng đợi:

Đuôi đại diện cho điểm mà các mục được chèn vào trong hàng đợi. Trong ví dụ này, 7 là giá trị cho điều đó.

Mặt trận đại diện cho điểm mà các mục trong hàng đợi sẽ bị xóa. Nếu bạn xóa một mục khỏi hàng đợi, phần tử đầu tiên bạn sẽ nhận được là 1, như trong hình.

Mục 1 là mục đầu tiên được chèn vào hàng đợi và khi xóa nó là mục đầu tiên xuất hiện. Do đó hàng đợi được gọi là FIRST IN FIRST OUT (FIFO)

Trong hàng đợi, các mục được xóa theo thứ tự và không thể xóa ở giữa. Bạn không thể xóa ngẫu nhiên mục 5 khỏi hàng đợi, để làm được điều đó, bạn sẽ phải xóa tất cả các mục trước mục 5. Các mục trong hàng đợi sẽ bị xóa theo thứ tự chúng được chèn vào.

Các loại hàng đợi trong Python

Chủ yếu có hai loại hàng đợi trong Python:

• Hàng đợi vào trước ra trước: Đối với điều này, phần tử đến trước sẽ là phần tử xuất hiện đầu tiên. Để làm việc với FIFO, bạn phải gọi Xếp hàng() lớp từ mô-đun hàng đợi.
• Hàng đợi cuối cùng ra trước: Ở đây, phần tử được nhập cuối cùng sẽ là phần tử xuất hiện đầu tiên. Để làm việc với LIFO, bạn phải gọi LifoQueue() lớp từ mô-đun hàng đợi.

Python cài đặt hàng đợi

Rất dễ dàng để làm việc với hàng đợi trong python. Dưới đây là các bước cần làm theo để sử dụng hàng đợi trong mã của bạn.

Bước 1) Bạn chỉ cần nhập mô-đun hàng đợi, như hiển thị bên dưới:

import queue

Theo mặc định, mô-đun này có sẵn với python và bạn không cần bất kỳ cài đặt bổ sung nào để bắt đầu làm việc với hàng đợi. Có 2 loại hàng đợi FIFO (vào trước ra trước) và LIFO (vào sau ra trước).

Bước 2) Để làm việc với hàng đợi FIFO, hãy gọi lớp Hàng đợi bằng cách sử dụng mô-đun hàng đợi được nhập như dưới đây:

import queue
q1 = queue.Queue()

Bước 3) Để làm việc với hàng đợi LIFO, hãy gọi lớp LifoQueue() như dưới đây:

import queue
q1 = queue.LifoQueue()

Các phương thức có sẵn bên trong lớp Queue và LifoQueue

Sau đây là các phương thức quan trọng có sẵn trong lớp Queue và LifoQueue:

• đặt (mục): Điều này sẽ đưa mục vào hàng đợi.
• lấy(): Điều này sẽ trả lại cho bạn một mục từ hàng đợi.
• trống(): Nó sẽ trả về true nếu hàng đợi trống và trả về false nếu có các mục.
• qsize(): trả về kích thước của hàng đợi.
• đầy(): trả về true nếu hàng đợi đã đầy, nếu không trả về false.

Ví dụ về hàng đợi vào trước ra trước

Trong trường hợp nhập trước xuất trước, phần tử nào đi trước sẽ là phần tử ra trước.

Thêm và mục trong hàng đợi

Chúng ta hãy làm một ví dụ để thêm một mục vào hàng đợi. Để bắt đầu làm việc với hàng đợi, trước tiên hãy nhập hàng đợi mô-đun, như trong ví dụ bên dưới.

Để thêm một mục, bạn có thể sử dụng phương thức put() như trong ví dụ:

import queue
q1 = queue.Queue()
q1.put(10) #this will additem 10 to the queue.

Theo mặc định, kích thước của hàng đợi là vô hạn và bạn có thể thêm bất kỳ số lượng mục nào vào đó. Trong trường hợp bạn muốn xác định kích thước của hàng đợi, bạn có thể thực hiện tương tự như sau

import queue
q1 = queue.Queue(5) #The max size is 5.
q1.put(1)
q1.put(2)
q1.put(3)
q1.put(4)
q1.put(5)
print(q1.full()) # will return true.

Đầu ra:

True

Bây giờ kích thước của hàng đợi là 5 và sẽ không mất quá 5 mục và phương thức q1.full() sẽ trả về true. Việc thêm bất kỳ mục nào nữa sẽ không thực thi mã nữa.

Xóa một mục khỏi hàng đợi

Để xóa một mục khỏi hàng đợi, bạn có thể sử dụng phương thức get(). Phương pháp này cho phép các mục từ hàng đợi khi được gọi.

Ví dụ sau đây cho thấy cách xóa một mục khỏi hàng đợi.

import queue
q1 = queue.Queue()
q1.put(10)

item1 = q1.get()

print('The item removed from the queue is ', item1)

Đầu ra:

The item removed from the queue is  10

Ví dụ về hàng đợi vào trước ra trước

Trong trường hợp cuối cùng trong hàng đợi ra đầu tiên, phần tử được nhập cuối cùng sẽ xuất hiện đầu tiên.

Để làm việc với LIFO, tức là cuối cùng trong hàng đợi ra đầu tiên, chúng ta cần nhập mô-đun hàng đợi và sử dụng phương thức LifoQueue().

Thêm và mục trong hàng đợi

Ở đây chúng ta sẽ hiểu cách thêm một mục vào hàng đợi LIFO.

import queue
q1 = queue.LifoQueue()
q1.put(10)

Bạn phải sử dụng phương thức put() trên LifoQueue, như trong ví dụ trên.

Xóa một mục khỏi hàng đợi

Để xóa một mục khỏi hàng đợi LIFO, bạn có thể sử dụng phương thức get().

import queue
q1 = queue.LifoQueue()
q1.put(10)

item1 = q1.get()

print('The item removed from the LIFO queue is ', item1)

Đầu ra:

The item removed from the LIFO queue is  10

Thêm nhiều hơn 1 mục vào Hàng đợi

Trong các ví dụ trên, chúng ta đã thấy cách thêm một mục và xóa mục đó cho hàng đợi FIFO và LIFO. Bây giờ chúng ta sẽ xem cách thêm nhiều mục và xóa mục đó.

Thêm và ghi vào hàng FIFO

import queue
q1 = queue.Queue()

for i in range(20):
    q1.put(i) # this will additem from 0 to 20 to the queue

Xóa một mục khỏi hàng đợi FIFO

import queue
q1 = queue.Queue()

for i in range(20):
    q1.put(i) # this will additem from 0 to 20 to the queue

while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.

Đầu ra:

The value is  0
The value is  1
The value is  2
The value is  3
The value is  4
The value is  5
The value is  6
The value is  7
The value is  8
The value is  9
The value is  10
The value is  11
The value is  12
The value is  13
The value is  14
The value is  15
The value is  16
The value is  17
The value is  18
The value is  19

Thêm và ghi vào hàng LIFO

import queue
q1 = queue.LifoQueue()
for i in range(20):
    q1.put(i) # this will additem from 0 to 20 to the queue

Xóa một mục khỏi hàng đợi LIFO

import queue
q1 = queue.LifoQueue()

for i in range(20):
    q1.put(i) # this will additem from 0 to 20 to the queue


while not q1.empty():
print("The value is ", q1.get()) # get() will remove the item from the queue.

Đầu ra:

The value is  19
The value is  18
The value is  17
The value is  16
The value is  15
The value is  14
The value is  13
The value is  12
The value is  11
The value is  10
The value is  9
The value is  8
The value is  7
The value is  6
The value is  5
The value is  4
The value is  3
The value is  2
The value is  1
The value is  0 

Sắp xếp hàng đợi

Ví dụ sau đây cho thấy cách sắp xếp hàng đợi. Thuật toán được sử dụng để sắp xếp là sắp xếp nổi bọt.

import queue
q1 = queue.Queue()
#Addingitems to the queue
q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)

#using bubble sort on the queue
n =  q1.qsize()
for i in range(n):
    x = q1.get() # the element is removed
    for j in range(n-1):
        y = q1.get() # the element is removed
        if x > y :  
            q1.put(y)   #the smaller one is put at the start of the queue
        else:
            q1.put(x)  # the smaller one is put at the start of the queue
            x = y     # the greater one is replaced with x and compared again with nextelement
    q1.put(x)

while (q1.empty() == False): 
print(q1.queue[0], end = " ")  
        q1.get()

Đầu ra:

3 4 5 10 11 21

Revxóa hàng đợi

Để đảo ngược hàng đợi, bạn có thể sử dụng hàng đợi khác và đệ quy.

Ví dụ sau đây cho thấy cách đảo ngược hàng đợi.

Ví dụ:

import queue
q1 = queue.Queue()

q1.put(11)
q1.put(5)
q1.put(4)
q1.put(21)
q1.put(3)
q1.put(10)

def reverseQueue (q1src, q2dest) :  
    buffer = q1src.get()
    if (q1src.empty() == False) :
reverseQueue(q1src, q2dest)      #using recursion
    q2dest.put(buffer)
return q2dest

q2dest = queue.Queue()
qReversed = reverseQueue(q1,q2dest)

while (qReversed.empty() == False): 
print(qReversed.queue[0], end = " ")  
        qReversed.get()

Đầu ra:

10 3 21 4 5 11

Tổng kết

• Hàng đợi là nơi chứa dữ liệu. Có hai loại hàng đợi là FIFO và LIFO.
• Đối với FIFO (Hàng đợi vào trước ra trước), phần tử nào đến trước sẽ là phần tử xuất hiện đầu tiên.
• Đối với LIFO (Hàng đợi vào trước ra trước), phần tử được nhập sau cùng sẽ là phần tử xuất hiện đầu tiên.
• Một mục trong hàng đợi được thêm bằng phương thức put(item).
• Để xóa một mục, phương thức get() được sử dụng.