สร้าง Stack ด้วยภาษา Java (Stack Array Implementation)

จากบล็อกที่แล้วเขียนถึงเรื่อง Linked List สำหรับบล็อกนี้จะเขียนเกี่ยวกับโครงสร้างข้อมูลแบบง่ายอีกแบบหนึ่งที่น่าจะได้เรียนหรือเคยได้ยินมาก่อนบ้างนั่นคือ Stack

Stack ก็เป็นโครงสร้างข้อมูลอีกแบบหนึ่งที่สามารถช่วยให้สามารถจัดเก็บข้อมูลได้ และสามารถนำไปประยุกต์ใช้กับโปรแกรมอื่นๆได้ เช่น Balancing Symbols, Postfix Expression Calculator เป็นต้น

หลักการทำงานของ Stack เป็นหลักการง่ายๆคือ ข้อมูลที่เข้าหลังสุดจะถูกนำออกก่อน (Last Input First Output: LIFO)

โอเปอเรชันที่สำคัญของ Stack มีอยู่ 3 โอเปอเรเตอร์ ประกอบด้วย

1. Push คือโอเปอเรชันที่ใช้สำหรับการเพิ่มข้อมูลไปยัง Stack
2. Pop คือโอเปอเรชันที่ใช้สำหรับการลบข้อมูลจาก Stack
3. Peek คือโอเปอเรชันที่ใช้สำหรับการดูข้อมูลที่ตำแหน่งบนสุดของ Stack นั่นคือดูข้อมูลล่าสุดที่เพิ่มเข้าไป

ในการสร้างสแตกสามารถสร้างได้จากอาร์เรย์ก็ได้ หรือสามารถใช้ Linked List ก็ได้ แต่สำหรับบล็อกนี้จะแสดงการสร้างสแตกโดยใช้อาร์เรย์

อันดับแรกก็สร้าง class Stack ขึ้นมาก่อน โดยมี Attribute ของคลาสดังรูป

อธิบายรูปคือ 

• บรรทัดที่ 3 คือขนาดของสแตกโดยมีค่าเริ่มต้นอยู่ที่ 100 แต่สามารถกำหนดเองได้
• บรรทัดที่ 4 คือตำแหน่งของข้อมูลที่เป็น top of stack
• บรรทัดที่ 5 คืออาร์เรย์ที่ใช้เก็บข้อมูลเป็นชนิดข้อมูลใดก็ได้ เช่น int, float, long, double, char, String

ต่อไปเป็นการสร้างเมธอดที่จำเป็นต้องใช้ซึ่งประกอบด้วย

1. Stack() -> constructor method เขียนโค๊ดได้ดังนี้

อธิบายรูปคือ

• บรรทัดที่ 7-9 เป็นการสร้าง constructor method โดยไม่มีพารามิเตอร์ และสร้างอารย์ของ Object ให้มีขนาดเท่ากับ maxStackSize
• บรรทัดที่ 11-14 เป็นการสร้าง constructor method โดยรับพารามิเตอร์หนึ่งค่าคือ size ขนาดของสแตกที่ต้องการ แล้วสร้างอารย์ของ Object ให้มีขนาดเท่ากับ size ที่รับเข้ามา และกำหนดค่า size ให้กับ maxStackSize

2. initializeValueStack() เป็นเมธอดสำหรับกำหนดค่าเริ่มต้นให้กับอาร์เรย์ เขียนโค๊ดได้ดังนี้

อธิบายรูปคือ

• บรรทัดที่ 17-18 เป็นการกำหนดค่า null ให้กับอาร์เรย์ทั้งหมดที่จะใช้เก็บข้อมูล
• บรรทัดที่ 19 กำหนดให้ตำแหน่งของข้อมูล top of stack เท่ากับศูนย์

3. isEmpty() เป็นเมธอดสำหรับตรวจสอบว่าสแตกไม่มีข้อมูลใดๆ เลยใช่หรือไม่ โดยมี return type คือ boolean เขียนโค๊ดได้ดังนี้

อธิบายรูปคือ

• บรรทัดที่ 23 คือการรีเทิร์นค่าที่ได้จากการตรวจสอบเงื่อนไข stackTop == 0 ถ้าเงื่อนไขนี้เป็นจริงจะรีเทิร์นค่า true และถ้าไม่จริงจะรีเทิร์นค่า false

4. isFull() เป็นเมธอดสำหรับตรวจสอบว่าสแตกเต็มหรือไม่  โดยมี return type คือ boolean เขียนโค๊ดได้ดังนี้

อธิบายรูปคือ

• บรรทัดที่ 27 คือการรีเทิร์นค่าที่ได้จากการตรวจสอบเงื่อนไข stackTop == maxStackSize ถ้าเงื่อนไขนี้เป็นจริงจะรีเทิร์นค่า true และถ้าไม่จริงจะรีเทิร์นค่า false

5. push() เป็นเมธอดสำหรับการเพิ่มข้อมูลไปยังสแตก โดยมรการรับพารามเตอร์หนึ่งตัวคือ Object newItem เขียนโค๊ดได้ดังนี้

อธิบายรูปคือ

• บรรทัดที่ 31-32 ตรวจสอบว่าสแตกเต็มหรือไม่ หากสแตกเต็มแล้วจะหยุดการทำงาน และแสดงคำว่า StackOverflow ออกทาง Console
• บรรทัดที่ 33-34 เป็นผลมาจากการตรวจสอบเงื่อนไขด้านบน หากเงื่อนไขบนไม่เป็นจริง ก็จะกำหนดค่า newItem ลงในอาร์เรย์ตำแหน่งที่ stackTop และเพิ่มค่า stackTopไปอีกหนึ่ง เพื่อไปชี้ยังตำแหน่งถัดไปของอาร์เรย์

6. pop() เป็นเมธอดสำหรับการลบข้อมูลจากสแตก เขียนโค๊ดได้ดังนี้

อธิบายรูปคือ

• บรรทัดที่ 44-45 ตรวจสอบว่าสแตกว่างหรือไม่ หากสแตกว่างไม่มีข้อมูลจะหยุดการทำงาน และแสดงคำว่า StackUnderflow ออกทาง Console
• บรรทัดที่ 46-47 เป็นผลมาจากการตรวจสอบเงื่อนไขด้านบน หากเงื่อนไขบนไม่เป็นจริง ก็จะลดค่า stackTop ลงหนึ่งค่า แล้วกำหนดค่าให้ข้อมูลในอาร์เรย์ตำแหน่งที่ stackTop ชี้อยู่มีค่าเท่ากับ null

7. peek() เป็นเมธอดสำหรับการดูข้อมูลที่ตำแหน่งบนสุดของสแตก นั่นคือดูข้อมูลล่าสุดที่เพิ่มเข้าไป โดยมี return type คือ Object เขียนโค๊ดได้ดังนี้

อธิบายรูปคือ

• บรรทัดที่ 38-39 ตรวจสอบว่าสแตกว่างหรือไม่ หากสแตกว่างไม่มีข้อมูลจะหยุดการทำงาน และแสดงคำว่า StackUnderflow ออกทาง Console
• บรรทัดที่ 40 เป็นผลมาจากการตรวจสอบเงื่อนไขด้านบน หากเงื่อนไขบนไม่เป็นจริง ก็จะรีเทิร์นข้อมูลในอาร์เรย์ตำแหน่งที่ stackTop ชี้อยู่ แต่จากโค๊ดจะเห็นค่าต้องลบหนึ่งด้วย เพราะอินเด็กของอาร์เรย์ให้เริ่มที่ศูนย์

8. main() เป็นเมธอดสำหรับการเรียกใช้เมธอดอื่นๆ เขียนโค๊ดได้ดังนี้

อธิบายรูปคือ

• บรรทัดที่ 50 สร้าง object s1  โดยใช้ constructor method แบบไม่มีพารามิเตอร์ จึงทำให้สแตกมีขนาดเท่ากับ 100 และสร้าง object s2 โดยใช้ constructor method แบบมีพารามิเตอร์ โดยส่งค่า 50 จึงทำให้สแตกมีขนาด 50
• บรรทัดที่ 52-53 เรียกใช้เมธอด initializeValueStack() ทั้งสองออปเจ็ค
• บรรทัดที่ 55-60 การเพิ่มค่าไปยังสแตก โดยพบว่าเพิ่มข้อมูลที่มีประเภทแตกต่างกันไปยังสแตกเดียวกันได้
• บรรทัดที่ 61-68 พยายามแสดงค่าที่อยู่ที่ top of stack โดยใช้เมธอด peek() และลบข้อมูลที่อยู่ที่ตำแหน่ง top of stack โดยใช้เมธอด pop()

จากการยกตัวอย่างทั้งหมดนี้ทำให้สามรถสร้างสแตกอย่างง่ายขึ้นมมาใช้งานได้ และสามารถนำไปประยุกต์กับงานอื่นๆได้

โต๊ดสมบูรณ์สามารถดาวน์โหลดได้ที่นี่

Stack.java