Stack กับ Queue ต่างกันอย่างไร
Data Structure ถือเป็นเครื่องมือที่ใช้ในการจัดเก็บ Data Store ที่มีโครงสร้างในคอมพิวเตอร์ เพื่อนำไปใช้งานได้อย่างมีประสิทธิภาพ ซึ่ง Data Structure ที่มีประสิทธิภาพก็มีบทบาทสำคัญในการออกแบบอัลกอริทึมที่ดี…
ถ้าผู้อ่านเรียน Computer Science, Computer Engineer หรือ Related IT field ทั้ง Stack และ Queue ก็ล้วนอยู่ในวิชา Data Structure 101 เช่นกัน แน่นอนครับว่ามันเป็นพื้นฐานมาก ๆ ในการเรียนรู้ และทำความเข้าใจใน Data Structure เพื่อที่จะให้ผู้เรียนนำสิ่งเหล่านี้นำไปต่อยอดต่อไป แต่จากประสบการณ์ที่ผ่านมาของตัวผู้เขียนเอง จะเห็นบ่อย ๆ เวลาถามว่า Stack กับ Queue คืออะไร แล้วต่างกันอย่างไร หลายครั้งจะพบว่าเป็นคำถามที่ กระดาษคำตอบนั้น… “ว่างเปล่า” ก็เลยเขียนบทความเรื่องนี้ขึ้นมาเพื่อทบทวนตัวเองไปในตัวด้วย
STACK
Stack เป็น Abstract Data Type (ADT) โดยทั่วไป ADT จะเป็นวิธีการจำแนกโครงสร้างข้อมูลตามวิธีการใช้งาน (classifying data structures) โดยที่ไม่ต้องระบุว่าจะต้องนำ Data Structure ชุดนี้ไปใช้อย่างไร ซึ่ง Stack อยู่บนพื้นฐานของหลักการแบบ Last In First Out(LIFO) หมายความว่าสิ่งที่ถูกแทรกเข้ามาล่าสุดจะถูกลบออกก่อน ลองจินตนาการว่าคุณมีไพ่กองอยู่สำรับนึง หรือมีกระดาษกองทับซ้อนกันอยู่ เวลาจะเอาออกก็ต้องเอาออกจากข้างบนก่อนนั้นเอง…
Operation
มาดูกันว่าคำสั่งพื้นฐานของ Stack มีอะไรกันบ้าง
- push() − เป็นการเพิ่ม element ลงไปในส่วนบนสุดของ Stack หรือ Pushing (storing)
- pop() − เป็นการลบ element ออกจากส่วนบนที่สุดของ Stack หรือ Removing (accessing)
- peek() − เป็นการดู element ที่อยู่บนสุดของ Stack
- isFull() − เป็นการตรวจสอบว่า Stack เต็ม หรือไม่
- isEmpty() − เป็นการตรวจสอบว่า Stack ว่าง หรือไม่
Implementation
Stack สามารถนำไปใช้ได้หลากหลายวิธีขึ้นอยู่กับการใช้งานเช่น Array หรือ LinkedList ซึ่งจะได้ประโยชน์เรื่อง Complexity โดยมี BigO เป็น O(1) จากการเพิ่ม และลบ จากจุดเริ่มต้น ตัวอย่าง Implement Stack via Java LinkList
QUEUE
Queue เป็น Linear Data Structure ซึ่งค่อนข้างจะคล้ายกับ Stack แต่ไม่ได้เหมือนกันซะทีเดียว Queue จะเปิดปลายทั้งหัว และท้าย ปลายด้านนึงจะใช้ในการแทรกข้อมูล (Enqueue) ปลายอีกด้านนึงจะใช้เพื่อทำการนำข้อมูลออก หรือลบข้อมูล (Dequeue)
ในการ Dequeue data ตัว Pointer จะชี้ไปที่ “Front” และ Enqueing data ตัว Pointer จะชี้ไปที่ “Rear”
Queue อยู่บนพื้นฐานของหลักการแบบ First In First Out(FIFO) หมายความว่าอะไรที่เข้าไปก่อน ก็จะออกก่อน ลองจินตนาการเช่น ถนนเลนเดียว เมื่อคุณจอดติดไฟแดงอยู่คันแรก คันต่อ ๆ มาก็มาติดตามหลังคุณ เมื่อไฟเขียว คุณก็จะได้ไปก่อน หรือต่อคิวรับไมโลฟรี ถ้าคุณมาต่อคิวก่อน คุณก็ได้ไปก่อน อันนี้จำง่าย ๆ ว่าตามคิวนั่นเอง
Operation
มาดูกันว่าคำสั่งพื้นฐานของ Queue มีอะไรกันบ้าง
- enqueue() − เป็นการเพิ่ม Data ลงไปใน Queue.
- dequeue() − เป็นการนำออก หรือลบ Data ใน Queue
- peek() − เป็นการดู Data ที่อยู่ตำแหน่ง Front ของ Queue โดยจะไม่ไปทำการนำค่า หรือลบค่าออกไป
- isFull() − เป็นการตรวจสอบว่า Queue เต็ม หรือไม่
- isEmpty() − เป็นการตรวจสอบว่า Queue ว่าง หรือไม่
Implementation
Queue สามารถนำไปใช้ได้หลากหลายวิธีขึ้นอยู่กับการใช้งานเช่น Array หรือ LinkedList คล้ายกันกับ Stack เลย โดยที่ Queue ไม่ว่าจะเป็นการ Enqueue หรือ Dequeue ก็ตามจะได้ Complexity เป็น O(1)
ตัวอย่างการ Implement Queue สามารถไปดูต่อได้ที่นี่
Conclusion
Stack เป็น LIFO พวก Element ต่าง ๆ จะถูกเพิ่มจากข้างบนสุด และตอนนำออกก็นำออกจากข้างบนสุด การเพิ่มจะเรียกว่า Push การนำออกเรียกว่า Pop ใน Stack จะมี Pointer อยู่ตัวนึง เพื่อเข้าถึงด้านบนสุดซึ่งจะชี้ไปยังตัวสุดท้ายของ List
Queue เป็น FIFO พวก Element ต่าง ๆ จะถูกเพิ่มจากตัวแรกสุดของ Element และ Element ตัวที่อยู่ด้านหน้าสุดจะเป็นตัวที่ถูกลบเป็นตัวแรก การเพิ่มจะเรียกว่า Enqueue การนำออกเรียกว่า Dequeue ใน Queue จะมี Pointer อยู่ 2 ตัว ตัวนึงจะชี้ด้านหน้า (Front, Head) อีกตัวนึงจะชี้ไปที่ตัวที่ล่าสุด (Rear, Tail)
ก็หวังว่าผู้อ่านจะได้ทบทวนเป็นการอ่านฆ่าเวลากันบ้างนะครับ ตรงไหนผิดพลาดประการใด รบกวนชี้จุดและบอกกล่าวได้เลย จะได้นำมาแก้ไขต่อไปครับ
