[자료구조] 스택 STACK

1. 의미
- 스택 자료구조는 아래가 막혀있는 긴 통에 물건을 층층이 쌓아둔 상태로 보시면 됩니다. 
예를들어 물건을 쌓기위해서는 현재 쌓여있는 물건 중 가장 위쪽에 쌓일 것이고, 꺼내기 위해서는 현재 쌓여있는 물건 중 가장 위쪽 물건이 꺼내질 것입니다. 이러한 구조를 선입후출(First In Last Out; FILO)또는 후입선출(Last In First Out; LIFO) 구조라고 칭합니다.

2. 연산
- 스택 자료구조의 연산(삽입, 삭제, 읽기)은 모두 스택의 꼭대기에서 일어납니다. 스택의 꼭대기를 가리키는 변수를 통상적으로 top이라고 합니다.

top이 -1을 가리키고 있는 상태가 스택이 비어있는 상태입니다.
(이해를 돕기위해 -1 인덱스를 표기한 것이지 배열의 인덱스는 0에서 시작합니다.)

삽입(push) 연산은 top이 가리키는 위치를 1 증가시키고, 그 위치에 데이터를 삽입합니다.

top이 인덱스 맨 끝을 가리키고 있는 상태가 스택이 가득 찬 상태입니다.
(인덱스 맨 끝은 스택 사이즈 -1입니다. 인덱스가 0부터 시작하기 때문)

삭제(pop) 연산은 top이 가리키는 위치의 데이터를 반환하고, 위치를 1 감소합니다.

3. 사용
- 스택은 컴퓨터 구조에서 다음과 같이 다양하게 사용됩니다. 

브라우저에서 이전페이지, 다음페이지 이동
에디터에서 실행취소, 다시실행
괄호검사
역순문자열 만들기
후위 표기법 수식의 연산 등...

아래의 구현방법을 통해 실제 스택 사용 예를 직접 구현해 보는것도 자료구조의 이해와 실력 향상에 도움이 될 것입니다.

4. 구현
C++ Class를 이용해 스택 자료구조를 배열로 구현했습니다.

#include <iostream> 
using namespace std; 

class stack 
{ 
private : 
     int *stack_arr; // 스택 배열(동적 할당을 위해 포인터로 선언) 
     int stack_size; // 스택의 크기 
     int top = -1; // top은 -1로 초기화  

public : 
     stack() // 디폴트 생성자 함수 
     { 
          stack_size = 5; // 매개변수 없이 객체 생성 시 스택 크기 5로 지정 
          stack_arr = new int[stack_size]; // 배열 동적 할당 
          for (int i = 0; i < stack_size; i++) 
          { 
               stack_arr[i] = 0; // 스택의 배열은 모두 0으로 초기화 
          } 
     } 
     stack(int size) // 생성자 함수 
     { 
          stack_size = size; // 입력한 매개변수 크기만큼 스택 크기 지정  
          stack_arr = new int[stack_size]; // 배열 동적 할당 
          for (int i = 0; i < stack_size; i++) 
          { 
               stack_arr[i] = 0; // 스택의 배열은 모두 0으로 초기화 
          } 
     } 
     ~stack() // 소멸자 함수 
     { 
          delete[] stack_arr; 
     } 
     void push(int data) // 삽입 함수 
     { 
          if (stack_is_full()) // 스택이 가득 차 있는 경우 
          { 
               cout << "스택이 가득 차 있습니다." << "\n"; 
               return; // 함수 종료 
          } 
          else // 아닐 경우 정상 작동 
          { 
               top++; // top 위치 1 증가 
               stack_arr[top] = data; // 데이터 삽입 
               cout << "데이터 삽입 성공!" << "\n"; 
          } 
     } 
     void pop() // 삭제 함수 
     { 
          if (stack_is_empty()) // 스택이 비어있는 경우 
          { 
               cout << "스택이 비어있습니다." << "\n"; 
               return; // 함수 종료 
          } 
          else // 아닐 경우 
          { 
               cout << "반환 된 데이터 : " << stack_arr[top] << "\n"; // 데이터 반환 
               stack_arr[top] = 0; // 데이터 삭제 
               top--; // top 위치 1 감소 
          } 
     } 
     int peak() // 현재 꼭대기 위치 확인 함수 
     { 
          return stack_arr[top]; 
     } 
     bool stack_is_empty() // 스택이 비어있는지 확인 함수 
     { 
          if (top == -1) // top이 -1을 가리키면 비어있음 
               return true;  
          else  // 아닐 경우 비어있지 않음 
               return false; 
     } 
     bool stack_is_full() // 스택이 가득 차 있는지 확인 함수 
     { 
          if (top == stack_size - 1) // top이 인덱스 마지막을 가리키면 가득 차 있음 
               return true; 
          else  // 아닐 경우 가득 차 있지 않음 
               return false; 
     } 
     void print_stack() // 스택 전체 출력 함수 
     { 
          cout << "STACK : [ "; 
          for (int i = 0; i < stack_size; i++) 
          { 
               if (i != stack_size - 1) 
               { 
                    cout << stack_arr[i] << " , "; 
               } 
          else 
          { 
               cout << stack_arr[i]; 
          } 
     } 
     cout << " ] " << "\n"; 
     cout << "top 위치 : " << top << "\n"; 
     } 
}; 

int main()  
{ 
     stack *stk; 
     int input_size; 
     cout << "스택 크기 입력 : "; 
     cin >> input_size; 
     if (input_size <= 0) 
     { 
          cout << "잘못 된 입력입니다. 디폴트 사이즈(5)로 생성합니다." << "\n"; 
          stk = new stack(); 
     } 
     else 
     { 
          stk = new stack(input_size); 
     } 
     while (1) 
     { 
          int input; 
          cout << "\n" << "[명령어 입력]" << "\n"; 
          cout << "1. PUSH " << "\n" << "2. POP " << "\n" << "3. PEAK "  
          << "\n" << "4. PRINT " << "\n" << "5. EXIT : "; 
          cin >> input; 
          switch (input) 
          { 
          case 1: 
               int input_data; 
               cout << "삽입 할 데이터를 입력하세요 : "; 
               cin >> input_data; 
               stk->push(input_data); 
               break; 
          case 2: 
               stk->pop(); 
               break; 
          case 3: 
               cout << "현재 top 위치의 데이터 : " << stk->peak() << "\n"; 
               break; 
          case 4: 
               stk->print_stack(); 
               break; 
          case 5: 
               cout << "프로그램을 종료합니다." << "\n"; 
               return 0; 
          default : 
               cout << "잘못 된 입력입니다. 다시 입력해 주세요" << "\n"; 
          } 
     } 
}

질문 사항은 댓글로 남겨주세요!