[자료구조] 스택 Stack

스택 Stack

 

스택이란?

스택이나 큐, 트리와 같은 자료구조는 자신이 행위적 측면을 포함하는 자료구조이다. 이런 자료 구조는 제한된 접근 방식을 규정하고 있으며 이를 추상적 자료 구조(Abstrct Data Structure)라고 한다.

스택은 제일 나중에 들어간 것이 제일 먼저 나오는 LIFO(Last In First Out) 구조로 배열이나 연결 리스트(Linked List)로 구현할 수 있다.

배열로 구현하기는 쉽지만 처음에 스택의 크기를 지정해줘야 한다는 단점이 있고,

연결 리스트는 크기를 동적으로 할당하기 때문에 용량에 대해서는 제한(최대 메모리까지)이 없지만 구현하기는 비교적 어렵다는 단점이 있다.

 

 

스택의 구성

스택은 기본적으로 데이터를 삽입할 수 있는 push와 스택에서 데이터 하나를 빼내는 pop으로 동작한다.

 

<스택 동작 과정>

그 외의 메소드들은 스택의 특징을 반영하여 만들 수 있다. 예를 들면 아래와 같은 종류가 있다.

• peek() : 스택의 가장 상단 부분에 있는 데이터 출력
• display() : 스택 내용 출력
• isEmpty() : 스택에 내용이 비었는지를 확인
• 등등...

 

배열로 이해하는 스택

스택을 배열로 구현할 때 가장 중요한 요소인 top는 현재 제일 윗 데이터를 가리키는 용도로 사용된다. 즉 이 top를 사용하여 스택의 현재 데이터의 양을 가늠하는 것이다.

 

top는 -1부터 시작하여 push를 하면 +1, pop을 하면 -1을 하는 방식으로 동작한다. 이를 통해 스택 오버플로우(stack overflow)와 스택 언더플로우(underflow)를 판단할 수 있다.

• 스택 오버플로우(stack overflow) : 스택이 꽉 차서 더 이상 자료를 push 할 수 없는 경우인데도 push를 하는 경우
• 스택 언더플로우(stack underflow) : 스택이 텅 비어있는 경우에 다시 pop을 하여 스택의 값을 빼낼 것을 요구하는 경우

 

*스택의 크기를 MAX라고 하자.

*스택과 top는 전역변수이고, MAX는 상수이다.

[push]

int push(int data) {
    if (top >= MAX - 1) {//스택이 꽉 찬 경우
        printf("Stack Overflow\n");
        return -1;
    }
    //top를 증가시키고 data를 삽입
    stack[++top] = data;
    return data;
}

line 2: if( top >= MAX -1)

top는 현재 제일 상단에 있는 데이터의 위치를 가리키고, MAX - 1은 스택의 최대 인덱스 위치이다.

top가 MAX-1보다 크거나 같다는 것은 스택이 꽉 차서 더 이상 데이터를 넣을 공간이 없다는 것을 의미한다.

*push를 int형이 아닌 void로 구현해도 괜찮다.

 

[pop]

int pop() {
    if (top < 0) {//스택에 내용이 없는 경우
        printf("Stack Underflow\n");
        return -1;
    }
    //스택 상단의 값을 리턴하고 top감소
    return stack[top--];
}

line 2: if(top < 0)

앞서 스택에 대해 설명할 때, top는 -1부터 시작한다는 것을 설명했었다.

즉, -1은 어느 인덱스도 가리키지 않다는 걸 의미하고 그것은 스택에 내용이 없다는 것이다.

 

 

스택 전체 코드(C언어 기반, 배열로 구현)

//STACK
#include <stdio.h>
#define MAX 10
int stack[MAX];
int top;
 
//스택 초기화
void init_stack() {
    top = -1;
}
 
//데이터 삽입
int push(int data) {
    if (top >= MAX - 1) {
        printf("STACK OVERFLOW\n");
        return -1;
    }
    //top를 증가시키고 data를 저장
    stack[++top] = data;
    return data;
}
 
//데이터 추출
int pop() {
    if (top < 0) {
        printf("STACK UNDERFLOW");
        return -1;
    }
    //스택 상단의 값을 리턴하고 top 감소
    return stack[top--];
}
 
//스택 출력
void print_stack() {
    printf("\nStack contents : Top ----> Bottom\n");
    for (int i = top; i >= 0; i--)
        printf("%d ", stack[i]);
}
 
void main() {
    int i;
    init_stack();
    printf("Push 5, 4, 7, 2, 1\n");
    push(5);
    push(4);
    push(7);
    push(2);
    push(1);
    print_stack();
    printf("\n\nPop");
    i = pop();
    print_stack();
    printf("\nPop data is %d\n", i);
    printf("\nPush 9, 3");
    push(9); push(3);
    print_stack();
    printf("\n\n");
    return 0;
}

[ 출력결과 ]