[자료구조] Stack

스택은 삽입과 삭제가 리스트의 한쪽 끝에서만 일어나는 자료구조입니다. 스택에 뭔가를 추가하는 것을 push라고 하고, 삭제하는 것을 pop이라고 합니다. 

 

스택은 전형적인 후입선출 (Last-In-Frist-Out)의 형태로써, 아래의 그림처럼 구현됩니다.

 

 

Push를 실행하게 되면 가장 위에 데이터를 쌓아 올리고, pop을 실행하면 가장 위에서부터 데이터를 삭제하게 됩니다.

 

 

---

 

스택은 C로 구현하면 다음과 같이 구현할 수 있습니다. 스택은 1차원 배열을 이용하여 구현을 하게 됩니다. 

 

#define MAX_STACK_SIZE 100     //Stack의 최대 사이즈

typedef struct {

      int key; // 변수는 더 추가해도 상관없습니다. 변수가 하나밖에 없다면 굳이 구조체를 만들지 않고 구현해도 됩니다.

} element;

 

이라는 구조체를 우선적으로 만들고, 전역변수로전역 변수로 위에서 만든 구조체에 대한 배열과 현재 배열의 크기를 알려줄 int형 변수 하나를 다음과 같이 전역 변수로 선언해줍니다.

 

element stack[MAX_STACK_SIZE];

int top = -1; 

 

top이라는 변수는 현재 배열의 크기를 알려줄 변수로써, 처음에는 -1로 초기화해두고, push가 일어날 때마다 1씩 증가하고, pop이 일어날 때 마다 1씩 감소하게 됩니다.

 

 

push는 다음과 같이 구현합니다.

 

void push(element item){

      if (top >= MAX_STACK_SIZE -1) // 만일 현재 최대 스택 사이즈에 도달했다면

            printf("Stack is full\n");      // 스택이 가득 찼다고 알려줌

      stack [++top] = item;               

}

 

push()

 

스택이 가득 차 있지 않다면, 위의 그림과 같이 먼저 top의 값을 1 증가시킨 후, 그 위치에 데이터를 추가해 줍니다.

 

 

pop은 다음과 같이 구현합니다.

 

element pop(){

      if (top==-1)                            // 만일 스택이 비어있다면?

            printf("stack empty");           // 스택이 비었다고 알려줌

      return stack [top--];                   

}

 

 

pop()

 

pop()은 push()와는 반대로 먼저 데이터를 빼서 리턴해 준 뒤, top의 값을 1 감소시켜 줍니다.

 

그리고 pop()에서는 굳이 삭제되는 데이터가 궁금하지 않다면 void pop()으로 구현하고 마지막에 return을 하지 않아도 상관없습니다. 

 

---

위에서 개념적인 이해를 위해 그림을 그렸지만 실제 프로그램에서는 

 

push 3

push 4

push 6

pop

pop

push 9

 

를 수행하면 다음과 같이 수행됩니다.

 

 

즉 pop을 한다고 해서 실제로 값을 없애는 것이 아닌 그냥 top 변수의 크기를 이용해 비어있는 칸처럼 취급을 하는 것입니다.

---

스택이 가득 찼다고 해서 에러 메시지만 반환하고 스택에 데이터를 넣을 수 없다면 굉장히 불편할 것입니다. 만약 동적 할당을 이용해서 스택을 구현한다면 스택이 가득 찰 때마다 스택의 크기를 더 늘려주면 되니까 해결이 가능할 것입니다. 다음은 C로 구현한 동적 할당을 사용한 스택입니다. 

 

typedef struct {

      char name [10];

      int age;

      int height;

      int weight;

} element;



element *stack = (element *)malloc(sizeof(element));

int capacity = 1;                //capacity는 현재 스택의 크기를 나타내는 변수입니다.

int top = -1; 



void push(element item){

      if (top >= capacity - 1) 
      { 
            stack = (int *)realloc(stack, sizeof(int) * 2 * capacity); 
            capacity *= 2; 
      } 
      stack [++top] = item;       

}



int pop() 
{ 
      if (top == -1) 
            printf("stack empty"); 
      return stack [top--]; 
}

 

 

이상으로 스택의 기본개념에 대해 알아보았습니다. 읽어주셔서 감사합니다.