스택은 요소 모음을 포함하는 추상 데이터 구조입니다. 스택은 LIFO 메커니즘을 구현합니다. 즉, 마지막에 푸시된 요소가 먼저 튀어 나옵니다. 스택의 주요 작업 중 일부는 다음과 같습니다. -
-
푸시 - 스택의 맨 위에 데이터 값을 추가합니다.
-
Pop - 스택 맨 위에 있는 데이터 값을 제거합니다.
-
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 즉 스택에 푸시할 값을 취합니다. 그런 다음 새 노드가 생성되고 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() 함수는 스택의 모든 요소를 표시합니다. 이것은 처음에 top을 가리키지만 스택의 끝까지 가는 ptr을 사용하여 수행됩니다. tipr에 해당하는 모든 데이터 값이 인쇄됩니다. 이것은 아래와 같습니다.
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;
}