[열혈자료구조] 6강. 스택(stack)

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다.

 

 

드디어 길고 길었던 연결 리스트가 무려 6개의 포스팅 만에 끝났다!! 이제 6강인 스택에 대해 다뤄 보자. 스택은 지난 번 코딩 연습 때 백준에서 다룬 바 있다.

https://cascade.tistory.com/61

스택(stack)구조란? (백준 9012번, 10828번)

스택의 정의는 지난 번 포스팅을 참고하도록. LIFO 구조라는 건 기억하고 가고, 어떤 기능을 구현해야 하는지를 아래 ADT에서 살펴보도록 하자.

 

스택의 ADT

 

네 가지 기능을 구현하도록 하자.

• PUSH: 스택 안에 데이터를 넣는다.
• POP: 스택 안의 데이터를 제거하고 읽는다.
• PEEK: 스택의 마지막 데이터가 무엇인지 확인한다.
• 스택이 비었는지 확인한다.

1) void StackInit(Stack * pstack);
: 스택을 초기화한다
2) int SIsEmpty(Stack * pstack);
: 스택이 비어 있는지 여부에 따라 1(비어있음), 0(차 있음)을 반환한다
3) void SPush(Stack * pstack, Data data);
: 스택에 Data를 push한다
4) Data SPop(Stack * pstack);
: 스택의 마지막 Data를 pop 한다
5) Data SPeek(Stack * pstack);
: 스택의 마지막 Data를 반환하지만, 삭제하지 않는다.

 

이러한 스택 구조를, 배열과 연결 리스트의 두 가지 방식으로 구현할 수 있다. 먼저 배열을 기반으로 구현하자.

 

배열로 스택 구현하기

배열로 구현하는 것의 단점은, 리스트 때와 마찬가지로 최대 길이가 정해져 있다는 점이다. 배열로 스택을 구현하는 과정에서 중요시해야 할 것은, 첫 요소(가장 낮은 요소)가 인덱스 0이라는 점과 마지막 데이터의 위치이다. 하지만 배열로 스택을 구현하는 것의 장점이 있다. 아주 쉽다는 점이다.

 

위의 ADT에 나와 있는 함수들을 하나씩 구현해 보자. 먼저 StackInit과 SIsEmpty는 간단하게 아래와 같이 할 수 있다.

void StackInit(Stack * pstack){
    pstack->topIndex = -1;
}

int SIsEmpty(Stack * pstack){
    if (pstack->topIndex ==-1){
        return TRUE;
    }
    else{
        return FALSE;
    }
}

 

빈 스택의 topIndex는 -1로 저장하고, 데이터가 하나씩 들어올 때마다 topIndex를 하나씩 늘린다는 규칙을 따른다.

 

다음으로 SPush는 아래와 같이 topIndex를 1 늘리는 동시에 들어온 데이터를 스택에 넣어준다.

void SPush(Stack * pstack, Data data){
    pstack->topIndex ++;
    pstack->stackArr[pstack->topIndex] = data;
}

 

SPop과 SPeek는 빈 스택인지 아닌지 먼저 확인 후, topIndex에 해당하는 수를 본다. 단, SPop은 topIndex를 하나 줄이고, SPeek는 줄이지 않는다.

Data SPop(Stack * pstack){
    if(pstack->topIndex == -1){
        printf("ERROR");
        exit(-1);
    }
    else{
        Data return_item = pstack->stackArr[pstack->topIndex];
        pstack->topIndex --;
        return return_item;
    }
    
}

Data SPeek(Stack * pstack){
    if(pstack->topIndex == -1){
        printf("no data");
        exit(-1);
    }
    else{
        Data return_item = pstack->stackArr[pstack->topIndex];
        return return_item;
    }
}

 

재미있는 점은, 위와 같이 구현한다면 SPop을 했을 때 삭제되었던 마지막 데이터는 스택의 메모리에 아직 남아 있게 된다. 하지만 topIndex가 감소하여 이를 읽을 일이 없으므로 아무런 상관이 없다.

 

연결리스트로 스택 구현하기

연결리스트로 스택을 구현하되, 새로운 노드를 머리에 추가한다고 생각하자. 즉, 스택의 가장 위 층이 head랑 가까운 것이다. 아래와 같은 헤더 파일에서, 각 함수를 구현해 보자.

#ifndef __LB_STACK_H__
#define __LB_STACK_H__

#define TRUE	1
#define FALSE	0

typedef int Data;

typedef struct _node
{
	Data data;
	struct _node * next;
} Node;

typedef struct _listStack
{
	Node * head;
} ListStack;


typedef ListStack Stack;

void StackInit(Stack * pstack);
int SIsEmpty(Stack * pstack);

void SPush(Stack * pstack, Data data);
Data SPop(Stack * pstack);
Data SPeek(Stack * pstack);

#endif

 

먼저, StackInit과 SIsEmpty는 head에 NULL을 주고, head를 읽는 방법으로 구현할 수 있다.

void StackInit(Stack * pstack){
    pstack->head = NULL;
}

int SIsEmpty(Stack * pstack){
    if (pstack->head==NULL){
        return TRUE;
    }
    else{
        return FALSE;
    }
}

 

다음으로, SPush는 head쪽에 새로운 newNode를 추가하는 것이기 때문에, 연결 리스트와 똑같은 방법으로 노드에 data를 할당한 후 추가하면 된다.

void SPush(Stack * pstack, Data data){
    Node * newNode = (Node *) malloc(sizeof(Node));
    newNode->data = data;

    if(pstack->head == NULL){
        pstack->head = newNode;
    }
    else{
        newNode->next = pstack->head;
        pstack->head = newNode;
    }
}

 

나는 위와 같이 작성하긴 했는데, 교재에서는 조건문 없이 newNode->next = pstack->head가 head!=NULL인 경우에도 적용되도록 했다.

Data SPop(Stack * pstack, Data data){
    Data data_return;
    Node * node_return;

    if(pstack->head == NULL){
        printf("Empty stack");
        exit(-1);
    }
    
    node_return = pstack->head;
    data_return = pstack->head->data;
    pstack->head = node_return->next;

    free(node_return);

    return data_return;
}

 

Pop 기능은 스택이 비어있는지 아닌지 확인 후, head와 연결된 노드를 하나 제거하고 그 다음 노드를 head와 이으면 된다. 연결 리스트에서 했던 것과 똑같다. SPeek는 여기서 head의 포인터를 바꾸는 과정을 없애면 되기 때문에, 훨씬 간단하다.

Data SPeek(Stack * pstack, Data data){
    Data data_return;
    if (pstack->head == NULL){
        printf("Empty stack");
        exit(-1); 
    }
    
    data_return = pstack->head->data;
    return data_return;
}