[C로 만드는 자료구조]스택(Stack) - 배열

스택(Stack)

이번에는 자료구조중 스택(Stack)을 알아보겠습니다.

스택이라는 것은 Stack이라는 단어의 사전적 의미에서도 볼 수 있고 위의 그림에서 볼 수 도 있듯이 쌓아놓은 더미를 뜻합니다.

스택(Stack)의 특징

스택은 후입선출(LIFO)의 특징을 가지고 있습니다. LIFO란 Last-In-First-Out으로 가장 나중에 들어온것이 가장 먼져 나간다는 것을 의미합니다. 말그대로 상자를 쌓아뒀다가 제일 밑에 것을 빼내고 싶으면 위에 것들을 다 치운다음 제일 밑에 것을 움직 일 수 있는 것과 같다고 생각하면 됩니다.

스택(Stack)의 구조

스텍은 후입선출의 구조를 가지므로 입구가 하나라고 생각할 수 있습니다. 구조는 다음과 같이 볼 수 있습니다. 스택의 가장 위쪽인(가장 나중에 들어온 자료) top, 스택의 가장 아래인(가장 먼저 들어온 자료) bottom으로 이루어 져 있습니다.

스택(Stack)의 연산

스택의 연산은 크게는 2가지로 볼 수 있습니다.

• push() : 스택에서 데이터를 추가하는 연산
• pop() : 스택에서 제일위에 있는 데이터를 삭제하는 연산

위의 그림에서 볼 수 있듯이 선입 후입선출의 구조를 따라 움직이는 것과 2 연산의 기능을 그림으로 확인할 수 있습니다.

스택(Stack)의 용도

스택은 입력과 역순의 출력이 필요한 경우에 사용을 하게됩니다. 따라서 다음 기능에서 스택을 사용하게 됩니다.

• 에디터등에서 되돌리기(undo) 기능 구현시
• 함수호출에서 복귀주소 기억시 (메모리 stack 영역)

스택(Stack)의 구현(배열)

스택은 다음과 같은 구조체들을 이용하여 구현하게됩니다.(배열)

#include<cstdio>
#define MAX_STACK_SIZE 100
 
typedef int element;
 
struct Stack_element
{
    element data;
};
struct STACK
{
    int top = -1; // 현재 배열에 들어간 인덱스 숫자
    Stack_element Array[MAX_STACK_SIZE];
};
 

top이라는 변수를 이용하여 이 스택이 어디까지 데이터가 들어가있는지 확인하는 기준으로 삼습니다. top 변수의 숫자는 데이터가 마지막에 들어있는 배열의 인덱스 숫자와 같습니다. 그리고 구현시에 배열의 0번지를 bottom으로 생각하였으면 배열의 뒤쪽으로 차례 차례 데이터가 들어온다고 생각하여 만들었습니다.

ADT (배열)

• Push()
  
  

  void PUSH(STACK *S, element item)
  {
      S->top += 1;
      S->Array[S->top].data = item;
  }

  데이터를 밀어 넣는 함수입니다.
  
  

• POP()
  
  

  element POP(STACK *S)
  {
      element temp = S->Array[S->top].data;
      S->top -= 1;
      return temp;
  }

  데이터를 빼내는 함수입니다. 후입선출(LIFO)방식이기 때문에 제일 뒤에 있는 데이터를 처음 빼줍니다.
  
  

• Peek()
  
  

  element PEEK(STACK *S)
  {
      return S->Array[S->top].data;
  }

  현재 제일 마지막 (제일 위)에 있는 데이터가 무엇인지 확인하는 ADT입니다.
  
  

• empty() & full()
  

  void Is_Empty(STACK *S)
  {
      if (S->top == -1)
          printf("Stack is empty\n");
      else
          printf("not empty\n");
  }
  void Is_FULL(STACK *S)
  {
      if (S->top == MAX_STACK_SIZE)
          printf("Stack is FULL\n");
      else
          printf("Stack is not FULL\n");
  }

  비어있는지 꽉 찼는지 확인하는 함수 들입니다.
  
  

이렇게 배열로 만든 스텍을 알아보았습니다. 다음 포스팅에서는 동적할당을 이용한 스택을 구현해 보겠습니다.