Data Structure ใน Python แบบง่าย ๆ (ตอน Stack/Queue)

วันนี้เรามาถึง Data Structure ที่หลาย ๆ คนน่าจะรู้จักกันผ่านเว็บในตำนาน เพื่อนตายของเหล่า Programmer คือ StackOverflow วันนี้เราจะมาทำความรู้จักกับ Stack และ ไหน ๆ ก็ไหน ๆ แล้ว เรามารู้จักกับเพื่อนของมันอย่าง Queue กันไปด้วยเลย

Stack

Stack เป็น Data Structure ประเภทนึงที่มีลักษณะเป็นก้อน ๆ ชั้น ๆ เหมือนขนมชั้น โดยมีกฏอยู่ว่า เราจะเก็บอะไรก็ได้ แต่เวลาเราจะเข้าถึงข้อมูล เราไม่สามารถเข้าถึงเป็น Index ได้ เราจะเข้าถึงได้เฉพาะข้อมูลที่เราเติมอันล่าสุด เราเรียกว่า First In First Out (FIFO) โดยมันจะมี 2 Operation ให้เราใช้งานกันคือ Push และ Pop

Push พูดง่าย ๆ ก็คือ เราอัด Data เข้าไปวางไว้ใน Stack และพอเราจะเอาข้อมูลออกมา เราก็ Pop มันออกมา ดังนั้น Pop ก็คือการเอาข้อมูลที่พึ่ง Push ไปล่าสุดออกมานั่นเอง ง่ายม่ะ

class Stack :
    def __init__ (self) :
        self.stack = []
    
    def push (self, data) :
    	self.stack.append(data)
    
    def pop (self) :
    	if self.is_empty() :
            return None
        else:
    	    return self.stack.pop()
    
    def is_empty (self) :
    	return len(self.stack) == 0
    
    def __len__ (self) :
    	return len(self.stack)

เริ่มจาก Constructer เราเลือกที่จะเก็บข้อมูลด้วย List ธรรมดาเลย เอาจริง ๆ แล้ว Data Structure พวกนี้มันไม่ได้ฟิคนะว่า เราจะ Implement มันออกมายังไง แต่ Concept มันต้องได้เท่านั้นเองว่า ตัวไหน มันทำงานยังไง มีกฏยังไงบ้าง

ส่วน Push Method ก็คือ การที่เรายัดข้อมูลตัวใหม่เข้าไป ซึ่งก็ทำง่าย ๆ เลย เราก็แค่เอาข้อมูลใหม่ไปต่อท้ายไปเลย

def pop (self) :
	if self.is_empty() :
    	return None
    else :
    	poped_val = self.stack[-1]
        self.stack = self.stack[:-1]
        return poped_val
        

ส่วนตัว Pop หรือการเอาตัวที่ Push ไปล่าสุดออกมา ถ้าเราไม่อยากเขียนอะไรเอง เราก็สามารถเรียกคำสั่ง pop ใน List ธรรมดานี่ได้เลยแหละ แต่อย่าลืมว่า ก่อนที่เราจะ pop ได้ เราต้องเช็คก่อนว่า มันมีข้อมูลมั้ย ไม่งั้นมันก็บึ้ม หรือจริง ๆ ถ้าเราอยากเขียนเอง มันก็ทำได้นะ จากตัวอย่างด้านบน เราก็ดึงข้อมูลตัวสุดท้ายออกมา จากนั้น เราไป Update List ของเราให้เอาตัวสุดท้ายออก ในที่นี้เราใช้ Shorthand ในการ Slice Element ออกจาก List เลยง่าย ๆ แล้วก็ โยนค่ากลับไปเป็นอันจบ อย่างที่บอกว่า เราสามารถเขียนได้หลายแบบมาก

def is_empty (self) :
    return len(self.stack) == 0

อันต่อไปที่เราหยิบมาใช้คือ is_empty หรือเป็น Method สำหรับเช็คว่า Stack นี้มีข้อมูลหรือไม่ เผื่อเวลาเราจะ pop ออก เราจะได้เข้ามาเช็คก่อน ในเมื่อเราเก็บข้อมูลด้วย List ทำให้เราสามารถเอาจำนวน Data ผ่านคำสั่ง len ได้ เราก็เช็คไปเลยว่าว่างจริงมั้ย ถ้าว่างให้คืน True กับไป และตรงข้ามให้เอา False กลับไปเท่านั้นเอง

def __len__ (self) :
    return len(self.stack)

และสุดท้าย อยากได้จำนวน Element ใน Stack เราก็ใช้ท่าเดิมจากการเขียน is_empty เลยคือ เราก็เรียก len บน List ธรรมดาได้เลย เราก็จะได้จำนวน Element ออกมาแล้ว

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

Stack Overflow คืออาการที่ Stack มันเต็ม หรือก็คือมันไม่สามารถที่จะ Push ลงไปได้อีกแล้ว ส่วนใหญ่มักจะเกิดจาก Memory มันเต็ม หรือบางทีเราอาจจะจอง Memory ไม่พอในภาษาที่เราจำเป็นที่จะต้องจอง Memory เอง

Queue

ไหน ๆ ก็พูดถึง Stack แล้ว เพื่อน ๆ ของมันก็คือ Queue จำง่าย ๆ ว่าถ้า Stack มัน FIFO เข้าก่อนออกก่อน Queue จะตรงข้ามเป็น First-In-Last-Out (FILO) หรือก็คือ เข้าก่อนออกหลัง เหมือนกับเราไปต่อคิวเลย โดยที่ Operation เราก็จะทำได้ 2 อย่างเหมือนกัน แต่เราเรียกว่า Enqueue และ Dequeue

Enqueue เหมือนกับ Push คือ การที่เราเอาข้อมูลใส่เข้าไปใน Queue ส่วน Dequeue ก็คือตรงข้ามกัน คือ เอาข้อมูลออกมา แต่เป็นข้อมูลที่ Enqueue ลงไปแล้วเก่าที่สุดแค่นั้นเลย

class Queue:
	def __init__ (self) :
    	self.queue = []
    
    def enqueue (self, data) :
    	self.queue.insert(0,data)
    
    def dequeue (self) :
    	if self.is_empty() :
        	return None
        else:
        	return self.queue.pop()
    
    def is_empty (self) :
    	return len(self.queue) == 0
    
    def __len__ (self) :
    	return len(self.queue)

ในการเขียน เราก็จะใช้ท่าเดียวกันเลย เราจะใช้ List เป็นตัวเก็บข้อมูลเหมือนกันเลย อยากให้ดูที่การ Enqueue และ Dequeue เริ่มจาก Dequeue จะเห็นว่า เราใช้วิธีการ Pop เหมือนกับตอน Stack เลย ซึ่ง Pop มันก็คือ การเอา Element ตัวสุดท้ายของ List ออกมา

ดังนั้นเวลาเรา Enqueue แทนที่เราจะใส่ไปเป็นตัวสุดท้ายเป็น Stack เราก็ทำกลับกันเลย ด้วยการยัดใส่ไปในตัวแรกแทน ซึ่งเราสามารถใช้คำสั่ง Insert ใน List ได้เลย โดยที่เราจะยัดมันที่ตำแหน่งแรกเสมอ สุดท้าย เวลาเรา Pop ออกมา เราก็จะเอาตัวสุดท้าย ซึ่งมันเป็นตัวที่อยู่หัว Queue นั่นเอง

def enqueue (self, data) :
	self.queue = [data] + self.queue

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

BONUS: Priority Queue

อันนี้เราอยากจะเสริมให้ Priority Queue จริง ๆ มันก็คือ Queue ที่เราเล่ามาเมื่อกี้เลย แต่มันเพิ่มเรื่องขึ้นมานิดนึงคือ มันเป็น Queue พิเศษแบบชนชั้นอภิสิทธ์ชนที่ให้ตัวที่มีความสำคัญสูงสุดออกก่อนเท่านั้นเอง ทำให้จุดที่เราต้องเพิ่มคือตรง Enqueue

def enqueue (self, data) :
    self.queue.insert(0,data)
    self.queue.sort()

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

สรุป

Stack และ Queue เป็น Data Structure ประเภทนึงที่มีความใกล้เคียงกันอยู่พอสมควร แต่การใช้งานต่างกันเลยทีเดียว เพราะวิธีการทำงานที่ Stack จะใช้หลักการที่เรียกว่า FIFO หรือคือ เข้าก่อนออกก่อน แต่กลับกัน Queue ใช้ FILO ที่เข้าก่อนออกหลัง ที่ในการ Implement นั้นไม่ใช่เรื่องยากเลย เราเลือกใช้ List ช่วยในการ Implement ซึ่งจริง ๆ แล้วอย่างที่เราบอกว่า การ Implement Data Structure พวกนี้ มันไม่ได้ฟิคว่า เราจะ Implement อย่างไร แต่ขอให้เรายึด Concept ไว้ว่ามันทำงานยังไง สุดท้าย เราก็จะเอาไป Implement ในภาษาอะไรก็ได้นั่นเอง