Như bạn đã nghiên cứu về tầm quan trọng của Cấu trúc dữ liệu trong bài viết trước, Chúng ta hãy đi sâu vào chủ đề của bài viết, tức là Cấu trúc dữ liệu hàng đợi. Tôi sẽ thảo luận về các chủ đề sau:
- Cần cho cấu trúc dữ liệu hàng đợi
- Ví dụ về cuộc sống hàng ngày về hàng đợi
- Tạo cấu trúc dữ liệu hàng đợi
- En-queue
- Bỏ xếp hàng
- Các ứng dụng của hàng đợi
Cần cho cấu trúc dữ liệu hàng đợi
Giả sử bạn muốn xem một bộ phim vào một ngày nào đó. Trong chương trình ghép kênh, vé được phát trên cơ sở Người đến trước Người được phục vụ trước và mọi người đứng sau lưng nhau chờ đến lượt. Vậy bạn sẽ làm gì?? Chắc hẳn bạn đã đi ra phía sau và đứng sau người cuối cùng chờ lấy vé.
Ở đây, mọi người đứng sau người kia và họ được phục vụ dựa trên Nhập trước - Xuất trước (FIFO) cơ chế. Sự sắp xếp như vậy được gọi là Xếp hàng.
toán tử phân giải phạm vi trong c ++
Ví dụ về cuộc sống hàng ngày về hàng đợi
Hãy xem xét một số ví dụ mà chúng ta thấy loại hàng đợi hoạt động trong cuộc sống hàng ngày:
- Hệ thống trả lời điện thoại- Người nào gọi trước trên thiết bị của bạn sẽ được tham dự trước.
- Máy kiểm tra hành lý - Kiểm tra Hành lý đã được giữ trước trên băng chuyền.
- Phương tiện qua cầu thu phí - Các phương tiện đến sớm xuất phát trước.
- Trung tâm cuộc gọi - hệ thống điện thoại sẽ sử dụng Hàng đợi, để giữ mọi người gọi cho họ theo thứ tự, cho đến khi đại diện dịch vụ miễn phí.
Tất cả các ví dụ này đều tuân theo Đầu vào - Cuối cùng chiến lược.
Tạo cấu trúc dữ liệu hàng đợi
Ngoài các hoạt động bổ sung, tôi có thể nói rằng các Hoạt động chính có thể có trên Hàng đợi là:
một. En-queue hoặc thêm một phần tử vào cuối hàng đợi.
2. Bỏ xếp hàng hoặc xóa một phần tử khỏi hàng đợi
Bây giờ, hãy bắt đầu bằng cách tạo Hàng đợi lớp trong Python:
class Queue: def __init __ (self, max_size): self .__ max_size = max_size self .__ element = [None] * self .__ max_size self .__ after = -1 self .__ front = 0
- max_size là số phần tử tối đa được mong đợi trong hàng đợi.
- Các phần tử của hàng đợi được lưu trữ trong danh sách python
- phía sau chỉ ra vị trí chỉ mục của phần tử cuối cùng trong hàng đợi.
- Phía sau ban đầu được coi là -1 vì hàng đợi trống
- Front chỉ ra vị trí của phần tử đầu tiên trong hàng đợi.
- Phía trước được coi là 0 ban đầu vì nó sẽ luôn trỏ đến phần tử đầu tiên của hàng đợi
Enqueue
Bây giờ, khi bạn đang cố gắng sắp xếp các phần tử vào Hàng đợi, bạn phải nhớ những điểm sau:
- Cho dù còn trống trong hàng đợi hay không, tức là nếu phía sau bằng max_size -1
- Phần sau sẽ trỏ đến phần tử cuối cùng được chèn trong hàng đợi.
Vậy, thuật toán sẽ là gì ??
#returns max_size of queue def get_max_size (self): tự trả về giá trị bool .__ max_size # trả về giá trị bool cho dù hàng đợi đã đầy hay chưa, True nếu đầy và False nếu không thì def is_full (self): return self .__ back == self .__ max_size-1 # insert / enqueue data vào queue nếu nó chưa đầy đủ def enqueue (self, data): if (self.is_full ()): print ('Hàng đợi đã đầy. Không thể xếp hàng') else: self .__ after + = 1 self. __elements [self .__ after] = data #display tất cả nội dung của hàng đợi def display (self): for i in range (0, self .__ after + 1): print (self .__ Elements [i]) # Bạn có thể sử dụng bên dưới __str __ () để in các phần tử của đối tượng DS trong khi gỡ lỗi def __str __ (self): msg = [] index = self .__ front while (index<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=' '.join(msg) msg='Queue data(Front to Rear): '+msg return msgBây giờ, khi bạn thực hiện như sau:
queue1 = Hàng đợi (5)
#Enueue tất cả (các) phần tử bắt buộc.
queue1.enqueue (“A”)
queue1.enqueue (“B”)
queue1.enqueue (“C”)
queue1.enqueue (“D”)
queue1.enqueue (“E”)
queue1.display ()
queue1.enqueue (“F”)
print (queue1)
Đầu ra:
ĐẾN
B
C
D
LÀ
Hàng đợi đã đầy. Không thể xếp hàng
Dữ liệu hàng đợi (Trước ra sau): A B C D E
De-Queue
Bây giờ, khi bạn đã chèn / xếp hàng các phần tử vào hàng đợi, bạn muốn xếp hàng / xóa chúng từ phía trước, vì vậy bạn cần chú ý những điều sau:
- Có các phần tử trong hàng đợi, tức là phía sau không được bằng -1.
- Thứ hai, bạn cần nhớ rằng vì các phần tử bị xóa từ phía trước, do đó, sau khi xóa phía trước sẽ được tăng lên để trỏ phía trước tiếp theo.
- Phía trước không được trỏ đến cuối hàng đợi, tức là bằng max_size.
Vậy, thuật toán sẽ là gì ??
# function để kiểm tra xem hàng đợi có trống hay không def is_empty (self): if (self .__ after == - 1 hoặc self .__ front == self .__ max_size): return True else: trả về False # function để deque một phần tử và trả về it def dequeue (self): if (self.is_empty ()): print ('hàng đợi đã trống') else: data = self .__ Elements [self .__ front] self .__ front + = 1 trả về data # chức năng để hiển thị các phần tử từ từ trước ra sau nếu hàng đợi không trống def display (self): if (not self.is_empty ()): for i in range (self .__ front, self .__ after + 1): print (self .__ Elements [i]) else : print ('hàng đợi trống')Bây giờ khi bạn thực hiện như sau:
queue1 = Hàng đợi (5)
#Enqueue tất cả (các) phần tử bắt buộc
queue1.enqueue (“A”)
queue1.enqueue (“B”)
queue1.enqueue (“C”)
queue1.enqueue (“D”)
queue1.enqueue (“E”)
print (queue1)
#Dequeue tất cả (các) phần tử bắt buộc
print (“Dequeued:“, queue1.dequeue ())
print (“Dequeued:“, queue1.dequeue ())
print (“Dequeued:“, queue1.dequeue ())
print (“Dequeued:“, queue1.dequeue ())
print (“Dequeued:“, queue1.dequeue ())
print (“Dequeued:“, queue1.dequeue ())
# Hiển thị tất cả các phần tử trong hàng đợi.
queue1.display ()
Đầu ra:
Dữ liệu hàng đợi (Trước ra sau): A B C D E
Dequeued: A
Dequeued: B
Dequeued: C
Dequeued: D
Dequeued: E
hàng đợi đã trống
Dequeued: Không có
hàng đợi trống
Các ứng dụng của hàng đợi
Như bây giờ, bạn đã hiểu cơ bản về hàng đợi. Bây giờ để đi sâu hơn, chúng ta sẽ xem xét một số ứng dụng của nó.
- Ví dụ 1:
In hàng đợi trong Windows sử dụng một hàng đợi để lưu trữ tất cả các lệnh in đang hoạt động và đang chờ xử lý. Khi muốn in tài liệu, chúng ta lần lượt ra lệnh in. Dựa trên các lệnh in, các tài liệu sẽ được xếp vào hàng đợi in. Khi máy in đã sẵn sàng, tài liệu sẽ được gửi trước để in trước.
Giả sử bạn đã phát lệnh in cho 3 tài liệu theo thứ tự doc1, tiếp theo là doc2 và doc3.
Hàng đợi in sẽ được điền như hình dưới đây:
doc-n, trong đó doc là tài liệu được gửi để in và n, là số trang trong tài liệu. Ví dụ: doc2-10 có nghĩa là doc2 sẽ được in và nó có 10 trang. Đây là một đoạn mã mô phỏng hoạt động hàng đợi in. Xem qua mã và quan sát cách hàng đợi được sử dụng trong việc triển khai này.
class Queue: def __init __ (self, max_size): self .__ max_size = max_size self .__ element = [None] * self .__ max_size self .__ after = -1 self .__ front = 0 def is_full (self): if (self .__ after = = self .__ max_size-1): return True return False def is_empty (self): if (self .__ front> self .__ after): trả về True return False def enqueue (self, data): if (self.is_full ()): print ('Hàng đợi đã đầy !!!') else: self .__ after + = 1 self .__ Elements [self .__ after] = data def dequeue (self): if (self.is_empty ()): print ('Hàng đợi trống! !! ') else: data = self .__ Elements [self .__ front] self .__ front + = 1 return data def display (self): cho chỉ mục trong phạm vi (self .__ front, self .__ after + 1): print (self .__ element [index]) def get_max_size (self): return self .__ max_size # Bạn có thể sử dụng __str __ () bên dưới để in các phần tử của đối tượng DS trong khi #debugging def __str __ (self): msg = [] index = self .__ front while (mục lục<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=' '.join(msg) msg='Queue data(Front to Rear): '+msg return msg #function that enqueue are the documents to be printed in Queue named print_queue def send_for_print(doc): global print_queue if(print_queue.is_full()): print('Queue is full') else: print_queue.enqueue(doc) print(doc,'sent for printing') #function that prints the document if number of pages of document is less than #total number of pages in printer def start_printing(): global print_queue while(not print_queue.is_empty()): #here we dequeue the Queue and take the coument that was input first for printing. doc=print_queue.dequeue() global pages_in_printer #the aim of this for loop is to find number of pages of the of document which is doc name followed by “-“ for i in range(0,len(doc)): if(doc[i]=='-'): no_of_pages=int(doc[i+1:]) break if(no_of_pages<=pages_in_printer): print(doc,'printed') pages_in_printer-=no_of_pages print('Remaining no. of pages in printer:', pages_in_printer) else: print('Couldn't print',doc[:i],'. Not enough pages in the printer.') pages_in_printer=12 print_queue=Queue(10) send_for_print('doc1-5') send_for_print('doc2-3') send_for_print('doc3-6') start_printing()Đầu ra:
doc1-5 đã được gửi để in
doc2-3 đã được gửi để in
doc3-6 đã được gửi để in
doc1-5 đã in
Còn lại là không. số trang trong máy in: 7
doc2-3 đã in
Còn lại là không. số trang trong máy in: 4
Không thể in tài liệu 3. Không đủ trang trong máy in
- Ví dụ 2:
Hãy thử hiểu một ví dụ khác sử dụng cấu trúc dữ liệu Hàng đợi. Bạn có thể thử hiểu mã và cho biết chức năng sau đây làm gì?
- def fun (n):
- aqueue = Hàng đợi (100)
- cho num trong phạm vi (1, n + 1):
- enqueue (num)
- kết quả = 1
- while (not (aqueue.is_empty ())):
- num = AQUUE.DEQUEUE ()
- kết quả * = num
- in (kết quả)
Khi hàm fun () được gọi bằng cách chuyển n,
có thể thay đổi trong java
- dòng 2 đến dòng 4 xếp hàng các phần tử từ 1 đến n
- dòng 5 đến dòng 8 tìm tích số của các phần tử đó bằng cách bỏ xếp hàng từng phần tử một
Với điều này, chúng ta đến phần cuối của bài viết Cấu trúc dữ liệu hàng đợi này. Nếu bạn đã hiểu và tự chạy mã thành công, bạn không còn là người mới đối với Cấu trúc dữ liệu hàng đợi.
Có một câu hỏi cho chúng tôi? Vui lòng đề cập đến vấn đề này trong phần bình luận của bài viết này và chúng tôi sẽ liên hệ lại với bạn trong thời gian sớm nhất.
Để có kiến thức chuyên sâu về Python cùng với các ứng dụng khác nhau của nó, bạn có thể đăng ký tham gia trực tiếp với hỗ trợ 24/7 và truy cập trọn đời.