สแต็กเป็นโครงสร้างข้อมูลนามธรรมที่มีคอลเล็กชันขององค์ประกอบ กองซ้อนใช้กลไก LIFO เช่นองค์ประกอบที่ถูกผลักในตอนท้ายจะถูกดึงออกมาก่อน การดำเนินการหลักบางอย่างในสแต็กคือ −
-
พุช - เพิ่มค่าข้อมูลไปที่ด้านบนของสแต็ก
-
ป๊อป - ค่านี้จะลบค่าข้อมูลที่ด้านบนของสแต็ก
-
Peek - ส่งคืนค่าข้อมูลบนสุดของสแต็ก
โปรแกรมที่ใช้สแต็กโดยใช้ลิงค์ลิสต์มีดังต่อไปนี้
ตัวอย่าง
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *next;
};
struct Node* top = NULL;
void push(int val) {
struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
newnode->data = val;
newnode->next = top;
top = newnode;
}
void pop() {
if(top==NULL)
cout<<"Stack Underflow"<<endl;
else {
cout<<"The popped element is "<< top->data <<endl;
top = top->next;
}
}
void display() {
struct Node* ptr;
if(top==NULL)
cout<<"stack is empty";
else {
ptr = top;
cout<<"Stack elements are: ";
while (ptr != NULL) {
cout<< ptr->data <<" ";
ptr = ptr->next;
}
}
cout<<endl;
}
int main() {
int ch, val;
cout<<"1) Push in stack"<<endl;
cout<<"2) Pop from stack"<<endl;
cout<<"3) Display stack"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<"Enter choice: "<<endl;
cin>>ch;
switch(ch) {
case 1: {
cout<<"Enter value to be pushed:"<<endl;
cin>>val;
push(val);
break;
}
case 2: {
pop();
break;
}
case 3: {
display();
break;
}
case 4: {
cout<<"Exit"<<endl;
break;
}
default: {
cout<<"Invalid Choice"<<endl;
}
}
}while(ch!=4);
return 0;
} ผลลัพธ์
1) Push in stack 2) Pop from stack 3) Display stack 4) Exit Enter choice: 1 Enter value to be pushed: 2 Enter choice: 1 Enter value to be pushed: 6 Enter choice: 1 Enter value to be pushed: 8 Enter choice: 1 Enter value to be pushed: 7 Enter choice: 2 The popped element is 7 Enter choice: 3 Stack elements are:8 6 2 Enter choice: 5 Invalid Choice Enter choice: 4 Exit
ในโปรแกรมข้างต้น โครงสร้าง Node ใช้สำหรับสร้างรายการเชื่อมโยงที่นำไปใช้เป็นสแต็ก รหัสได้รับด้านล่าง
struct Node {
int data;
struct Node *next;
}; ฟังก์ชัน push() รับค่าอาร์กิวเมนต์ เช่น ค่าที่จะผลักเข้าไปในสแต็ก จากนั้นโหนดใหม่จะถูกสร้างขึ้นและใส่ val ลงในส่วนข้อมูล โหนดนี้ถูกเพิ่มที่ด้านหน้าของรายการที่เชื่อมโยงและจุดบนสุด ข้อมูลโค้ดสำหรับสิ่งนี้มีดังนี้
void push(int val) {
struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
newnode->data = val;
newnode->next = top;
top = newnode;
} ฟังก์ชัน pop() แสดงค่าสูงสุดของสแต็ก หากมีค่าใด ๆ หากสแต็กว่างเปล่า อันเดอร์โฟลว์จะถูกพิมพ์ ได้ดังนี้
void pop() {
if(top==NULL)
cout<<"Stack Underflow"<<endl;
else {
cout<<"The popped element is "<< top->data <<endl;
top = top->next;
}
} ฟังก์ชัน display() แสดงองค์ประกอบทั้งหมดในสแต็ก สิ่งนี้ทำได้โดยใช้ ptr ที่เริ่มแรกชี้ไปที่ด้านบนแต่ไปจนสุดของสแต็ก พิมพ์ค่าข้อมูลทั้งหมดที่เกี่ยวข้อง ti ptr ด้านล่างนี้
void display() {
struct Node* ptr;
if(top==NULL)
cout<<"stack is empty";
else {
ptr = top;
cout<<"Stack elements are: ";
while (ptr != NULL) {
cout<< ptr->data <<" ";
ptr = ptr->next;
}
}
cout<<endl;
} ฟังก์ชัน main() ให้ตัวเลือกแก่ผู้ใช้หากต้องการพุช ป๊อป หรือแสดงสแต็ก ตามการตอบสนองของผู้ใช้ ฟังก์ชันที่เหมาะสมเรียกว่าการใช้สวิตช์ หากผู้ใช้ป้อนคำตอบที่ไม่ถูกต้อง คำตอบนั้นจะถูกพิมพ์ออกมา ข้อมูลโค้ดสำหรับสิ่งนี้แสดงไว้ด้านล่าง
int main() {
int ch, val;
cout<<"1) Push in stack"<<endl;
cout<<"2) Pop from stack"<<endl;
cout<<"3) Display stack"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<"Enter choice: "<<endl;
cin>>ch;
switch(ch) {
case 1: {
cout<<"Enter value to be pushed:"<<endl;
cin>>val;
push(val);
break;
}
case 2: {
pop();
break;
}
case 3: {
display();
break;
}
case 4: {
cout<<"Exit"<<endl;
break;
}
default: {
cout<<"Invalid Choice"<<endl;
}
}
}while(ch!=4);
return 0;
} 