스택이란?
인터넷을 돌아다니다 보면 "업보 스택 쌓는다"라는 말을 들을 수 있을 것이다. 무언가 잘못을 해서 업보를 차곡차곡 쌓는다는 뜻인데, 나중에 이를 그대로 돌려받을 때 "업보 청산" 한다고 한다.
여기서 스택의 뜻을 대충 유추할 수 있는데, 스택은 업보와 같이 동일한 구조의 데이터를 차곡차곡 쌓는 것을 말한다.
스택의 특징
스택의 대표적인 특징으로는 "가장 마지막에 삽입된 데이터가 가장 먼저 삭제"되는 후입선출(LIFO:Last-In-First-Out)의 구조를 가진다는 것이다.
이러한 특징 때문에 스택에서는 가장 나중에 들어간 데이터 만을 조작할 수 있는데, 여기서 가장 위에 위치한 데이터를 top이라고 한다.
스택에서 삽입과 삭제는 모두 top을 통해서만 가능하다.
스택의 기능
스택에는 데이터를 삽입하는 push 연산과, 데이터를 삭제하는 pop 연산이 있다.
push 연산
스택에서 top을 통한 삽입 연산을 push라 한다.
만약 새로운 데이터를 push하게 된다면, 새로운 데이터는 그 전에 스택에 들어있던 데이터의 위로 쌓이게 된다.
스택에 데이터를 집어넣은 후에는 새롭게 들어간 데이터를 top으로 만들어 주는 과정이 반드시 필요하다.
pop 연산
스택에서 top을 통한 삭제 연산을 pop이라 한다.
pop연산을 통한 데이터 삭제는 가장 위에 있는 데이터. 즉, top으로 지정되어 있는 데이터만 가능하다.
만약 pop연산을 통해 가장 위에 있는 데이터를 삭제했다면, 그 아래 있는 데이터를 새로운 top으로 만들어 주는 과정이 반드시 필요하다.
스택의 구현
스택을 구현하는 가장 쉬운 방법은 배열을 이용하는 것이다.
위 그림은 배열을 사용해서 구현한 스택에서, push와 pop 연산이 이루어질 때 top의 값이 어떻게 변하는지 알기 쉽도록 나타낸 것이다.
스택에 push연산이 이루어질 때, 새로운 데이터가 추가되는 위치는 그 직전 top의 크기보다 +1이 증가한 위치에 삽입된다는 것을 반드시 기억해야한다.
스택
#define STACK_SIZE 10 //스택의 사이즈 변경을 용이하게 하기 위해서 기호상수로 선언
int stack[STACK_SIZE]; //STACK_SIZE 만큼의 int형 배열
int top = -1; //top의 위치n칸짜리 스택을 만들고 싶다면 크기가 n인 배열 stack[n]을 선언하면 된다.
top의 경우 -1로 초기화한다.
스택이 비어있는지 확인 - isEmpty() 함수
int isEmpty() { //스택이 비어있는지 확인
if(top < 0) { //스택이 비어있다면 top의 값이 -1인 것을 생각
return 1;
}
else {
return 0;
}
}스택이 비어있음에도 불구하고 pop 연산을 수행하게 된다면 스택에 오류가 생길 것이다.
때문에 pop 연산 전에는 반드시 스택이 비어있는지 확인을 해주어야 한다.
isEmpty() 함수는 스택이 비어있는지 확인 후 스택이 비어있으면 1을, 스택이 비어있지 않으면 0을 반환한다.
스택이 차있는지 확인 - isFull() 함수
int isFull() { //스택이 꽉 차있는지 확인
if (top == STACK_SIZE - 1) { //STACK_SIZE가 10이면, stack[STACK_SIZE]는 0~9의 인덱스를 가짐
return 1;
}
else {
return 0;
}
}스택이 꽉 차있는데도 데이터를 삽입하려고 하면 스택이 망가질 것이다.
때문에 push 연산 전에는 반드시 스택이 꽉 차있는지 확인을 해주어야 한다.
isFul() 함수는 스택이 차있는지 확인 수 스택이 차있으면 1을, 스택이 차있지 않으면 0을 반환한다.
데이터 삽입 - Push() 함수
void Push(int input) { //스택에 데이터를 삽입하는 함수
if(!isFull()) { //스택이 꽉 차있는지 확인
top++; //top을 증가
stack[top] = input; //데이터 삽입
}
else {
cout << "Stack is Full\n";
}
}Push() 함수는 데이터를 매개변수로 받아 스택에 삽입하는 함수다.
스택에 데이터를 삽입하기 전에 스택이 꽉 차있는지 상태를 점검하는 과정을 거쳐야 한다.
데이터 삭제 - Pop() 함수
void Pop() { //스택에서 데이터를 삭제하는 함수
if(isEmpty()) { //스택이 비어있는지 확인
cout << "Stack is Empty\n";
}
else {
stack[top] = 0; //스택의 가장 끝 데이터를 0으로 초기화
top--; //top 감소
}
}Pop() 함수는 top의 위치에 있는 데이터를 삭제하는 함수다.
스택에 있는 데이터를 삭제하기 전에 스택이 비어있는지 확인하는 과정을 거쳐야 한다.
스택에 있는 데이터를 출력 - PrintStack() 함수
void PrintStack() { //스택 전체를 출력하는 함수
if(isEmpty()) {
cout << "Stack is Empty\n";
}
else {
for(int i = 0; i <= top; i++) { //스택의 끝까지 탐색
cout << "stack[" << i << "] = " << stack[i] << "\n"; //출력 : stack[i] = data
}
}
}스택에 있는 데이터를 모두 출력하는 함수다.
스택에서 데이터를 검색 - Serch() 함수
void Search(int position) { //스택에서 특정 인덱스의 값을 찾아오는 함수
if(position <= top){
cout << "stack[" << position << "] = " << stack[position] << "\n"; //출력 : stack[i] = data
}
else { //인덱스의 값이 배열의 크기보다 큼
cout << "There is no value on that index.\n";
}
}스택에서 특정 인덱스에 위치한 값을 찾아서 출력하는 함수다.
main() 함수
int main() {
int menu = 0;
int position = 0;
int input = 0;
while(1) {
cout << "\n메뉴를 선택하시오\n\n";
cout << "1. Push\n2. Pop\n3. 스택 출력\n"
"4. 원소 검색\n5. 종료\n";
cin >> menu;
switch (menu) {
case 1:
cout << "입력할 값을 입력하시오 : ";
cin >> input;
Push(input);
break;
case 2:
Pop();
break;
case 3:
PrintStack();
break;
case 4:
cout << "검색할 위치를 입력하시오 : ";
cin >> position;
Search(position);
break;
case 5:
return 0;
}
}
}총평
스택은 배열로 구현하면 굉장히 쉽게 구현할 수 있다.
스택은 '문자열 뒤집기'나 '괄호 짝 찾기' 등의 문제를 풀 때 요긴하게 쓰인다.
배열이 아니라 연결 리스트로도 구현할 수 있으니 궁금한 사람은 보충해서 공부해도 좋을 거 같다.
백준 문제 예시)
BOJ.108298(스택) : https://www.acmicpc.net/problem/10828
BOJ.9012(괄호) : https://www.acmicpc.net/problem/9012
'자료구조 > C++' 카테고리의 다른 글
| [자료구조/C++] 연결 자료구조와 연결 리스트(Linked List) (0) | 2022.01.24 |
|---|
댓글