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

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

รวมถึง -

1. การดำเนินการเพิ่ม (Push, Enqueue)
2. การดำเนินการลบ (Pop, Dequeue)
3. การแสดงผล/การเดินทาง (Display/Traversing)

ข้อกำหนดเบื้องต้น: List และ List Operations

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

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

Stack

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

การดำเนินการบน Stack -

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

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

ลักษณะเฉพาะของ Stack

• ลำดับการแทรกถูกเก็บรักษา
• อนุญาตให้มีค่าซ้ำใน Stack
• จัดเก็บข้อมูลชนิดเดียวกัน
• มีประโยชน์มากในการ Parsing Operations

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

def isEmpty(stk):
    # ตรวจสอบว่า Stack ว่างหรือไม่
    if stk == []:
        return True
    else:
        return False

def Push(stk, item):
    # อนุญาตให้เพิ่มเข้า Stack
    stk.append(item)
    top = len(stk) - 1

def Pop(stk):
    if isEmpty(stk):  # ตรวจสอบว่า Stack ว่างหรือไม่
        print("Underflow")
    else:
        # อนุญาตให้ลบจาก 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]))

# โค้ดที่รันได้
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 หลายๆ คำสั่ง แนวคิดของการสร้าง Stack เหมือนกันในทั้งสองกรณี

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

ผลลัพธ์

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

Queue

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

การดำเนินการบน Queue

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

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

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

เรายังสามารถเพิ่มฟังก์ชัน peek ได้ คือ การดึงค่าที่ด้านหลัง/ปลายของ Queue

ลักษณะเฉพาะของ Queue

• ลำดับการแทรกถูกเก็บรักษา
• อนุญาตให้มีค่าซ้ำใน Queue
• จัดเก็บข้อมูลชนิดเดียวกัน
• มีประโยชน์มากในการ Parsing CPU task operations

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

# เพิ่มองค์ประกอบเข้า Queue ที่ปลายหลัง
def enqueue(data):
    queue.insert(0, data)

# ลบองค์ประกอบด้านหน้าออกจาก Queue
def dequeue():
    if len(queue) > 0:
        return queue.pop()
    return ("Queue Empty!")

# แสดงองค์ประกอบของ Queue
def display():
    print("Elements on queue are:")
    for i in range(len(queue)):
        print(queue[i])

# โค้ดที่รันได้
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 หลายๆ คำสั่ง แนวคิดของการสร้าง Queue เหมือนกันในทั้งสองกรณี

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

ผลลัพธ์

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

สรุป

ในบทความนี้ เราได้เรียนรู้วิธีการนำ Stack และ Queue data structure ไปปฏิบัติใน Python 3.x (หรือเวอร์ชันก่อนหน้า) คุณสามารถนำอัลกอริทึมเดียวกันไปใช้สร้างโปรแกรมตรวจจับ stack/queue ในภาษาโปรแกรมอื่นได้