Ngăn xếp là một cấu trúc dữ liệu trừu tượng có chứa một tập hợp các phần tử. Stack thực hiện cơ chế LIFO tức là phần tử được đẩy vào cuối sẽ được bật ra trước. Một số hoạt động chính trong ngăn xếp là -
-
Đẩy - Điều này thêm một giá trị dữ liệu vào đầu ngăn xếp.
-
Cửa sổ bật lên - Thao tác này sẽ xóa giá trị dữ liệu trên đầu ngăn xếp.
-
Peek - Giá trị này trả về giá trị dữ liệu hàng đầu của ngăn xếp.
Một chương trình triển khai ngăn xếp sử dụng danh sách liên kết được đưa ra như sau.
Ví dụ
#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;
} Đầu ra
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
Trong chương trình trên, Node cấu trúc được sử dụng để tạo danh sách liên kết được thực hiện dưới dạng ngăn xếp. Mã được cung cấp bên dưới.
struct Node {
int data;
struct Node *next;
}; Hàm push () nhận đối số val, tức là giá trị được đẩy vào ngăn xếp. Sau đó, một nút mới được tạo và val được chèn vào phần dữ liệu. Nút này được thêm vào phía trước của danh sách được liên kết và điểm trên cùng của nó. Đoạn mã cho điều này như sau.
void push(int val) {
struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
newnode->data = val;
newnode->next = top;
top = newnode;
} Hàm pop () bật giá trị trên cùng của ngăn xếp, nếu có bất kỳ giá trị nào. Nếu ngăn xếp trống thì dòng in dưới sẽ được in. Điều này được đưa ra như sau.
void pop() {
if(top==NULL)
cout<<"Stack Underflow"<<endl;
else {
cout<<"The popped element is "<< top->data <<endl;
top = top->next;
}
} Hàm display () hiển thị tất cả các phần tử trong ngăn xếp. Điều này được thực hiện bằng cách sử dụng ptr mà ban đầu chỉ lên đầu nhưng đi đến cuối ngăn xếp. Tất cả các giá trị dữ liệu tương ứng ti ptr được in ra. Điều này được đưa ra bên dưới.
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;
} Hàm main () cung cấp lựa chọn cho người dùng nếu họ muốn đẩy, bật hoặc hiển thị ngăn xếp. Theo phản hồi của người dùng, chức năng thích hợp được gọi là sử dụng công tắc. Nếu người dùng nhập một phản hồi không hợp lệ, thì phản hồi đó sẽ được in. Đoạn mã cho điều này được cung cấp bên dưới.
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;
}