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

Mục lục:

Anonim

Hàng đợi Python là gì?

Hàng đợi là một vùng chứa 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à "Nhập trước xuất trước" (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.

Trong hướng dẫn Python này, bạn sẽ học:

  • Hàng đợi Python là gì?
  • Hàng đợi Python hoạt động như thế nào?
  • Các loại hàng đợi trong Python
  • Cài đặt hàng đợi Python
  • Các phương thức có sẵn bên trong lớp Queue và LifoQueue
  • Ví dụ về hàng đợi đầu tiên trong đầu tiên
  • Ví dụ về hàng đợi Cuối cùng trong Đầu ra Đầu tiên
  • Thêm nhiều hơn 1 mục trong hàng đợi
  • Sắp xếp hàng đợi
  • Đảo ngược hàng đợi

Hàng đợi Python hoạt động như thế nào?

Có thể dễ dàng so sánh hàng đợi với ví dụ trong thế giới thực là dòng người xếp hàng chờ ở quầy bán vé, người đứng trước sẽ lấy 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.

Đây là một biểu diễn sơ đồ của hàng đợi:

Các phía sau tượng trưng cho điểm nơi các mặt hàng được chèn vào bên trong hàng đợi. Trong ví dụ này, 7 là giá trị cho điều đó.

Các Mặt trận đại diện cho điểm mà các mặt hàng từ hàng đợi sẽ được gỡ bỏ. 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ư thể hiện trong hình.

Mục 1 là mục đầu tiên được chèn vào hàng đợi, và trong 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 một hàng đợi, các mục được xóa theo thứ tự và không thể bị xóa ở giữa. Bạn chỉ không thể loại bỏ ngẫu nhiên mục 5 khỏi hàng đợi, để làm điều đó, bạn sẽ phải xóa tất cả các mục trướ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:

  • First in First out Queue: Đối với điều này, phần tử đi 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 lớp Queue () từ mô-đun hàng đợi.

  • Cuối cùng trong Hàng đợi xuất đầu tiên: Ở đây, phần tử được nhập sau 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 lớp LifoQueue () từ mô-đun hàng đợi.

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

Nó 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 để 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ư được hiển thị bên dưới:

import queue

Mô-đun có sẵn theo mặc định 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 (xuất trước vào trước) và LIFO (nhập trước xuất sau).

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ư hình dưới đây: 

import queueq1 = queue.Queue()

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

import queueq1 = 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 bên trong lớp Queue và LifoQueue:

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

Ví dụ về hàng đợi đầu tiên trong đầu tiên

Trong trường hợp ra trước vào trước, phần tử đi trước sẽ là phần tử đi ra đầu tiên.

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

Hãy để chúng tôi làm việc trên một ví dụ để thêm một mục trong 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ư thể hiện 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 queueq1 = 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 như sau

import queueq1 = 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à nó sẽ không có nhiều hơn 5 mục và phương thức q1.full () sẽ trả về true. 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 được gọi là get (). Phương thức 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 queueq1 = 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 Cuối cùng trong Đầu ra Đầu tiên

Trong trường hợp cuối cùng trong hàng đợi xuất đầu tiên, phần tử được nhập sau cùng sẽ là phần tử 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 một 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 queueq1 = 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 LIFOqueue, bạn có thể sử dụng phương thức get ().

import queueq1 = 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 trong 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 FIFO và LIFOqueue. Bây giờ chúng ta sẽ xem làm thế nào để thêm nhiều hơn một mục và cũng có thể loại bỏ nó.

Thêm và mục trong FIFOqueue

import queueq1 = 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 FIFOqueue

import queueq1 = queue.Queue()for i in range(20):q1.put(i) # this will additem from 0 to 20 to the queuewhile not q1.empty():print("The value is ", q1.get()) # get() will remove the item from the queue.

Đầu ra:

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

Thêm và mục trong một LIFOqueue

import queueq1 = 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 LIFOqueue

import queueq1 = queue.LifoQueue()for i in range(20):q1.put(i) # this will additem from 0 to 20 to the queuewhile not q1.empty():print("The value is ", q1.get()) # get() will remove the item from the queue.

Đầu ra:

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

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

Ví dụ sau 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 bong bóng.

import queueq1 = queue.Queue()#Addingitems to the queueq1.put(11)q1.put(5)q1.put(4)q1.put(21)q1.put(3)q1.put(10)#using bubble sort on the queuen = q1.qsize()for i in range(n):x = q1.get() # the element is removedfor j in range(n-1):y = q1.get() # the element is removedif x> y :q1.put(y) #the smaller one is put at the start of the queueelse:q1.put(x) # the smaller one is put at the start of the queuex = y # the greater one is replaced with x and compared again with nextelementq1.put(x)while (q1.empty() == False):print(q1.queue[0], end = " ")q1.get()

Đầu ra:

3 4 5 10 11 21

Đảo ngược hàng đợi

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

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

Thí dụ:

import queueq1 = 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 recursionq2dest.put(buffer)return q2destq2dest = 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óm lược:

  • Hàng đợi là một vùng chứa chứa dữ liệu. Có hai loại Hàng đợi, FIFO và LIFO.
  • Đối với FIFO (First in First out Queue), phần tử đi trước sẽ là phần tử xuất hiện đầu tiên.
  • Đối với LIFO (Last in First out Queue), 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 vào bằng phương thức put (item).
  • Để xóa một mục, phương thức get () được sử dụng.