[자료구조] 스택 stack / 배열을 이용한 스택의 구현

스택이란?

스택은 자료나 물건들을 차례대로 쌓아둔 더미를 의미한다.

 

 

스택의 특성

• 2가지 대표적인 함수 : push/pop 함수
  
  
  • push 함수 : 스택에 값을 넣을때(제일 상단에 값을 추가함)
  • pop 함수 : 스택에서 값을 꺼낼 때(제일 상단의 값을 꺼냄)
• 후입선출 (LIFO : Last-In First-Out) 방식
  
  
  • 먼저 들어 온 것이 아래에 있으므로 나중에 들어온 것이 먼저 사용 또는 제거되는 특징을 가진다.
    (반대 개념 FIFO : First-In First-Out)

 

스택 관련 주요 연산/함수

• createStack() - 스택을 생성한다.
• is_empty(s) - 스택 s가 비어있는지를 검사한다.
• is_full(s) - 스택 s가 가득 찼는지를 검사한다. (배열인 경우)
• push(s, e) - 스택 s의 맨 위에 요소 e를 추가한다.
• pop(s) - 스택 s의 맨 위에 있는 요소를 삭제한다.
• peek(s) - 스택 s의 맨 위에 있는 요소를 삭제하지 않고 반환한다.
  (비고) peek와 pop의 차이는 스택에서 값을 제거하는지의 여부

 

스택의 구현 방식

• 배열 방식
  
  
  • 스택의 경우, 보통 배열 방식을 주로 사용
  • 단순한 배열 또는 객체의 배열을 사용
  • 배열 인덱스(스택포인터)를 이용하여 편리하게 사용
  • 배열(스택) 크기에 제한 존재 -> 수시 확인 필요
  • (cf) 그림에서는 주로 배열을 세운 모양으로 설명
• 연결리스트 방식
  
  
  • 노드/연결리스트 방식으로도 구현 가능
  • 스택 크기에 제한이 없음
  • 일반적으로 연결리스트는 원소 삽입/삭제시 매우 유리하나,
    스택의 경우, 배열 방식보다 다소 복잡한 면이 있어 배열 방식을 선호한다.

 

배열을 이용한 스택의 구현

• 배열의 인덱스 이용
  
  
  • 첫 자료를 stack[0], 다음 자료를 stack[1]에 넣는 식으로 유지
• 스택 포인터(stack pointer)라는 변수를 사용
  
  
  • 가장 나중에 입력된 자료의 배열 인덱스를 저장
  • 주로 sp 또는 top 등의 변수명을 사용하며, 초기값은 주로 -1로 설정
    예) sp = -1; 또는 top = -1;
  • 원소가 3개 스택에 들어있다면, 즉, stack[0], stack[1], stack[2]에 자료가 있으므로, top = 2로 설정
  • 항상 첫 원소는 stack[0], 마지막 원소는 stack[top]에 저장됨
• 스택 포인터(인덱스)의 값으로 원소 개수 추정도 가능
  
  
  • 예) top 값이 -1이면, 그 스택은 비어 있다.
  • 예) top = 2이면, 3개의 원소를 보유
• 배열 방식의 스택은 배열을 세워서 설명하는 경우가 많다.

 

배열을 이용한 스택의 구현 예시

#include <iostream>
using namespace std;

const int MAX_NUM = 100;
//define MAX_NUM 100
typedef int element;

class Stack{
public:
    element data[MAX_NUM];
    int top; //마지막 원소를 가리키는 인덱스
    
    Stack(){
        top=-1; //초기화
    }
    bool is_empty(){
        //if(top == -1) return true;
        //else return false;
        return(top == -1);
    }
    
    bool is_full(){
        //if (top == MAX_NUM-1) return true; //인덱스는 0~99까지니까 -1 해주어야 한다.
        //else return false;
        return (top == MAX_NUM-1);
    }
    
    void push(element value){
        if(is_full()){
            cout << "STACK OVERFLOW!!!" << endl;
            exit(-1);
        }
        else{
            //top++;
            //data[top] = value;
            data[++top] = value;
        }
    }
    element pop(){
        if (is_empty()){
            cout<<"STACK UNDERFLOW!!!"<<endl;
            exit(-1);
        }
        else{
            //element x = data[top];
            //top--;
            //return(x);
            return(data[top--]);
        }
    }
    element peek(){
        if(is_empty()){
            cout<< "STACK UNDERFLOW!!!" <<endl;
            exit(-1);
        }
        else{
            return(data[top]);
        }
    }
    void printStack(){
        cout << "## STACK 상태 ###" <<endl;
        for(int i = top; i >= 0; i--)
            cout << data[i] <<endl;
    }
};

int main(){
    Stack MyStack;
    
    MyStack.push(100); MyStack.printStack();
    
    MyStack.pop(); MyStack.printStack();
    
    MyStack.push(200); MyStack.printStack();
    MyStack.push(300); MyStack.printStack();
    MyStack.push(400); MyStack.printStack();
    
    element key = MyStack.pop(); MyStack.printStack();
    
    MyStack.push(500); MyStack.printStack();   
}