[자료구조] : 스택 (C)

출처 | DO IT C언어 자료구조 입문

이번 시간에는 스택에 대해 알아보자.

• 스택은 데이터를 일시적으로 저장하기 위해 사용하는 자료구조다.

• 데이터의 입력과 출력 순서는 후입선출이다.(LIFO, Last In First Out)

• push : 스택에 데이터를 넣는 작업을 푸시라고한다.

• pop : 스택에서 데이터를 꺼내는 작업

• top : push, pop를 하는 위치 (꼭대기) peek

• bottom : 스택의 가장 밑바닥 부분을 (바닥)bottom이라고 한다.

다음은 함수의 호출과정을 알아보겠다.

void x()
{

}

void y()
{

}

void z()
{
  x();
  y();
}

int main()
{
   z();
}

<함수 호출과정>

1. main 함수를 실행한다.
(main함수를 push)

2. z함수를 호출한다.
(z함수를 push)

3. x함수를 호출한다. 
(x함수 push) / 스택(main - z- x)

4. x함수가 종료되고, z함수로 돌아온다. 
(x함수 pop) /스택(main-z)

5. y함수를 호출한다. 
(y함수 push) / 스택 (main-z-y)

6. y함수를 종료하고 z함수로 돌아온다.
(y함수 pop) /스택(main-z)

7. z함수를 종료하고 main 함수로 돌아온다.
(z함수 pop) / 스택 (main)

8. main 함수를 종료한다.
(main 함수 pop) / 스택 (비어있음)

※전처리기에 관련된 모든 것
https://eskeptor.tistory.com/24 <참고

스택에대한 예제를 보자..

#ifndef ___IntStack
#define ___IntStack

typedef struct {
	int max; // 스택의 최대용량 max
	int ptr; // 스택에 쌓여있는 데이터의 개수를 나타내는 멤버 (스택 포인터라고 한다)
	int* stk; // 스택으로 사용할 배열을 가리키는 포인터
}IntStack;

//스택 초기화
int Initialize(IntStack* s, int max);

// 스택에 데이터를 푸시
int Push(IntStack* s, int x);

//스택에 데이터를 팝
int Pop(IntStack* s, int* x);

// 스택에 데이터를 피크
int Peek(const IntStack* s, int* x);

//스택 비우기
void Clear(IntStack* s);

// 스택의 최대 용량
int Capacity(const IntStack* s);

// 스택의 데이터 개수 
int Size(const IntStack* s);

// 스택이 비어 있나요?
int IsEmpty(const IntStack* s);

// 스택이 가득 찼나요?
int IsFull(const IntStack* s);

// 스택에서 검색
int Search(const IntStack* s, int x);

//모든 데이터를 출력
void print(const IntStack* s);

//스택 종료 
void Terminate(IntStack* s);

#endif

• InStack은 3개의 멤버로 구성된다.

  • stk

    • 스택으로 사용할 배열을 가리키는 포인터
    • 스택으로 푸시된 데이터를 저장할 용도의 배열을 가르킨다. 가장 먼저 푸시된 데이터를 저장하는 곳은 stk[0]이다.
    • 멤버 stk는 배열의 첫 요소를 가리키는 포인터다.
      (배열이 아니다.)

  • max

    • 스택의 최대 용량을 나타낸다.
      이 값은 배열 stk의 요소 개수와 같다.

  • ptr

    • 스택 포인터를 의미한다. 스택에 쌓여 있는 데이터의 개수를 나타낸다.
    • 스택이 비어 있으면 ptr == 0/ 가득 차 있으면 max
    • 가장 먼저 푸시된 바닥의 데이터는 stk[0]
    • 가장 나중에 푸시된 꼭대기(top) 데이터는 stk[ptr-1]이다.

배열 초기화 예제

#include <stdio.h>
#include <stdlib.h>
#include "IntStack.h"

typedef struct 
{
 	int max; // 스택 용량
	int ptr; // 스택 포인터
    int *stk; // 스택을 가리키는 포인터
}IntStack;

int Initialize(IntStack* s, int max)
{
	s->ptr = 0; // 스택 포인터를 0으로 둔다. 왜냐하면 메모리 공간을 만들 때, 스택은 비어 있어야 하기 때문이다.
	if ((s->stk = calloc(max, sizeof(int))) == NULL) // 배열의 생성 실패 했을 경우 
	{
		s->max = 0; // max가 0이라는 의미는 생성 x 
		return -1; // -1를 반환하고 빠져나온다.
	}
	s->max = max; 
	return 0;

}

• 배열을 위한 메모리 공간을 확보하는데, 실패하면 max의 값을 0으로 해야 되는데 이는 존재하지 않는 배열 stk에 대한 함수의 접근을 막기 위해서 사용한다.

Stack Push(데아터 추가)

int Push(IntStack* s, int x) //새로 추가할 데이터 x
{
	if (s->stk >= s->max) // 스택이 가득찬 경우
    //if(s->stk == s->max)도 가능하다.
    //IntStack.c에서 제공하는 함수는 ptr(0~Max)다. 그렇기 때문에 등가 연산자 사용가능
    //부등호를 사용하면 스택 크기의 최댓값과 최솟값을 넘는 액세스를 막을 수 있다.
		return -1; 
     //스택이 가득차면 푸시를 할 수 없으면 -1 반환
	s->stk[s->ptr++] = x; 
    //스택이 가득차지 않으면 x를 배열의 요소 stk[ptr]에 저장
    //ptr를 증가시킨다.
	return 0;

}

• ptr(스택포인터)는 포인터 변수를 의미하는 것이 아니라, 새로운 데이터를 삽입할 인덱스를 기억하는 용도로 사용된다.
• 스택의 인덱스를 가리킨다 = 스택포인터

Stack Pop(데이터 제거)

만약 main에서 pop(&s, &x)라고 호출했다면,

int pop(IntStack* s, int* x) 
{
	if (s->ptr <= 0)
		return -1; //스택이 비어 있어 팝을 할 수 없는 경우에는 -1를 반환
	*x = s->stk[s->ptr--]; // 스택 포인터 ptr의 값을 감소 시키고 stk[ptr]에 저장된 값을 포인터 x가 가리키는 변수에 저장한다.
	return 0;//팝에 성공할 경우 0을 반환 
}

Stack Peek(스택의 꼭대기의 데이터를 보는 함수)

int Peek(const IntStack* s, int* x)
{
	if (s->ptr <= 0)
		return -1;
	*x = s->stk[s->ptr - 1]; 
    //스택이 비어있지 않으면 
    //꼭대기 요소 stk[ptr-1]의 값을 포인터 x가 가리키는 변수에 저장
    //데이터의 입력 및 출력이 없기 때문에 스택 포인터는 변화가 없다.
	return 0; // 피크에 성공하면 0를 반환
}

Stack Clear(스택의 모든 요소를 삭제)

void Clear(IntStack* s)
{
	s->ptr = 0;
    // 스택에 대한 push, pop은 -> 스택 포인터를 바탕으로 이루어진다. (ptr)
    // 스택의 배열 요솟갑을 변경할 필요가 x
    // 모든 요소의 삭제는 ptr = 0으로 하면 끝난다.
}

오늘 배운걸 정리해보자.

1. 스택에 대한 개념
2. 함수의 호출 과정
3. 스택 변수 의미
4. 스택 기능 구현 - push, pop, peek, clear