[자료구조] c언어 구조체로 스택 구현하기

스택(Stack)이란?

스택은 데이터를 후입선출(LIFO:Last-In First-Out)하는 자료구조로, 가장 최근에 들어온 데이터가 가장 먼저 나간다는 특징이 있다.

상자나 책을 쌓아놓은 더미를 생각하면 이해하기 쉬울 것이다. 이번 글에서는 스택을 배열 구조체를 이용해서 구현해 볼 것이다.

스택 타입 구조체 정의 및 초기화 함수

#include <stdio.h>
#define SIZE 100

typedef int element; // 배열안에 들어오는 값의 타입을 element로 한번에 지정

typedef struct {
  element data[SIZE];
  int top; // Index 번호
} StackType;

// 초기화
void init(StackType *S)
{
  S -> top = -1; // 포인터 연산자로 top에 접근해서 -1로 초기화
}

스택의 요소에 해당하는 data 배열과, 스택의 index 번호에 해당하는 top을 포함하는 StackType 구조체를 선언한다.

에러체크함수 is_full(), is_empty()

• is_full함수는 스택이 공백상태인지 아닌지를 검사한다.
• is_empty함수는 스택이 포화상태인지 아닌지를 검사한다.

// 에러 체크 함수
int is_full(StackType *S)
{
  return S->top == SIZE - 1;
}

int is_empty(StackType *S)
{
  return S->top == -1;
}

삽입함수 push()

push함수는 스택에 데이터를 추가한다. 만약 스택이 가득 차있다면 더이상 넣을 공간이 없으므로 가득 차있다는 문구를 출력한다.

// 삽입
void push(StackType *S, element e)
{
  if (isFull(S))
    printf("Overflow\n");
  else
  {
    S->top++;              // top을 하나 증가시킨후
    S->data[S->top] = e;   // 데이터를 삽입한다
  }
}

삭제함수 pop()

pop함수는 스택에서 데이터를 삭제하고, 그 데이터를 반환한다. 만약 스택이 비어있는 상태라면 동작하지않고 비어있다는 문구를 출력한다.

// 삭제
element pop(StackType *S)
{
  if (is_empty(S))
  {
    printf("Empty\n");
    return -1;
  }
  else
  {
    element e = S->data[S->top]; // 가장 상위에 있는 데이터를 e에 저장한 후
    S->top--;                    // top을 하나 감소시킨다
    return e;
  }
}

조회함수 peek()

peek함수는 스택에서 데이터를 삭제하지 않고 들여다 보기만 하는 함수이다. pop과 마찬가지로 스택의 비어있음을 체크한다.

// 조회
element peek(StackType *S)
{
  if (is_empty(S))
  {
    printf("Empty\n");
    return -1;
  }
  else
  {
    return S->data[S->top];
  }
}

스택 출력 함수 print()

print함수를 만들어 스택을 처음부터(0) 끝까지(top) 차례로 출력함으로써 확인할 수 있다.

void print(StackType *S)
{
  for (int i = 0; i <= S->top; i++)
  {
    printf("%c ", S->data[i]);
  }
  printf("\n");
}

전체 코드

스택을 구현한 전체 코드는 아래와 같다. (더보기)

#include <stdio.h>
#define SIZE 100

typedef int element;

typedef struct
{
  element data[SIZE];
  int top; 
} StackType;

// 초기화
void init(StackType *S)
{
  S->top = -1;
}

// 에러 체크 함수
int is_empty(StackType *S)
{
  return S->top == -1;
}

int is_full(StackType *S)
{
  return S->top == SIZE - 1;
}

// 삽입
void push(StackType *S, element e)
{
  if (is_full(S))
    printf("Overflow\n");
  else
  {
    S->top++;
    S->data[S->top] = e;
  }
}

// 삭제
element pop(StackType *S)
{
  if (is_empty(S))
  {
    printf("Empty\n");
    return -1;
  }
  else
  {
    element e = S->data[S->top];
    S->top--;
    return e;
  }
}

// 조회
element peek(StackType *S)
{
  if (is_empty(S))
  {
    printf("Empty\n");
    return -1;
  }
  else
  {
    return S->data[S->top];
  }
}

void print(StackType *S)
{
  for (int i = 0; i <= S->top; i++)
  {
    printf("%c ", S->data[i]);
  }
  printf("\n");
}

int main()
{
  StackType S;
  init(&S);

  pop(&S);
  push(&S, 'a');
  push(&S, 'b');
  push(&S, 'c');
  print(&S);

  element p = pop(&S);
  printf("%c\n", p);
  print(&S);
}

도움이 되었다면 아래 '공감' 버튼을 눌러주세요! 읽어주셔서 감사합니다 :)