โครงสร้างข้อมูลคิวใน Python คืออะไร?

ดังที่คุณได้ศึกษาไปแล้วเกี่ยวกับความสำคัญของโครงสร้างข้อมูลในบทความก่อนหน้านี้เรามาดูหัวข้อของบทความกันก่อนเช่นโครงสร้างข้อมูลคิว ฉันจะพูดถึงหัวข้อต่อไปนี้:

• ต้องการโครงสร้างข้อมูลคิว
• ตัวอย่างชีวิตประจำวันของคิว
• การสร้างโครงสร้างข้อมูลคิว
• เข้าคิว
• ยกเลิกคิว
• การประยุกต์ใช้คิว

ต้องการโครงสร้างข้อมูลคิว

สมมติว่าคุณต้องการดูหนังวันหนึ่ง ในมัลติเพล็กซ์ตั๋วจะออกตามลำดับก่อน - หลัง - เสิร์ฟก่อนและผู้คนยืนอยู่ข้างหลังกันเพื่อรอการเปิด แล้วคุณจะทำยังไง ?? คุณต้องไปด้านหลังและยืนอยู่ข้างหลังคนสุดท้ายที่รอรับตั๋ว

ที่นี่ผู้คนยืนอยู่ข้างหลังอีกคนและได้รับการบริการตาม เข้าก่อน - ออกก่อน (FIFO) กลไก. การจัดเรียงดังกล่าวเรียกว่า คิว.

ความแตกต่างระหว่างการโอเวอร์โหลดและการลบล้าง

ตัวอย่างชีวิตประจำวันของคิว

ลองพิจารณาตัวอย่างบางส่วนที่เราใช้ประเภทคิวทำงานในชีวิตประจำวัน:

• ระบบตอบรับโทรศัพท์ - ผู้ที่โทรเข้ามาก่อนในแกดเจ็ตของคุณจะเข้าร่วมก่อน
• เครื่องตรวจกระเป๋า - ตรวจสอบสัมภาระที่เก็บไว้ก่อนบนสายพาน
• ยานพาหนะบนสะพานเก็บภาษี - รถที่มาถึงก่อนออกเดินทางก่อน
• คอลเซ็นเตอร์ - ระบบโทรศัพท์จะใช้คิวเพื่อรอให้คนโทรเข้ามาตามลำดับจนกว่าตัวแทนบริการจะว่าง

ตัวอย่างทั้งหมดนี้เป็นไปตาม เข้าก่อน - ออกสุดท้าย กลยุทธ์.

การสร้างโครงสร้างข้อมูลคิว

นอกเหนือจากการดำเนินการเสริมแล้วฉันอาจพูดได้ว่าการดำเนินการหลักที่เป็นไปได้ในคิวคือ:

หนึ่ง. เข้าคิว หรือเพิ่มองค์ประกอบที่ท้ายคิว

2. ยกเลิกคิว หรือลบองค์ประกอบออกจากด้านหน้าของคิว

เริ่มจากการสร้างคิวคลาสใน Python:

class Queue: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ rear = -1 self .__ front = 0

• max_size คือจำนวนองค์ประกอบสูงสุดที่คาดหวังในคิว
• องค์ประกอบของคิวจะถูกเก็บไว้ในรายการหลาม
• ด้านหลังระบุตำแหน่งดัชนีขององค์ประกอบสุดท้ายในคิว
• ด้านหลังเริ่มต้นเป็น -1 เนื่องจากคิวว่างเปล่า
• ด้านหน้าระบุตำแหน่งขององค์ประกอบแรกในคิว
• ด้านหน้าจะถูกนำไปเป็น 0 ในตอนแรกเพราะมันจะชี้ไปที่องค์ประกอบแรกของคิวเสมอ

จัดคิว

ตอนนี้เมื่อคุณพยายามจัดคิวองค์ประกอบในคิวคุณต้องจำประเด็นต่อไปนี้:

• ไม่ว่าจะมีพื้นที่ว่างในคิวหรือไม่เช่นหากด้านหลังเท่ากับ max_size -1
• ด้านหลังจะชี้ไปที่องค์ประกอบสุดท้ายที่แทรกในคิว

แล้วอัลกอริทึมจะเป็นอย่างไร ??

#returns max_size ของคิว def get_max_size (self): return self .__ max_size #returns bool value ไม่ว่าคิวจะเต็มหรือไม่ True if full and False มิฉะนั้น def is_full (self): return self .__ rear == self .__ max_size-1 # แทรก / จัดคิวข้อมูลไปยังคิวหากไม่ได้กำหนดค่า def แบบเต็ม (self, data): if (self.is_full ()): print ('Queue is full. No enqueue possible') else: self .__ rear + = 1 self __elements [self .__ rear] = data # แสดงเนื้อหาทั้งหมดของการแสดงผล def คิว (self): for i in range (0, self .__ rear + 1): print (self .__ elements [i]) # คุณสามารถใช้ ด้านล่าง __str __ () เพื่อพิมพ์องค์ประกอบของออบเจ็กต์ DS ในขณะที่ดีบัก 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 msg

ตอนนี้เมื่อคุณดำเนินการต่อไปนี้:

คิว 1 = คิว (5)

# จัดคิวองค์ประกอบที่จำเป็นทั้งหมด

que1.enqueue (“ A”)

que1.enqueue (“ B”)

que1.enqueue (“ C”)

que1.enqueue (“ D”)

que1.enqueue (“ E”)

que1.display ()

que1.enqueue (“ F”)

พิมพ์ (คิว 1)

เอาท์พุต:

ถึง

ข

ค

ง

คือ

คิวเต็มแล้ว ไม่สามารถจัดคิวได้

ข้อมูลคิว (หน้าไปหลัง): A B C D E

ยกเลิกคิว

ตอนนี้เมื่อคุณแทรก / จัดคิวองค์ประกอบลงในคิวคุณต้องการยกเลิกคิว / ลบออกจากด้านหน้าดังนั้นคุณต้องดูแลสิ่งต่อไปนี้:

• มีองค์ประกอบในคิวเช่นด้านหลังไม่ควรเท่ากับ -1
• ประการที่สองคุณต้องจำไว้ว่าเนื่องจากองค์ประกอบจะถูกลบออกจากด้านหน้าดังนั้นหลังจากการลบส่วนหน้าควรเพิ่มขึ้นเป็นจุดหน้าถัดไป
• ด้านหน้าไม่ควรชี้ท้ายคิวนั่นคือเท่ากับ max_size

แล้วอัลกอริทึมจะเป็นอย่างไร ??

#function เพื่อตรวจสอบว่าคิวว่างหรือไม่ def is_empty (self): if (self .__ rear == - 1 or self .__ front == self .__ max_size): return True else: return False #function เพื่อยกเลิกองค์ประกอบและส่งคืน it def dequeue (self): if (self.is_empty ()): print ('que is already empty') else: data = self .__ elements [self .__ front] self .__ front + = 1 return data #function เพื่อแสดงองค์ประกอบจาก ด้านหน้าไปด้านหลังหากคิวไม่ว่างการแสดงผล def (ตัวเอง): if (ไม่ใช่ self.is_empty ()): สำหรับ i อยู่ในช่วง (self .__ front, self .__ rear + 1): print (self .__ elements [i]) else : พิมพ์ ('คิวว่าง')

ตอนนี้เมื่อคุณดำเนินการต่อไปนี้:

คิว 1 = คิว (5)

# จัดคิวองค์ประกอบที่จำเป็นทั้งหมด

que1.enqueue (“ A”)

que1.enqueue (“ B”)

que1.enqueue (“ C”)

que1.enqueue (“ D”)

que1.enqueue (“ E”)

พิมพ์ (คิว 1)

# จัดคิวองค์ประกอบที่ต้องการทั้งหมด

พิมพ์ (“ Dequeued:“, que1.dequeue ())

พิมพ์ (“ Dequeued:“, que1.dequeue ())

พิมพ์ (“ Dequeued:“, que1.dequeue ())

พิมพ์ (“ Dequeued:“, que1.dequeue ())

พิมพ์ (“ Dequeued:“, que1.dequeue ())

พิมพ์ (“ Dequeued:“, que1.dequeue ())

# แสดงองค์ประกอบทั้งหมดในคิว

que1.display ()

เอาท์พุต:

ข้อมูลคิว (หน้าไปหลัง): A B C D E

ยกเลิกการจัดคิว:

ยกเลิกการจัดคิว: B

ยกเลิกการจัดคิว: ค

ยกเลิกการจัดคิว: D

ยกเลิกการจัดคิว: E

คิวว่างอยู่แล้ว

ยกเลิกการจัดคิว: ไม่มี

คิวว่าง

การประยุกต์ใช้คิว

ณ ตอนนี้คุณเข้าใจพื้นฐานของคิวแล้ว ตอนนี้เพื่อเจาะลึกลงไปเราจะดูแอปพลิเคชันบางอย่าง

• ตัวอย่างที่ 1:

คิวการพิมพ์ใน Windows ใช้คิวเพื่อจัดเก็บงานพิมพ์ที่กำลังดำเนินการและรอดำเนินการทั้งหมด เมื่อเราต้องการพิมพ์เอกสารเราจะออกคำสั่งพิมพ์ทีละคำสั่ง ตามคำสั่งการพิมพ์เอกสารจะเรียงแถวกันในคิวการพิมพ์ เมื่อเครื่องพิมพ์พร้อมเอกสารจะถูกส่งเข้ามาก่อนเพื่อพิมพ์

สมมติว่าคุณออกคำสั่งพิมพ์สำหรับเอกสาร 3 ชุดในลำดับ doc1 ตามด้วย doc2 และ doc3
คิวการพิมพ์จะถูกเติมตามที่แสดงด้านล่าง:

doc-n โดยที่ doc คือเอกสารที่ส่งสำหรับการพิมพ์และ n คือจำนวนหน้าในเอกสาร ตัวอย่างเช่น doc2-10 หมายถึง doc2 จะถูกพิมพ์และมี 10 หน้า นี่คือรหัสที่จำลองการทำงานของคิวการพิมพ์ อ่านโค้ดและสังเกตวิธีใช้คิวในการใช้งานนี้

class Queue: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ rear = -1 self .__ front = 0 def is_full (self): if (self .__ rear = = self .__ max_size-1): return True return False def is_empty (self): if (self .__ front> self .__ rear): return True return False def enqueue (self, data): if (self.is_full ()): print ('Queue is full !!!') else: self .__ rear + = 1 self .__ elements [self .__ rear] = data def dequeue (self): if (self.is_empty ()): print ('Queue is empty! !! ') else: data = self .__ elements [self .__ front] self .__ front + = 1 return data def display (self): for index in range (self .__ front, self .__ rear + 1): print (self .__ elements [index]) def get_max_size (self): return self .__ max_size # คุณสามารถใช้ __str __ () ด้านล่างเพื่อพิมพ์องค์ประกอบของวัตถุ DS ในขณะที่ #debugging def __str __ (self): msg = [] index = self .__ front while (ดัชนี<=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()

เอาท์พุต:

ส่ง doc1-5 เพื่อพิมพ์

ส่ง doc2-3 สำหรับการพิมพ์

ส่ง doc3-6 เพื่อพิมพ์

พิมพ์ doc1-5 แล้ว

เลขที่เหลือ จำนวนหน้าในเครื่องพิมพ์: 7

พิมพ์ doc2-3

เลขที่เหลือ จำนวนหน้าในเครื่องพิมพ์: 4

ไม่สามารถพิมพ์ doc3 จำนวนหน้าที่ไม่เพียงพอในเครื่องพิมพ์

• ตัวอย่างที่ 2:

ลองทำความเข้าใจอีกตัวอย่างหนึ่งซึ่งใช้โครงสร้างข้อมูลคิว ลองทำความเข้าใจโค้ดและบอกได้ไหมว่าฟังก์ชันต่อไปนี้ทำหน้าที่อะไร

1. def สนุก (n):
2. aqueue = คิว (100)
3. สำหรับจำนวนในช่วง (1, n + 1):
4. enqueue (จำนวน)
5. ผลลัพธ์ = 1
6. ในขณะที่ (ไม่ใช่ (aqueue.is_empty ())):
7. num = AQUUE.DEQUEUE ()
8. ผลลัพธ์ * = num
9. พิมพ์ (ผลลัพธ์)

เมื่อฟังก์ชัน fun () ถูกเรียกใช้โดยการส่ง n

jit ใน java คืออะไร

• บรรทัดที่ 2 ถึง 4 จัดคิวองค์ประกอบตั้งแต่ 1 ถึง n
• บรรทัดที่ 5 ถึง 8 จะค้นหาผลคูณขององค์ประกอบเหล่านั้นโดยการยกเลิกการจัดคิวทีละรายการ

ด้วยเหตุนี้เราจึงมาถึงตอนท้ายของบทความโครงสร้างข้อมูลคิวนี้ หากคุณเข้าใจและรันโค้ดด้วยตัวเองสำเร็จคุณจะไม่ใช่มือใหม่ในการจัดคิวโครงสร้างข้อมูลอีกต่อไป

มีคำถามสำหรับเรา? โปรดระบุไว้ในส่วนความคิดเห็นของบทความนี้และเราจะติดต่อกลับโดยเร็วที่สุด

หากต้องการรับความรู้เชิงลึกเกี่ยวกับ Python พร้อมกับแอพพลิเคชั่นต่างๆคุณสามารถลงทะเบียนเพื่อถ่ายทอดสด ด้วยการสนับสนุนตลอด 24 ชั่วโมงทุกวันและการเข้าถึงตลอดชีวิต