STACK(스택)이 뭔가요?[1]

본 포스트는 c언어를 중심으로 작성되었습니다.

 

STACK(스택)이 뭔가요?

스택.. 롤 하신분이라면 압니다. 필자 또한 롤을 즐겨했고, 요즘 롤은 참고로 전혀 몰라요. 근데 예전에 메자이 스택 아시겠죠? 뭔지?

 

르블랑이 메자이 풀스택이면 게임은 끝

요놈 말입니다 ㅋㅋ.. c에서 스택이 그냥 이거에요!

 

스택 자료구조는 하나하나 데이터를 차곡차곡 쌓아올린 형태의 자료구조 중 하나입니다. 스택은 동일한 구조, 크기의 데이터를 정해진 방향으로만 쌓을 수 있습니다. 또한 최상위 층부터 접근하도록 제한되어 있는데 이말은 그냥 블록쌓기 마냥 아래에서 위로 쌓인다는 말입니다. 

 

스택의 논리적구조

위와 같이 제일먼저들어온 구조가 1이라면 제일 마지막에 들어온 구조는 n번째 항에 속합니다. 즉 가장 마지막에 들어온 데이터가 제일 먼저 삭제가 되는 순차적 구조를 따르는것입니다. 이러한 동작 구조를 후입선출방식 (Last in - First out) LIFO방식이라고 합니다.

 

스택의 구현

그렇다면 스택은 배열에서 사용하는 순차식 자료구조나 포인터변수를 사용하는 연결리스트 등 앞서 포스팅한 그런 것들로 구현할 수 있습니다.

 

위의 그림을 구현한것을 다시 물리적 구조로 표현해보겠습니다.

[0]첫번째 데이터

[1]두번째 데이터

- - -

[n]n번째 데이터

로 표현할 수 있습니다. 그렇다면 실제 코드상에선 어떻게 구현될지 직접 코드로 구현해보았습니다.

#include <stdio.h>
#include <stdlib.h>
#define STACK_SIZE 200
 
typedef int value;
//우선 스택에 들어갈 밸류의 자료형을 인트로 사용자 정의 합니다.
 
value stack[STACK_SIZE];
int x = -1;
 
int isNULL()
{
    if(x == -1)return 1;
    else return 0;
    //본 함수에서는 스택이 null인지 확인을 합니다.
    //만약 처음 선언한 x의 값이 그대로 -1이라면 1을 반환하며 종료하겠죠
}
 
int isOkay()
{
    if(x == STACK_SIZE -1)return 1;
    else return 0;
    //본 함수에서는 스택이 가득찬 상태인지 확인을 합니다.
}
 
void inIt(value data)
{
    if(isOkay())
    {
        printf("스택이 가득 차서 더이상 삽입은 불가능합니다");
        return;
    }
    else stack[++x] = data;
    //만약 스택이 꽉 찬상태가 아니라면 맨 위 블록을 증가 시킨 후에
    //데이터를 삽입할 수 있을 것입니다.
}
 
//스택의 맨 윗부분에서 원소를 삭제합니다
//이는 리스트 등에서 데이터를 삭제하는것과 비슷합니다
value pop()
{
    if(isNULL())
    {
        printf("\n 스택이 비어있습니다.");
        return 0;
    }
    else return stack[--x];
    //현재 맨위의 데이터를 삭제한 후 다시 크기를 감소해야합니다.
}
 
value search()
{
    if(isNULL())
    {
        printf("\n 스택이 비어있습니다");
        return 0;
    }
    else return stack[x];
    //찾고싶은 데이터를 검색도 해봐야겠죠.
    //공백상태가 아니라면 맨 위의 데이터를 확인해갈것입니다.
}
 
//출력하는 함수입니다
void Print()
{
    int a;
    printf("\n STACK = [");
    for(a=0; a <= x; a++)
    {
        printf("%d",stack[a]);
    }
    printf("] ");
}
 
int main()
{
    value data;
    printf("\n 스택의 구조에 대해서 알아보자");
    Print();
    inIt(1); Print();
    inIt(2); Print();
    inIt(3); Print();
    //데이터에 1,2,3을 삽입하고 각각 출력해봅니다
 
    data = search();Print();
    printf("search  = %d",data);
    //최상위 데이터를 출력합니다
 
    data = pop(); Print();
    printf("\n pop : %d",data);
 
    data = pop(); Print();
    printf("\n pop : %d",data);
 
    data = pop(); Print();
    printf("\n pop : %d",data);
 
    return 0;
}
 
 

 

출력결과는 

스택의 구조에 대해서 알아보자

STACK = []

STACK = [1]

STACK = [12]

STACK = [123]

STACK = [123] search = 3

STACK = [12]

pop : 2

STACK = [1]

pop : 1

STACK = []

pop : 0

 

위와 같이 나옵니다. 순차자료구조를 사용하여 구현했기 때문에 좀 간단하죠? 이해가 안가실 부분은 딱히 없을것 같지만, 의문이 들거나 제가 잘못된점이 있다면 댓글부탁드립니다.

 

이번엔 포인터 변수를 이용한 연결리스트에서의 스택을 구현해보겠습니다.

 

포인터 변수를 이용한 연결리스트

 

다음 포스트로 넘어갑니다.

 

댓글/ 피드백 환영합니다!!