การใช้ List เป็น Stack และ Queues ใน Python

ในบทความนี้ เราจะเรียนรู้เกี่ยวกับโครงสร้าง Stack &Queue ใน Python 3.x หรือก่อนหน้านี้ เราจะพูดถึงการทำงานและการปรับเปลี่ยนโครงสร้างข้อมูลเหล่านี้ -

ซึ่งรวมถึง −

1. การดำเนินการแทรก (พุช, เข้าคิว)
2. การดำเนินการลบ (ป๊อป ดีคิว)
3. การแสดง / การดำเนินการตามขวาง

ข้อกำหนดเบื้องต้น :รายการและรายการการดำเนินงาน

โครงสร้างข้อมูลที่เกี่ยวข้อง :การจัดการรายการ

รูปภาพที่เกี่ยวข้อง

กอง

ในสแต็ก ออบเจ็กต์จะถูกจัดเก็บทับกัน และอ็อบเจ็กต์เหล่านี้จะถูกลบออกในลำดับย้อนกลับของการมาถึง เช่น ปฏิบัติตามแนวคิด LIFO LIFO หมายถึงการจัดประเภท Last in First Out ตามโครงสร้างข้อมูล Stack

การดำเนินงานบนกอง −

• การเติม / การต่อท้ายองค์ประกอบ:สิ่งนี้จะเพิ่มขนาดสแต็กตามจำนวนรายการที่เพิ่ม และการเพิ่มจะเกิดขึ้นที่ด้านบนสุดของสแต็ก
• การลบ / การลบองค์ประกอบ - สิ่งนี้เกี่ยวข้องกับสองเงื่อนไข - หากกองว่างเปล่าไม่มีองค์ประกอบใดที่สามารถลบได้เช่น Underflow เกิดขึ้นใน Stack หรือหาก Stack มีองค์ประกอบบางอย่างอยู่ในนั้น องค์ประกอบที่อยู่ด้านบนจะถูกลบออก . ซึ่งจะช่วยลดขนาดของสแต็กตามจำนวนองค์ประกอบที่นำออก
• Traversing /Displaying - สิ่งนี้เกี่ยวข้องกับการเยี่ยมชมแต่ละองค์ประกอบของสแต็กและแสดงบนหน้าจอ

นอกจากนี้เรายังสามารถแทรกฟังก์ชันเพิ่มเติมของ peek เช่น การดึงค่าที่ด้านบนสุดของ Stack

ลักษณะของกอง

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

โค้ดตัวอย่าง

def isEmpty(stk): # checks whether the stack is empty or not
   if stk==[]:
      return True
   else:
      return False

def Push(stk,item): # Allow additions to the stack
   stk.append(item)
   top=len(stk)-1

def Pop(stk):
   if isEmpty(stk): # verifies whether the stack is empty or not
      print("Underflow")
   else: # Allow deletions from the stack
      item=stk.pop()
      if len(stk)==0:
         top=None
      else:
         top=len(stk)
         print("Popped item is "+str(item))

def Display(stk):
   if isEmpty(stk):
      print("Stack is empty")
   else:
      top=len(stk)-1
      print("Elements in the stack are: ")
      for i in range(top,-1,-1):
         print (str(stk[i]))

# executable code
if __name__ == "__main__":
   stk=[]
   top=None
   Push(stk,1)
   Push(stk,2)
   Push(stk,3)
   Push(stk,4)
   Pop(stk)
   Display(stk)

โค้ดด้านบนใช้ฟังก์ชัน Stack ใน Python 3.x หรือก่อนหน้านี้ เราสามารถสร้างโปรแกรมที่ขับเคลื่อนด้วยเมนูโดยให้ตัวเลือกแก่ผู้ใช้โดยใช้คำสั่ง if-else หลายคำสั่ง แนวคิดของการจัดเฟรมสแต็กยังคงเหมือนเดิมในทั้งสองกรณี

หน้าจอที่แสดงด้านล่างแสดงผลลัพธ์ที่ผลิตโดยโปรแกรมด้านบน นอกจากนี้เรายังสามารถใช้ฟังก์ชัน input() สำหรับระบบอินพุตแบบอิงตามผู้ใช้ (ในที่นี้ ฉันใช้อินพุตแบบคงที่)

ผลลัพธ์

Popped item is 4
Elements in the stack are:
3
2
1

คิว

ในสแต็ก ออบเจ็กต์จะถูกจัดเก็บทีละรายการ และอ็อบเจ็กต์เหล่านี้จะถูกลบออกตามลำดับการมาถึง เช่น ปฏิบัติตามแนวคิด FIFO FIFO หมายถึงการจัดเรียงประเภท First in First Out จะตามมาในโครงสร้างข้อมูลคิว

การดำเนินการตามคิว

• การเพิ่ม / ต่อท้ายองค์ประกอบ - สิ่งนี้จะเพิ่มขนาดคิวตามจำนวนรายการที่เพิ่มและการเพิ่มจะเกิดขึ้นที่ส่วนท้ายเช่นที่ด้านหลังของคิว

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

• Traversing /Displaying - สิ่งนี้เกี่ยวข้องกับการเยี่ยมชมแต่ละองค์ประกอบของสแต็กและแสดงบนหน้าจอ

นอกจากนี้เรายังสามารถแทรกฟังก์ชันเพิ่มเติมของ peek เช่น การดึงค่าที่ส่วนหลัง/ท้ายของคิว

ลักษณะของคิว

• ลำดับการแทรกยังคงอยู่
• อนุญาตให้มีการทำซ้ำในคิว
• ที่เก็บข้อมูลประเภทข้อมูลที่คล้ายคลึงกัน
• มีประโยชน์มากในการแยกวิเคราะห์การทำงานของ CPU

โค้ดตัวอย่าง

#Adding elements to queue at the rear end
def enqueue(data):
   queue.insert(0,data)

#Removing the front element from the queue
def dequeue():
   if len(queue)>0:
      return queue.pop()
   return ("Queue Empty!")

#To display the elements of the queue
def display():
   print("Elements on queue are:");
   for i in range(len(queue)):
      print(queue[i])

# executable code
if __name__=="__main__":
   queue=[]
   enqueue(5)
   enqueue(6)
   enqueue(9)
   enqueue(5)
   enqueue(3)
   print("Popped Element is: "+str(dequeue()))
   display()

โค้ดด้านบนใช้ฟังก์ชัน Queue ใน Python 3.x หรือก่อนหน้านี้ เราสามารถสร้างโปรแกรมที่ขับเคลื่อนด้วยเมนูโดยให้ตัวเลือกแก่ผู้ใช้โดยใช้คำสั่ง if-else หลายคำสั่ง แนวคิดของการจัดกรอบคิวยังคงเหมือนเดิมในทั้งสองกรณี

หน้าจอที่แสดงด้านล่างแสดงผลลัพธ์ที่ผลิตโดยโปรแกรมด้านบน นอกจากนี้เรายังสามารถใช้ฟังก์ชัน input() สำหรับระบบอินพุตแบบอิงตามผู้ใช้ (ในที่นี้ ฉันใช้อินพุตแบบคงที่)

ผลลัพธ์

Popped item is: 5
Elements on queue are:
3
5
9
6

บทสรุป

ในบทความนี้ เราได้เรียนรู้วิธีใช้โครงสร้างข้อมูล Stack &Queue ใน Python 3.x หรือก่อนหน้านี้ คุณสามารถใช้อัลกอริธึมเดียวกันเพื่อใช้โปรแกรมตรวจจับสแต็ก/คิวในภาษาการเขียนโปรแกรมอื่นๆ