포스트

[스택] 스택의 기초와 고정 크기 스택 구현

게시 업데이트
By Yun Hyeok Nam
18 분읽는 시간

📚 스택이란?

Stack of Books 책 무더기

영어단어 스택(Stack)이란 명사로는 무더기, 혹은 동사로는 쌓다, 쌓이다 라는 뜻을 가지고 있다.

자료구조에서 스택은 어떤 자료들을 쌓아놓은(stacked) 형태의 자료구조를 의미한다. 어떤 의미있는 자료들을 순서대로 받아와서 아래부터 차곡차곡 쌓고, 위에서부터 순서대로 하나씩 제거하며 자료들을 사용한다. 이를 선입후출 (LIFO - Last In, First Out) 원칙을 따른다고 한다. 먼저 들어간 자료는 (그 뒤로 들어간 자료들 보다) 나중에 나온다.

문서 작성시에 Ctrl-z를 눌러 실행취소를 하는 것을 생각해보자. 프로그램은 사용자가 한 작업을 순서대로 기억하고 있다가, 실행취소 키를 누르면 가장 마지막에 한 작업 1개를 되돌릴 수 있다. 여러번 실행취소 키를 누르면 사용자가 한 작업의 역순으로 여러번 작업을 되돌릴 수도 있다.

스택 자료구조를 사용하는 대표적인 경우가 프로그램 실행에 사용되는 호출스택이다.

호출스택 비주얼스튜디오에서 호출스택 창을 확인한 모습

  • 호출된 순서 : main() 👉 foo() 👉 bar()
  • 함수가 끝나고 호출된 곳으로 되돌아가는 순서 : main() 👈 foo() 👈 bar()

현재 코드에서 bar()함수가 끝났다면 어디로 돌아가야할까? 바로 자신을 호출한 bar()일 것이다. 마찬가지로 bar()또한 끝났다면 자신을 호출한 main()으로 돌아가야한다. 즉, 각 함수가 끝나고 되돌아가는 (이를 Return, 복귀한다 라고 한다) 순서는 호출된 순서의 반대인 main() 👈 foo() 👈 bar()이다.

간단하게 이야기하자면, 함수를 호출하면서 순서대로 각 함수의 주소를 차곡차곡 쌓아두고, 각 함수가 할 일을 다 해서 불러진 곳으로 리턴할 때, 호출스택으로부터 저장된 주소를 제거해서 가지고와 그 주소로 리턴하면된다. (엄밀하게 이야기하자면 활성레코드와 관련있지만 그것은 여기서 중요하지않다.)

📖 스택 용어

스택의 모습 스택의 구조

  • 스택 최상단 요소 : Top
    • 스택 밑바닥 요소 : Bottom
  • 스택에 삽입 : Push
  • 스택에서 제거 : Pop
  • 스택에서 제거하지 않고 top 요소를 보기 : Peek

스택에서의 자료를 넣는 구멍은 단 하나이다. 이 말은 자료를 빼낼 수 있는 구멍도 단 하나라는 것이다. 넣고 뺄 수 있는 이 구멍으로 볼 때 우리 눈에 보이는 것은 스택 꼭대기에 있는 자료밖에 보이지 않을 것이다. 이때 현재 스택 최상단에 있는 자료를 Top이라고 하고, 반대로 맨 아래에 있는 자료를 Bottom이라고 부른다. 스택에 자료를 삽입하는 행위를 Push, 스택으로부터 자료를 뽑아 가져오는 것을 Pop, Top에 어떤 자료가 있는지 보기만 하는 것을(자료를 제거하지 않음) Peek라고 한다.

💡 C언어에서 스택의 구현 방법

C언어에서 스택을 구현할 수 있는 방법에는 몇가지가 있다. 이 글에서는 첫번째 방법, 고정 크기 스택 구현방법에 대해 알아본다.

🚀 스택의 추상 자료형 (정적 크기)

스택을 C언어로 구현하기에 앞서 우선 어떻게 스택을 구현할 것인지, 스택에서 꼭 필요한 연산과 변수들을 추상자료형으로 정리해보자. 일단은 크기가 생성시에 고정되어 바꿀 수 없는 스택에 대해서 정리한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

변수:
    - 크기가 고정된 배열
    - 현재 top 요소가 들어있는 인덱스

주요 연산:
    - push() # 스택에 데이터를 삽입
    - pop()  # 스택에 데이터를 제거 후 그 데이터를 리턴
    - peek() # 스택에서 데이터를 제거하지 않고 읽어오기

기타 연산:
    - init()     # 스택 초기화
    - is_empty() # 스택이 다 비어있는가?
    - is_full()  # 스택이 다 찼는가? (고정 크기 배열을 사용하기 때문에 스택이 다 찰 수도 있다.) 
    - print()    # 스택 전체 모습을 출력

배열을 사용하는 고정 크기 스택에서는 top 인덱스 변수와 배열을 통해 스택 자료구조를 관리한다.

💡 고정 크기 스택의 구현

아쉽게도 C언어에서는 class를 통한 객체지향 개념을 지원하지 않는다. 여기서는 구조체와 외부 전역함수를 통해 스택을 구현한다.

스택의 초기화

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#define MAX_SIZE 32  // 스택의 최대 사이즈
typedef int element; // 스택에 넣을 자료의 자료형 element (여기서는 int)

// 고정 크기 스택 FixedStack 구조체 선언
typedef struct _FixedStack
{
    element arr[MAX_SIZE]; // MAX_SIZE크기 스택 배열
    int top;               // 스택 top 요소의 인덱스
} FixedStack;

// 스택 초기화 함수
void stack_init(FixedStack* s)
{
    s->top = -1; // 빈 스택 = top 인덱스 변수를 -1일때로 하자.
}

스택에 담을 요소의 자료형은 typedef int element를 통해 int형에 element라는 별명을 지어줬다. 즉 int와 element는 같은 것이다.

그 후 스택 구조체를 선언한다. 데이터들을 담을 배열 arr[]와 top 요소의 인덱스를 나타낼 top 변수로 구성된다.

스택 구조체 변수를 초기화 해 줄 void stack_init() 함수에서는 스택 내 top 인덱스 값을 -1로 초기화 시켜준다. top 인덱스가 -1이라면 빈 스택을 나타내고, 만약 MAX_SIZE - 1의 값이라면 스택이 꽉 찬 상태를 의미한다. (C언어에서 배열의 첫 요소의 인덱스는 0이므로, MAX_SIZE 크기의 배열에서 마지막 요소의 인덱스는 MAX_SIZE - 1일 것이다.)

이때, 스택 구조체 멤버를 수정해야하므로 포인터를 사용해 Call by reference 형식으로 구현하던가, Call by value1로 복사본을 넘겨 함수 내에서 수정한 구조체를 다시 리턴해주는 방법이 있다. 여기서는 포인터를 사용한 방식을 채택했다.

스택이 비었나요? 스택이 꽉 찼나요?

1
2
3
4
5
6
7
8
9
10
11

// 스택이 비었다면 1, 비어있지 않다면 0을 리턴
int stack_is_empty(FixedStack* s)
{
    return (s->top == -1);
}

// 스택이 꽉 찼다면 1, 꽉 차지않았다면 0을 리턴
int stack_is_full(FixedStack* s)
{
    return (s->top == MAX_SIZE - 1);
}

이 뒤로 사용할 연산에서는 스택이 비었거나 꽉 차있지 않은가를 따져가며 연산을 구현해야한다. 이를 편하게하기 위해 스택이 비었는지와 꽉 찼는지 상태를 리턴하는 두가지 함수를 구현한다. C언어에서는 bool 자료형을 지원하지 않는다. 따라서 int형을 이 두 함수의 리턴타입으로 지정한다. 만약 s->top == -1이 참이라면 1을, 거짓이라면 0을 리턴할 것이기 때문이다.

C언어에서는 숫자 0을 제외한 모든 값이 참입니다! 0은 거짓입니다!

스택에 삽입, Push!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// 스택 s에 새 요소 e를 삽입
void stack_push(FixedStack*s, element e)
{
    // 스택이 꽉 찼다면 삽입할 수 없습니다
    if (stack_is_full(s))
    {
        printf("Stack is full!\n");
        return;
    }
    // 스택에 여유자리가 있으면 삽입
    else
    {
        ++s->top;           // 현재 top 요소의 다음 인덱스에다가
        s->arr[s->top] = e; // 삽입할 요소 e 삽입!
    }
}

stack-push Push 연산

스택에 삽입하는 Push연산에서는 현재 top 의 인덱스의 다음 인덱스에 삽입할 요소를 넣으면 된다. 다만 고정 크기 스택인 만큼 스택이 꽉 찼다면 삽입을 할 수 없다는 점을 기억하자.

1

s->arr[++s->top] = e;

혹은 전위연산자를 사용해 한줄로 해도 된다.

스택에서 제거, Pop!

1
2
3
4
5
6
7
8
9
10
11

// 스택 s로부터 요소를 pop
element stack_pop(FixedStack* s)
{
    // 스택이 비어있다면 요소를 제거할 수 없음. 비어있지 않을 때만 동작
    if (!stack_is_empty(s))
    {
        element pop = s->arr[s->top]; // top 요소를 임시저장
        --s->top;                     // top 인덱스를 하나 감소
        return pop;                   // 임시저장한 top 요소를 리턴
    }
}

stack-pop Pop 연산 스택에서 요소를 제거해오는 함수는 위와 같이 구현한다. 우선 비어있는 스택에서는 아무것도 제거할 수 없으므로 스택이 비어있지 않을 때만 동작하게 한다. 이후 top 요소를 기억해두고, 스택에서 1개를 제거하므로 단순히 top 인덱스를 하나 감소시키면 된다. 이후 기억해둔 요소를 리턴해주면 끝이다.

1

return s->arr[s->top--];

혹은 후위연산자를 사용해서 한줄로 쓸 수 있다.

기타 연산

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// 스택에서 pop하지않고 top 요소 보기
element stack_peek(FixedStack* s)
{
    return s->arr[s->top];
}

// 스택 출력
void stack_print(FixedStack* s)
{
  printf("<  Stack  >\n");

  if (stack_is_empty(s))
    printf("-- Empty stack --\n");
  else
  {
    // top ~ 0 인덱스까지 상단에서 하단 방향으로 배열 출력
    for (int i = s->top; i >= 0; --i)
        printf("   [ %2d ]\n", s->arr[i]);
  }
  printf("\n");
}

스택의 top 요소를 알 수 있는 Peek 함수와 스택을 출력하는 함수는 이렇게 구현하면 된다. 출력하는 함수는 현재 배열을 사용하고 있으므로 단순히 배열을 for문을 통해 출력하면 된다.

💻 코드 전체

pastebin 보러가기

⭐정리

  • 스택이란 선입후출의 원칙을 따르는 선형 자료구조이다.
  • 스택에서 필요한 것은 최상단의 요소 top 요소이다.
  • 스택에 삽입하는 것을 push, 스택에서 요소를 제거하는 것을 pop이라 한다.
  • 고정 크기 스택은 간단하게 배열을 통해 구현할 수 있다.

참고서적 : C언어로 쉽게 풀어쓴 자료구조 (개정 3판), 천인국·공용해·하상호, 생능출판 - Yes24바로가기

  1. 1
2
3
4
5
6
7
8

    FixedStack stack_init(FixedStack s)
{
    s.top = -1; // 복사본을 수정
    return s;   // 복사본을 다시 리턴
}
// main() 함수에서...
FixedStack s1;
s1 = stack_init(s1); // 복사되어 수정된 s1로 자신을 대치한다.

    C언어에서는 Call by value만을 지원한다. 포인터를 통해 Call by reference를 흉내내는 것이다. 함수의 매개변수를 넘기면 그 값은 무조건 복사되어 넘어간다. 포인터도 마찬가지다. 변수의 주소를 담고 있는 포인터 변수가 복사되어 넘어간다. 다만 함수 내부에서 포인터 변수가 담고 있는 내용물인 주소를 수정하는 것이 아니라, 주소가 가르키는 곳만을 수정하는 것이면 복사본-원본 불일치 문제를 생각할 필요가 없다.

    만약 인자로 넘긴 포인터 변수 자체에 수정을 가해야한다면, ** 이중 포인터 사용을 감안해야할 것이다… 이런 문제 때문에 필자가 참고한 책에서는 위와 같은 방법을 사용하기도 한다.

    여기서 FixedStack s자리에 넘긴 인자 s1이 통째로 복사되어 함수 내에서 사용된다. 함수 내에서 복사본이 수정되었고, 외부에서 넘겨준 원본은 그대로이다. 따라서 수정본을 다시 리턴해주어 원본에 대치(replace)해주어야 한다. ↩︎

Data structure with C
c data structure
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.