สแตก(Stack) เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติคือ การเพิ่มหรือลบข้อมูลในสแตก จะทำที่ปลายข้างเดียวกัน เรียกว่า Top ของสแตก (Top of Stack) และลักษณะที่สำคัญของสแตก คือ ข้อมูลใส่หลังสุดจะนำออกมา จากสแตกเป็นลำดับแรกสุด เรียกคุณสมบัตินี้ว่า LIFO (last in first out)
การทำงานของสแตกมี3กระบวนการคือ
1.Push คือ การนำข้อมูลใส่ลงไปในสแตก
2.Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตก
3.Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก
การแทนที่ข้อมูลของสแตก สามารถทำได้ 2 วิธี คือ
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์ จะประกอบไปด้วย2 ส่วน คือ
1. Head Node จะประกอบไปด้วย 2ส่วนคือ top pointer และจำนวนสมาชิกในสแตก
2. Data Node จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ ที่ชี้ไปยังข้อมูลตัวถัดไป
การดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack จัดสรรหน่วยความจำให้แก่ Head Nodeและส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
2. Push Stack การเพิ่มข้อมูลลงไปในสแตก
3. Pop Stack การนำข้อมูลบนสุดออกจากสแตก
4. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก โดยไม่มีการลบข้อมูลออกจากสแตก
5.Empty Stack เป็นการตรวจสอบการว่างของสแตก เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลออกจากสแตกที่เรียกว่า Stack Underflow
6. Full Stack เป็นการตรวจสอบว่าสแตกเต็มหรือไม่ เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลเข้าสแตกที่เรียกว่า Stack Overflow
7. Stack Count เป็นการนับจำนวนสมาชิกในสแตก
8. Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
การคำนวณนิพจน์ทางคณิตศาสตร์
ในการเขียนนิพจน์ทางคณิตศาสตร์เพื่อการคำนวณ จะต้องคำนึงถึงลำดับความสำคัญของเครื่องหมายสำหรับการคำนวณด้วยโดยทั่วไปนิพจน์ทางคณิตศาสตร์สามารถเขียนได้ 3 รูปแบบ คือ
1. นิพจน์ Infix นิพจน์รูปแบบนี้ operatorจะอยู่ตรงกลางระหว่างตัวถูกดำเนินการ 2 ตัว
2. นิพจน์ Postfix นิพจน์รูปแบบนี้ จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และ 2 ก่อน แล้วตามด้วย operator
3. นิพจน์ Prefix นิพจน์รูปแบบนี้ จะต้องเขียน operatorก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และ 2
ในการเขียนโปรแกรมคอมพิวเตอร์ด้วยภาษาระดับสูง คำสั่งที่เป็นนิพจน์ทางคณิตศาสตร์จะเขียนอยู่ในรูปแบบของนิพจน์Infix การคำนวณค่านิพจน์ในรูปแบบนี้ ตัวแปลภาษาต้องทำการ ตรวจสอบนิพจน์จากซ้ายไปขวา เพื่อหาเครื่องหมาย
ที่ต้องคำนวณ ก่อน จึงจะเริ่มคำนวณให้ แล้วทำแบบนี้ซ้ำ ๆกันจนกว่าจะ คำนวณเครื่องหมายครบทุกตัว ทำให้การทำงานช้าและไม่สะดวก ต่อการคำนวณ
การแก้ปัญหานี้ ตัวแปลภาษาจะทำงานแปลง
นิพจน์ Infix ให้ อยู่ในรูปแบบที่ช่วยให้การคำนวณสะดวกและรวดเร็วขึ้น โดยแปลงให้อยู่ในรูปของนิพจน์ Postfix ในการแปลงจากนิพจน์ Infixไปเป็นนิพจน์ Postfix จะใช้ เทคนิคของการจัดเก็บข้อมูลใน โครงสร้างสแตกเข้ามาช่วย โดยพิจารณานิพจน์ Infix ทีละตัวอักษรจากซ้ายไปขวาและย้าย ตัวอักษรเหล่านั้นไปเป็นนิพจน์ Postfixทีละตัว ส่วนตัวดำเนินการหรือ operator จะถูกนำไปเก็บไว้ในสแตก
ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์Postfix
1. อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัว ดำเนินการที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
- ถ้ามีความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัวดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์ Postfix
4. ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตกแต่มีผลให้ตัวดำเนินการอื่น ๆ ถูก pop ออกจากสแตก นำไป เรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(” จะ popวงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5. เมื่อทำการอ่านตัวอักษรในนิพจน์ Infixหมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุกตัวในสแตกนำมาเรียงต่อในนิพจน์Postfix
ในการคำนวณค่า Postfix ที่แปลงมาแล้ว ตัวแปลภาษาจะทำการคำนวณโดยใช้โครงสร้างสแตกช่วยอีกเช่นกันขั้นตอนในการคำนวณ
1. อ่านตัวอักษรในนิพจน์ Postfix จากซานไปขวาทีละตัวอักษร
2. ถ้าเป็นตัวถูกดำเนินการ ให้ทำการ push ตัวถูกดำเนินการนั้นลงในสแตก แล้วกลับไปอ่านอักษรตัวใหม่เข้ามา
3. ถ้าเป็นตัวดำเนินการ ให้ทำการ pop ค่าจากสแตก 2 ค่าโดย ตัวแรกเป็นตัวถูกดำเนินการตัวที่ 2 และตัวที่ 1
4. ทำการคำนวณ ตัวถูกดำเนินการตัวที่ 1ด้วยตัวถูก ดำเนินการตัวที่ 2 โดยใช้ตัวดำเนินการในข้อ 3
5. ทำการ push ผลลัพธ์ที่ได้จากการคำนวณในข้อ 4 ลงสแตก
6. ถ้าตัวอักษรในนิพจน์ Postfix ยังอ่านไม่หมดให้กลับไปทำข้อ 1 ใหม่
ฟังก์ชั่น iostream
#include
#include
int main () {
long int num;
cout<<"========== Count Back to one =========="<<'\n'<<'\n'; cout<<"Please enter number (0 to STOP):"; cin>>num;
while(num!=0){
while (num>0) {
cout<< num <<'\n';>>num;
}
clrscr();
cout<<"+++++++++++++++++++++++++++++\n"; cout<<"++++++++++ Good Bye++++++++++\n"; cout<<"+++++++++++++++++++++++++++++\n"; return 0; }
