Cách tốt nhất để triển khai hàng đợi trong python là gì?

Trong Phần 4 của loạt bài này, chúng ta hãy đi sâu vào Hàng đợi, một cấu trúc dữ liệu lưu trữ dữ liệu theo cách Nhập trước, Xuất trước [FIFO]. Queue là một cấu trúc dữ liệu trừu tượng, hơi giống với Stacks. Không giống như ngăn xếp, hàng đợi được mở ở cả hai đầu của nó. Trong bài viết này, chúng ta sẽ xem xét cách triển khai và sử dụng cấu trúc dữ liệu hàng đợi trong Python

Để biết thêm thông tin cơ bản về các cấu trúc dữ liệu khác nhau trong Python, hãy xem các bài viết của tôi về cấu trúc dữ liệu Danh sách và Ngăn xếp

Mục lục

• Xếp hàng. Giới thiệu
• Công dụng của hàng đợi
• Triển khai hàng đợi
• hàng đợi thực hành
• Sự kết luận

Hàng đợi - Giới thiệu

Hàng đợi là một cấu trúc dữ liệu tuyến tính trong đó dữ liệu được lưu trữ theo cách Nhập trước, Xuất trước. Trong một hàng đợi, mục nào được thêm vào sớm nhất sẽ bị xóa trước. Mục được thêm gần đây hơn được xóa lần cuối. Một hàng đợi có thể được so sánh với hàng đợi ngoài đời thực

enqueue là thao tác xếp hàng trong đó bạn thêm một mục vào cuối hàng đợi

dequeue là thao tác xếp hàng trong đó bạn xóa một mục khỏi đầu hàng

Công dụng của hàng đợi

• Hệ điều hành - thường duy trì hàng đợi trong khi thực hiện các hoạt động cấp thấp khác nhau như Lập lịch CPU, Lập lịch ổ đĩa, v.v.
• Phần cứng - ngắt phần cứng được xử lý bằng hàng đợi
• Internet - Xử lý lưu lượng truy cập trang web
• Và tất cả các tình huống khác trong đó ưu tiên Nhập trước, Xuất trước phải được thực hiện

Triển khai hàng đợi

Phương pháp xếp hàng

xếp hàng. hàng đợi[]

• Phương thức

  from collections import deque
  class Queue:
  
      def __init__[self]:
          """
          Initializing Queue.
          """
          self.queue = deque[]
  
      def isEmpty[self] -> bool:
          return True if len[self.queue] == 0 else False
  
      def front[self] -> int:
          return self.queue[-1]
  
      def rear[self] -> int:
          return self.queue[0]
  
      def enqueue[self, x: int] -> None:
          self.x = x
          self.queue.append[x]       
  
      def dequeue[self] -> None:
          self.queue.popleft[]
  

  0 thêm một phần tử vào cuối hàng đợi
• Độ phức tạp của thời gian -> O[1]

xếp hàng. Dequeue[]

• Phương thức

  from collections import deque
  class Queue:
  
      def __init__[self]:
          """
          Initializing Queue.
          """
          self.queue = deque[]
  
      def isEmpty[self] -> bool:
          return True if len[self.queue] == 0 else False
  
      def front[self] -> int:
          return self.queue[-1]
  
      def rear[self] -> int:
          return self.queue[0]
  
      def enqueue[self, x: int] -> None:
          self.x = x
          self.queue.append[x]       
  
      def dequeue[self] -> None:
          self.queue.popleft[]
  

  1 loại bỏ một phần tử từ đầu hàng đợi
• Độ phức tạp của thời gian -> O[1]

xếp hàng. Đổi diện[]

• Phương thức

  from collections import deque
  class Queue:
  
      def __init__[self]:
          """
          Initializing Queue.
          """
          self.queue = deque[]
  
      def isEmpty[self] -> bool:
          return True if len[self.queue] == 0 else False
  
      def front[self] -> int:
          return self.queue[-1]
  
      def rear[self] -> int:
          return self.queue[0]
  
      def enqueue[self, x: int] -> None:
          self.x = x
          self.queue.append[x]       
  
      def dequeue[self] -> None:
          self.queue.popleft[]
  

  2 trả về mục phía trước từ hàng đợi
• Độ phức tạp của thời gian -> O[1]

xếp hàng. Ở phía sau[]

• Phương thức

  from collections import deque
  class Queue:
  
      def __init__[self]:
          """
          Initializing Queue.
          """
          self.queue = deque[]
  
      def isEmpty[self] -> bool:
          return True if len[self.queue] == 0 else False
  
      def front[self] -> int:
          return self.queue[-1]
  
      def rear[self] -> int:
          return self.queue[0]
  
      def enqueue[self, x: int] -> None:
          self.x = x
          self.queue.append[x]       
  
      def dequeue[self] -> None:
          self.queue.popleft[]
  

  3 trả về mục phía sau từ hàng đợi
• Độ phức tạp của thời gian -> O[1]

xếp hàng. isEmpty[]

• Phương thức

  from collections import deque
  class Queue:
  
      def __init__[self]:
          """
          Initializing Queue.
          """
          self.queue = deque[]
  
      def isEmpty[self] -> bool:
          return True if len[self.queue] == 0 else False
  
      def front[self] -> int:
          return self.queue[-1]
  
      def rear[self] -> int:
          return self.queue[0]
  
      def enqueue[self, x: int] -> None:
          self.x = x
          self.queue.append[x]       
  
      def dequeue[self] -> None:
          self.queue.popleft[]
  

  4 trả về

  from collections import deque
  class Queue:
  
      def __init__[self]:
          """
          Initializing Queue.
          """
          self.queue = deque[]
  
      def isEmpty[self] -> bool:
          return True if len[self.queue] == 0 else False
  
      def front[self] -> int:
          return self.queue[-1]
  
      def rear[self] -> int:
          return self.queue[0]
  
      def enqueue[self, x: int] -> None:
          self.x = x
          self.queue.append[x]       
  
      def dequeue[self] -> None:
          self.queue.popleft[]
  

  5 nếu hàng đợi trống, ngược lại trả về

  from collections import deque
  class Queue:
  
      def __init__[self]:
          """
          Initializing Queue.
          """
          self.queue = deque[]
  
      def isEmpty[self] -> bool:
          return True if len[self.queue] == 0 else False
  
      def front[self] -> int:
          return self.queue[-1]
  
      def rear[self] -> int:
          return self.queue[0]
  
      def enqueue[self, x: int] -> None:
          self.x = x
          self.queue.append[x]       
  
      def dequeue[self] -> None:
          self.queue.popleft[]
  

  0
• Độ phức tạp của thời gian -> O[1]

Hàng đợi có thể được thực hiện theo nhiều cách khác nhau. Chúng ta hãy xem cách triển khai hàng đợi bằng cách sử dụng danh sách và sử dụng mô-đun

from collections import deque
class Queue:

    def __init__[self]:
        """
        Initializing Queue.
        """
        self.queue = deque[]

    def isEmpty[self] -> bool:
        return True if len[self.queue] == 0 else False

    def front[self] -> int:
        return self.queue[-1]

    def rear[self] -> int:
        return self.queue[0]

    def enqueue[self, x: int] -> None:
        self.x = x
        self.queue.append[x]       

    def dequeue[self] -> None:
        self.queue.popleft[]

1 trong Python

Xếp hàng sử dụng Danh sách

Chúng ta có thể sử dụng các phương thức danh sách

from collections import deque
class Queue:

    def __init__[self]:
        """
        Initializing Queue.
        """
        self.queue = deque[]

    def isEmpty[self] -> bool:
        return True if len[self.queue] == 0 else False

    def front[self] -> int:
        return self.queue[-1]

    def rear[self] -> int:
        return self.queue[0]

    def enqueue[self, x: int] -> None:
        self.x = x
        self.queue.append[x]       

    def dequeue[self] -> None:
        self.queue.popleft[]

2 và

from collections import deque
class Queue:

    def __init__[self]:
        """
        Initializing Queue.
        """
        self.queue = deque[]

    def isEmpty[self] -> bool:
        return True if len[self.queue] == 0 else False

    def front[self] -> int:
        return self.queue[-1]

    def rear[self] -> int:
        return self.queue[0]

    def enqueue[self, x: int] -> None:
        self.x = x
        self.queue.append[x]       

    def dequeue[self] -> None:
        self.queue.popleft[]

3 để triển khai hàng đợi

class Queue:

    def __init__[self]:
        """
        Initializing Queue.
        """
        self.queue = []

    def isEmpty[self] -> bool:
        return True if len[self.queue] == 0 else False

    def front[self] -> int:
        return self.queue[-1]

    def rear[self] -> int:
        return self.queue[0]

    def enqueue[self, x: int] -> None:
        self.x = x
        self.queue.insert[0, x]       

    def dequeue[self] -> None:
        self.queue.pop[]

Xếp hàng sử dụng bộ sưu tập. Deque

Lớp

from collections import deque
class Queue:

    def __init__[self]:
        """
        Initializing Queue.
        """
        self.queue = deque[]

    def isEmpty[self] -> bool:
        return True if len[self.queue] == 0 else False

    def front[self] -> int:
        return self.queue[-1]

    def rear[self] -> int:
        return self.queue[0]

    def enqueue[self, x: int] -> None:
        self.x = x
        self.queue.append[x]       

    def dequeue[self] -> None:
        self.queue.popleft[]

4 từ mô-đun

from collections import deque
class Queue:

    def __init__[self]:
        """
        Initializing Queue.
        """
        self.queue = deque[]

    def isEmpty[self] -> bool:
        return True if len[self.queue] == 0 else False

    def front[self] -> int:
        return self.queue[-1]

    def rear[self] -> int:
        return self.queue[0]

    def enqueue[self, x: int] -> None:
        self.x = x
        self.queue.append[x]       

    def dequeue[self] -> None:
        self.queue.popleft[]

5 của python cũng có thể được sử dụng để triển khai hàng đợi. Phương pháp triển khai hàng đợi này hiệu quả hơn nhiều vì deque cung cấp các thao tác xử lý hàng đợi và hàng đợi nhanh hơn

from collections import deque
class Queue:

    def __init__[self]:
        """
        Initializing Queue.
        """
        self.queue = deque[]

    def isEmpty[self] -> bool:
        return True if len[self.queue] == 0 else False

    def front[self] -> int:
        return self.queue[-1]

    def rear[self] -> int:
        return self.queue[0]

    def enqueue[self, x: int] -> None:
        self.x = x
        self.queue.append[x]       

    def dequeue[self] -> None:
        self.queue.popleft[]

hàng đợi thực hành

Trước tiên hãy thử triển khai hàng đợi trong Python. Sau đó, khi bạn đã hoàn tất việc triển khai, hãy thử giải quyết các sự cố này trên HackerRank và LeetCode

• Đảo ngược hàng đợi - GeekforGeek
• Sắp xếp hàng đợi bằng đệ quy - GeekforGeek
• Đảo ngược các phần tử K đầu tiên của hàng đợi - GeekforGeek
• Triển khai ngăn xếp bằng hàng đợi - GeekforGeek
• Truy vấn có độ dài cố định - HackerRank
• Tham quan xe tải - HackerRank
• Tổng tối đa của tam giác không nhỏ hơn K - LeetCode
• Thiết kế hàng đợi tròn - LeetCode
• Design Circular Dequeue - LeetCode

Sự kết luận

Chúng tôi đã triển khai hàng đợi và học cách sử dụng chúng trong các bài toán thuật toán. Hàng đợi rất không thể thiếu từ quan điểm của hệ điều hành. Họ cũng thường được hỏi về trong các cuộc phỏng vấn

Điều gì là tốt nhất để triển khai hàng đợi trong Python?

Cách tốt nhất để thực hiện hàng đợi là gì?

Hai cách để thực hiện hàng đợi là gì?

Cấu trúc dữ liệu thích hợp nhất để triển khai hàng đợi là gì?