0. Mục tiêu học tập

Ngăn xếp và hàng đợi là các kiểu dữ liệu phổ biến trong lập trình. Từ góc độ cấu trúc dữ liệu, ngăn xếp và hàng đợi cũng là các bảng tuyến tính với các phép toán hạn chế. rất khác so với các bảng tuyến tính. Phần này sẽ giới thiệu định nghĩa về hàng đợi và cách triển khai khác nhau của chúng cũng như đưa ra một số ứng dụng thực tế của hàng đợi.
Sau khi học xong phần này bạn cần nắm vững những nội dung sau:

• Các khái niệm cơ bản về hàng đợi và các phương pháp triển khai khác nhau
• Việc triển khai và độ phức tạp về thời gian của các hoạt động xếp hàng cơ bản
• Triển khai các thuật toán phức tạp bằng các thao tác cơ bản trên hàng đợi

1. Khái niệm cơ bản về hàng đợi

1.1 Khái niệm cơ bản về hàng đợi

Hàng đợi (Hàng đợi) là một danh sách tuyến tính trong đó các thao tác chèn và xóa bị giới hạn ở cả hai đầu của chuỗi (các phần tử mới được chèn từ một phân đoạn và các phần tử hiện có chỉ có thể bị xóa khỏi đầu kia đối với hàng đợi, phần cuối cho phép chèn). của các phần tử được gọi là phần đuôi của hàng đợi (ở phía sau) và phần cho phép loại bỏ các phần tử được gọi là phần đầu của hàng đợi (đằng trước).
Trong hàng đợi, thứ tự dữ liệu đến rất quan trọng. Phần tử mới được thêm vào phải ở cuối hàng đợi và phần tử ở trong hàng đợi lâu nhất sẽ ở phía trước. Nguyên tắc sắp xếp này được gọi là vào trước, ra trước (.vào trước ra trước,FIFO), hoặc cuối cùng vào, cuối cùng ra (vào sau ra trước, LILO).
Ví dụ thực tế về việc xếp hàng có thể được nhìn thấy ở khắp mọi nơi. Việc xếp hàng mà chúng ta cần dùng bữa trong cuộc sống là một ví dụ thực tế về việc xếp hàng. Người đầu tiên vào hàng có thể ăn trước, trong khi những người đến sau phải xếp hàng chờ. cuối hàng đợi. Giả sử hàng đợi là Q = ( a 0 , a 1 , … , an ) Q=(a_0, a_1, …, a_n)Q=(a0,a1,…,an), thì phần tử đầu của hàng đợi là a 0 a_0a0, an a_nan Nó là phần tử đuôi của hàng đợi. Các phần tử trong hàng đợi là a 0 , a 1 , … , an a_0, a_1, …, a_na0,a1,…,an Thứ tự xếp hàng (xếp hàng), xếp hàng (xếp hàng) chỉ có thể thoát theo thứ tự này. Thành phần đứng đầu của đội là người đầu tiên rời khỏi đội (xếp hàng) và chỉ a 0 , a 1 , … , an − 1 a_0, a_1, …, a_{n-1}a0,a1,…,an−1 chỉ có thể thoát khỏi hàng đợi sau a_nan . Hình dưới đây là một ví dụ về hàng đợi đơn giản:

Bằng cách quan sát thứ tự các phần tử được thêm và xóa, bạn có thể nhanh chóng hiểu được ý tưởng đằng sau hàng đợi. Hình dưới đây cho thấy quá trình enqueue và dequeue của các phần tử hàng đợi. Thứ tự chèn và thứ tự loại bỏ các phần tử trong hàng đợi hoàn toàn giống nhau.

1.2 Kiểu dữ liệu trừu tượng hàng đợi

Ngoài các thao tác chính (xếp hàng và giải hàng đợi), hàng đợi còn có các thao tác phụ như khởi tạo, phán đoán hàng trống và xác định độ dài hàng đợi. Cụ thể, kiểu dữ liệu trừu tượng của hàng đợi được định nghĩa như sau:
Hàng đợi ADT:
 Đối tượng dữ liệu: D = ai ∣ ai ∈ D ata T ype , i = 1 , 2 , . , n , n ≥ 0 D={a_i|a_i∈DataType, i=1,2,...,n, n\geq0}D=ai∣ai∈DataType,i=1,2,...,n,n ≥0
 Mối quan hệ dữ liệu: R = < ai , ai + 1 > ∣ ai , ai + 1 ∈ D , i = 1 , 2 , . R={|a_i,a_{i+1}∈D,i=1,2,...,n-1}R=∣ai,ai+1∈D,i=1,2,...,n−1
       a 1 a_1a1 là phần tử đầu của đội, a_nan là phần tử đuôi của đội
 Các thao tác cơ bản:
  1. nó(): khởi tạo hàng đợi
   Tạo một hàng đợi trống
  2. size(): Tìm và trả về số n phần tử có trong hàng đợi
   Nếu hàng đợi trống, trả về số nguyên 0
  3. isempty(): Xác định hàng đợi có trống không
   Xác định xem các phần tử có được lưu trữ trong hàng đợi hay không
  4. enqueue(data): enqueue
   Chèn dữ liệu phần tử vào cuối hàng đợi
  5. dequeue(): dequeue
   Xóa và trả về phần tử cuối cùng của hàng đợi
  4. head(): Lấy phần tử head của team
   Trả về phần tử đầu của hàng đợi nhưng không xóa phần tử

1.3 Kịch bản ứng dụng hàng đợi

Hàng đợi có nhiều tình huống ứng dụng khác nhau, chẳng hạn như:

• Với tiền đề là các công việc có cùng mức độ ưu tiên, hệ điều hành sẽ sắp xếp các công việc theo thứ tự chúng đến;
• Các lần nhấn phím được đưa vào bộ đệm giống như hàng đợi để các ký tự tương ứng được hiển thị theo đúng thứ tự;
• Mô phỏng hàng đợi trong thế giới thực;
• đa chương trình;
• Truyền dữ liệu không đồng bộ;

Ngoài các ứng dụng trên, chúng ta sẽ thấy hàng đợi được sử dụng làm cấu trúc dữ liệu phụ trợ cho nhiều thuật toán trong các nghiên cứu tiếp theo của chúng ta.

2. Thực hiện hàng đợi

Giống như bảng tuyến tính, hàng đợi cũng có hai cách biểu diễn lưu trữ: lưu trữ tuần tự và lưu trữ theo chuỗi.

2.1 Triển khai hàng đợi tuần tự

Tương tự như ngăn xếp tuần tự, cấu trúc lưu trữ tuần tự của hàng đợi sử dụng một tập hợp các đơn vị lưu trữ có địa chỉ liên tiếp để lưu trữ tuần tự từ đầu hàng đợi đến cuối hàng đợi và yêu cầu sử dụng hai con trỏ. đằng trước Và ở phía sau Cho biết vị trí của phần tử đầu hàng và phần tử đuôi hàng đợi tương ứng. Khi khởi tạo một hàng đợi trống,trước=sau=0, khi phần tử được xếp vào hàng đợi,phía sau cộng 1và khi phần tử bị loại bỏ,phía trước cộng 1, như hình dưới đây:

Từ ví dụ trên, có thể thấy rõ rằng không gian trước phần đầu của hàng đợi bị lãng phí. Để giải quyết vấn đề này, chúng ta có thể giả sử rằng hàng đợi tuần tự là không gian vòng và coi phần tử cuối cùng và phần tử đầu tiên là liên tục. , như thể hiện trong hình dưới đây:

Như có thể thấy từ hình trên, khi hàng đợi đầy và khi hàng đợi trống, cóphía trước=phía sau, nên nó không thể vượt qua phía trước==phía sau để xác định xem hàng đợi đã đầy hay chưa. Có hai giải pháp cho vấn đề này: 1) Đặt cờ để cho biết liệu có không gian trống trong hàng đợi hay không; 2) Loại bỏ một không gian phần tử, nghĩa là khi nào đằng trước Con trỏ đang ở ở phía sau Chữ số tiếp theo của con trỏ là ((phía sau+1)%max_size=phía trước) Hàng đợi đã đầy. Việc triển khai sau đây sử dụng tùy chọn thứ hai.
Tương tự, hàng đợi tuần tự có thể có độ dài cố định và độ dài động. Khi hàng đợi đầy, hàng đợi tuần tự có độ dài cố định sẽ đưa ra một ngoại lệ đầy đủ trong ngăn xếp và hàng đợi tuần tự động sẽ tự động áp dụng cho không gian trống.

2.1.1 Khởi tạo hàng đợi

Việc khởi tạo hàng đợi tuần tự yêu cầu 4 thông tin:xếp hàng Danh sách được sử dụng để lưu trữ các phần tử dữ liệu,kích thước tối đa để lưu trữ xếp hàng độ dài tối đa của danh sách và đằng trước Và ở phía sau Dùng để ghi chỉ số của phần tử đầu và phần tử đuôi tương ứng:

Hàng đợi lớp: def __init__(self, max_size=5): self.max_size = max_size self.queue = [Không] * self.max_size self.front = 0 self.rear = 0

2.1.2 Tìm độ dài hàng đợi

bởi vì đằng trước Và ở phía sau Chúng dùng để ghi chỉ số của phần tử đầu và phần tử đuôi tương ứng nên chúng ta có thể dễ dàng tính toán độ dài của hàng đợi, đồng thời chúng ta cần coi hàng đợi là một hàng đợi hình tròn;đằng trước có thể lớn hơn ở phía sau, không thể truyền trực tiếp phía sau phía trước, chúng ta cần sử dụng công thức tính toán để giải bài toán này:
( phía sau − phía trước + kích thước tối đa ) % kích thước tối đa (phía sau+max_size) % max_size(phía sau−phía trước+max_size)%max_size

Python Việc thực hiện như sau:

kích thước def(self): return (self.rear-self.front+self.max_size) % self.max_size

2.1.3 Hàng đợi trống

theo đằng trước Và ở phía sau Giá trị có thể dễ dàng xác định xem hàng đợi có trống hay không:

def isempty(self): return self.rear==self.front

2.1.4 Xác định hàng đợi đã đầy

theo đằng trước Và ở phía sau Giá trị có thể dễ dàng xác định xem có chỗ trống trong hàng đợi hay không:

def isfull(self): return ((self.rear+1) % self.max_size == self.front)

2.1.5 Tham gia nhóm

Khi tham gia hàng đợi, trước tiên bạn cần xác định xem có chỗ trống trong hàng đợi hay không, sau đó tùy thuộc vào việc hàng đợi là hàng đợi tuần tự có độ dài cố định hay hàng đợi tuần tự động, thao tác nối sẽ hơi khác một chút:
[Hoạt động Enqueue của hàng đợi tuần tự có độ dài cố định] Nếu hàng đợi đầy, một ngoại lệ sẽ được đưa ra:

def enqueue(self, data): if not self.isfull(): self.queue[self.rear] = data self.rear = (self.rear+1) % self.max_size else: raise IndexError("Ngoại lệ hàng đợi đầy đủ ")

[Hoạt động Enqueue của hàng đợi tuần tự động] Nếu hàng đợi đầy, trước tiên hãy áp dụng không gian mới, sau đó thực hiện thao tác enqueue:

def thay đổi kích thước(self): new_size = 2 * self.max_size new_queue = [Không có] * new_size cho i trong phạm vi(self.max_size): new_queue[i] = self.queue[i] self.queue = new_queue self.max_size = new_size def enqueue(self, data): if self.isfull(): self.resize() self.queue[self.rear] = data self.rear = (self.rear+1) % self.max_size

Độ phức tạp về thời gian của việc xếp hàng là O ( 1 ) O(1)O(1). Cần lưu ý ở đây rằng mặc dù khi hàng đợi chuỗi động đã đầy, trước tiên các phần tử trong hàng đợi ban đầu cần được sao chép sang hàng đợi mới, sau đó các phần tử mới được thêm vào. Tuy nhiên, hãy tham khảo phần giới thiệu các thao tác nối thêm bảng tuần tự trong. "Bảng tuần tự và việc triển khai hoạt động của nó", bởi vì N Tổng thời gian của các hoạt động xếp hàng T ( n ) T(n)T(n) tỷ lệ thuận với O ( n ) O(n)O(n), do đó độ phức tạp thời gian phân bổ của ngăn xếp hàng đợi có thể được coi là O ( 1 ) O(1)O(1).

2.1.6 Dequeue

Nếu hàng đợi không trống, hãy xóa và trả về phần tử head:

def dequeue(self): if not self.isempty(): result = self.queue[self.front] self.front = (self.front+1) % self.max_size trả về kết quả khác: raise IndexError("Empty Queue Exception ")

2.1.7 Tìm thành phần đứng đầu của đội

Nếu hàng đợi không trống, trả về phần tử head:

def head(self): if not self.isempty(): result = self.queue[self.front] trả về kết quả khác: raise IndexError("Ngoại lệ hàng đợi trống")

2.2 Triển khai hàng đợi chuỗi

Một cách biểu diễn lưu trữ khác của hàng đợi là sử dụng cấu trúc lưu trữ chuỗi, do đó nó còn thường được gọi là hàng đợi chuỗi, trong đó xếp hàng Hoạt động được thực hiện bằng cách chèn các phần tử vào cuối danh sách liên kết.xếp hàng Hoạt động được thực hiện bằng cách xóa nút khỏi phần đầu.

2.2.1 Nút hàng đợi

Việc triển khai nút của hàng đợi không khác gì với danh sách liên kết:

lớp Node: def __init__(self, data=None): self.data = data self.next = Không có def __str__(self): return str(self.data)

2.2.2 Khởi tạo hàng đợi

Trong hàm khởi tạo của hàng đợi, đặt con trỏ đầu của nó đằng trước Và ở phía sau cả hai đều trỏ đến Không cóvà khởi tạo độ dài hàng đợi:

Hàng đợi lớp: def __init__(self): self.front = Không có self.rear = Không có self.num = 0

2.2.3 Tìm độ dài hàng đợi

trở lại kích cỡ Giá trị của được sử dụng để tìm độ dài của hàng đợi, nếu không có kích cỡ thuộc tính, bạn cần duyệt qua toàn bộ danh sách liên kết để có được độ dài hàng đợi:

kích thước def (tự): trả về self.num

2.2.4 Hàng đợi trống

Bạn có thể dễ dàng xác định xem hàng đợi có trống hay không dựa trên độ dài của hàng đợi:

def isempty(self): trả về self.num <= 0

2.2.5 Tham gia nhóm

Khi vào hàng đợi, chèn một phần tử mới vào cuối hàng đợi và con trỏ cuối của hàng đợi cần phải là ở phía sau Trỏ tới phần tử mới Nếu hàng đợi trống thì con trỏ đầu của hàng đợi phải là. đằng trước Cũng trỏ đến yếu tố này:

def enqueue(self, data): node = Node(data) nếu self.front là Không có: self.rear = node self.front = self.rear else: self.rear.next = node self.rear = node self.num += 1

2.2.6 Dequeue

Nếu hàng đợi không trống, hãy xóa và trả lại phần tử đầu và cập nhật con trỏ đầu. đằng trước Trỏ tới nút kế thừa của nút đầu nhóm ban đầu. Nếu phần tử dequeue là nút cuối cùng trong nhóm đuôi, hãy cập nhật con trỏ đuôi nhóm. ở phía sau:

def dequeue(self): if self.isempty(): raise IndexError("Ngoại lệ hàng đợi trống") result = self.front.data self.front = self.front.next self.num -= 1 if self.isempty() : self.rear = kết quả trả về self.front

2.2.7 Tìm thành phần đứng đầu của đội

Nếu hàng đợi không trống, trả về phần tử head:

def head(self): if self.isempty(): raise IndexError("Ngoại lệ hàng đợi trống") result = kết quả trả về self.front.data

2.3 So sánh các cách triển khai hàng đợi khác nhau

Việc so sánh các cách triển khai khác nhau của hàng đợi cũng tương tự như các cách triển khai khác nhau của ngăn xếp. Bạn có thể tham khảo "Ngăn xếp và triển khai hoạt động của nó".

3. Ứng dụng xếp hàng

Tiếp theo, trước tiên chúng tôi kiểm tra hàng đợi được triển khai ở trên để xác minh tính hiệu quả của các hoạt động, sau đó sử dụng các hoạt động cơ bản đã triển khai để giải quyết các vấn đề thuật toán thực tế.

3.1 Ứng dụng hàng đợi tuần tự

Đầu tiên khởi tạo một hàng đợi tuần tự xếp hàngvà sau đó kiểm tra các hoạt động liên quan:

# Khởi tạo một hàng đợi có độ dài tối đa là 5 q = Queue(5) print('Hàng đợi trống?', q.isempty()) for i in range(4): print('Các phần tử được xếp hàng đợi:', i) q. enqueue(i) print('Queue full?', q.isfull()) print('Queue head element:', q.head()) print('Queue length is:', q.size()) trong khi không q.isempty(): print('Phần tử Dequeue: ', q.dequeue())

Kết quả đầu ra của chương trình thử nghiệm như sau:

Hàng đợi trống? Các phần tử sắp xếp thực sự: 0 Các phần tử xếp hàng: 1 Các phần tử xếp hàng: 2 Các phần tử xếp hàng: 3 # Một khoảng trống bị loại bỏ trong hàng đợi, do đó có 4 phần tử trong hàng đợi, nghĩa là hàng đợi đã đầy. phần tử: 0 Độ dài hàng đợi là: 4 Phần tử Dequeue: 0 Phần tử Dequeue: 1 Phần tử Dequeue: 2 Phần tử Dequeue: 3

3.2 Ứng dụng hàng đợi chuỗi

Đầu tiên khởi tạo hàng đợi chuỗi xếp hàngvà sau đó kiểm tra các hoạt động liên quan:

# Khởi tạo một hàng đợi mới q = Queue() print('Hàng đợi trống?', q.isempty()) for i in range(4): print('Enqueued element:', i) q.enqueue(i) print( 'Phần tử đầu hàng đợi:', q.head()) print('Độ dài hàng đợi là:', q.size()) trong khi không phải là q.isempty(): print('Phần tử Dequeue:', q.dequeue())

Kết quả đầu ra của chương trình thử nghiệm như sau:

Hàng đợi trống?

3.3 Triển khai các thuật toán phức tạp bằng các thao tác xếp hàng cơ bản

[1] Xét bài toán vành Josephus cổ điển,N Các cá nhân tạo thành một vòng tròn, bắt đầu từ vòng đầu tiên 1 Các cá nhân bắt đầu đếm, người đầu tiên tôi Một người sẽ bị loại, quá trình trên được lặp lại cho đến khi chỉ còn lại một người và những người còn lại sẽ bị loại.
Chúng tôi sử dụng hàng đợi để mô phỏng một vòng, như trong hình bên dưới. Bắt đầu từ đầu hàng đợi, người ở đầu hàng đợi sẽ bị xóa khỏi hàng đợi và ngay lập tức được đưa vào cuối hàng đợi. người đó sẽ đợi cho đến khi anh ta lại đến cuối hàng. Trong dequeue và enqueue m-1 Sau một thời gian, người đứng đầu hàng đã ra ngoài (tức là người đứng đầu hàng đã ra ngoài) tôi người), và sau đó một vòng mới của trò chơi bắt đầu; điều này được lặp lại cho đến khi chỉ còn một người trong hàng đợi (kích thước của hàng đợi là 1 ).

def Josephus(name_list, m): queue = Queue() cho tên trong name_list: queue.enqueue(name) while queue.size() > 1: for i in range(m-1): queue.enqueue(queue.dequeue ()) queue.dequeue() return queue.head() # n=6, m=5 result = Josephus(["A", "B", "C", "D", "E", "F"], 5) print('Người sống sót', result)

Đầu ra của chương trình như sau:

Người sống sót là A

Liên kết liên quan

Các khái niệm cơ bản về bảng tuyến tính
Bảng tuần tự và cách thực hiện hoạt động của nó
Danh sách liên kết đơn và cách thực hiện thao tác của nó
Stack và việc triển khai hoạt động của nó