스택(Stack)이란?
스택은 여러 개의 요소(element)를 모아 놓은 추상 자료구조입니다. 스택은 LIFO(Last In First Out, 후입선출) 방식으로 동작하며, 이는 가장 마지막에 삽입된 요소가 가장 먼저 제거된다는 의미입니다.
스택의 대표적인 연산은 다음과 같습니다.
Push – 스택의 맨 위(top)에 데이터 값을 추가합니다.
Pop – 스택의 맨 위에 있는 데이터 값을 제거합니다.
Peek – 스택의 맨 위 데이터 값을 제거하지 않고 그대로 반환합니다.
아래 프로그램은 연결 리스트(linked list)를 활용하여 스택을 구현한 C++ 코드입니다.
예제 코드
#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
코드 상세 설명
1. 노드(Node) 구조체 정의
위 프로그램에서는 Node 구조체를 이용해 연결 리스트를 생성하고, 이를 스택으로 구현합니다. 각 노드는 실제 데이터를 저장하는 data와 다음 노드를 가리키는 포인터 next로 구성되며, 전역 포인터 top은 항상 스택의 최상단 노드를 가리킵니다.
struct Node {
int data;
struct Node *next;
};
2. push() 함수 – 데이터 삽입
push() 함수는 인자 val, 즉 스택에 넣을 값을 전달받습니다. 먼저 새로운 노드를 생성하고 data 부분에 값을 저장한 뒤, 이 노드를 연결 리스트의 맨 앞에 추가하고 top이 새 노드를 가리키도록 합니다. 이러한 구조 덕분에 삽입 연산은 O(1)의 시간 복잡도로 수행됩니다.
void push(int val) {
struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
newnode->data = val;
newnode->next = top;
top = newnode;
}
3. pop() 함수 – 데이터 삭제
pop() 함수는 스택에 값이 존재하는 경우 맨 위의 값을 제거하고 출력합니다. 반면 스택이 비어 있으면(top == NULL) 언더플로우(Stack Underflow) 메시지를 출력하여 더 이상 삭제할 요소가 없음을 알립니다.
void pop() {
if(top==NULL)
cout<<"Stack Underflow"<<endl;
else {
cout<<"The popped element is "<< top->data <<endl;
top = top->next;
}
}
4. display() 함수 – 스택 내용 출력
display() 함수는 스택에 저장된 모든 요소를 화면에 출력합니다. 포인터 ptr이 처음에는 top을 가리키다가 next 포인터를 따라 스택의 끝까지 이동하면서, 각 노드의 데이터 값을 순서대로 출력합니다. 스택이 비어 있으면 stack is empty라는 메시지를 표시합니다.
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;
}
5. main() 함수 – 사용자 메뉴 처리
main() 함수는 사용자에게 스택에 값을 넣기(push), 값 빼기(pop), 스택 출력(display) 중 원하는 작업을 선택할 수 있는 메뉴를 제공합니다. 사용자의 입력에 따라 switch 문으로 적절한 함수를 호출하며, 잘못된 번호가 입력되면 Invalid Choice 안내 메시지를 출력합니다. 사용자가 종료(4번)를 선택할 때까지 이 과정이 반복됩니다.
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;
}
마무리 및 참고 사항
연결 리스트 기반 스택은 배열 기반 스택과 달리 크기 제한이 없어 필요할 때마다 노드를 동적으로 추가할 수 있다는 장점이 있습니다. 다만 위 예제에서는 설명의 편의를 위해 malloc()을 사용했는데, 순수 C++ 환경에서는 new 연산자를 사용하는 것이 일반적이며, 실제 프로젝트에서는 사용이 끝난 노드의 메모리 해제(delete/free)도 반드시 고려해야 합니다.