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 thực hiện một ngăn xếp bằng cách sử dụng mảng được đưa ra như sau.
Ví dụ
#include <iostream>
using namespace std;
int stack[100], n=100, top=-1;
void push(int val) {
if(top>=n-1)
cout<<"Stack Overflow"<<endl;
else {
top++;
stack[top]=val;
}
}
void pop() {
if(top<=-1)
cout<<"Stack Underflow"<<endl;
else {
cout<<"The popped element is "<< stack[top] <<endl;
top--;
}
}
void display() {
if(top>=0) {
cout<<"Stack elements are:";
for(int i=top; i>=0; i--)
cout<<stack[i]<<" ";
cout<<endl;
} else
cout<<"Stack is empty";
}
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, hàm push () nhận đối số val tức là giá trị được đẩy vào ngăn xếp. Nếu đỉnh lớn hơn hoặc bằng n, không có khoảng trống trong ngăn xếp và phần tràn được in. Nếu không, val được đẩy vào ngăn xếp. Đoạn mã cho điều này như sau.
void push(int val) {
if(top>=n-1)
cout<<"Stack Overflow"<<endl;
else {
top++;
stack[top]=val;
}
} 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<=-1)
cout<<"Stack Underflow"<<endl;
else {
cout<<"The popped element is "<< stack[top] <<endl;
top--;
}
} Hàm display () hiển thị tất cả các phần tử trong ngăn xếp. Nó sử dụng vòng lặp for để làm như vậy. Nếu không có phần tử nào trong ngăn xếp, thì Ngăn xếp trống được in. Điều này được đưa ra bên dưới.
void display() {
if(top>=0) {
cout<<"Stack elements are:";
for(int i=top; i>=0; i--)
cout<<stack[i]<<" ";
cout<<endl;
}else
cout<<"Stack is empty";
} 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;
}