#2-5. 스택의 개념과 알고리즘 / 함수

스택과 큐는 프로그래밍에서 가장 고전적인 자료구조이며, 그중 스택은 거의 모든 애플리케이션을 만들 때 사용하는 기본 자료 구조이다.

스택의 개념

스택의 기본 개념을 프로그래밍 시각에서 설명하면 다음과 같다.

입력과 출력을 한 방향으로 제한한 자료 구조

스택은 배열과 연결리스트와 비교하면 비교적 간단한 구조로, 삽입과 삭제에서 용이하다.

연결리스트에서 새로운 노드를 삽입하려면 기존의 연결리스트에서 새로운 노드가 삽입될 위치를 검색하고 링크를 연결시켜야 하기 때문이다.

 

스택은 이러한 배열과 연결리스트에 비해 구조가 간단하다.

스택을 단순하게 표현하면 바닥부터 데이터를 쌓는 형식이다. 이렇게 데이터를 쌓는 과정을 푸시(push)라고 한다.

반면 가장 위에 있는 데이터부터 사용하는데 이를 팝(pop)이라고 한다.

푸시(push)	데이터에 순서를 적용해 차례로 저장하는 것.
팝(pop)	가장 최신 데이터부터 차례로 가져오는 것.

이러한 방식을  LIFO(Last In First Out) 형식이라고 한다.

스택의 구현

스택을 구현하려면 스택을 저장하는 메모리 공간과 그에 맞는 하위 자료구조를 선언해야 한다.

이때 하위 자료구조는 배열이나 연결리스트를 사용하는데 이하 포스팅은 연결리스트를 활용하도록 한다.

/*스택을 구현하는 구조체*/
typedef struct Stack{
    int data;
    struct Stack *next;
}IntStack;

int main(){}

위 코드는 이전 포스팅에서 다룬 연결리스트의 형태와 비슷하다. 이를 통해 스택의 구현에서 단일 연결리스트를 응용함을 유추할 수 있겠다.

 

스택을 다룰 구조체를 만들었으니 이제 구조체를 저장할 연결리스트가 필요하다. 이를 위해 Intialize라는 함수를 만들어 헤드와 테일 노드를 선언하도록 한다.

스택의 함수: Push 함수

void Push(IntStack *head, int ipt){
    IntStack *prtStack = (IntStack*)malloc(sizeof(IntStack));
    prtStack->data = ipt;

    prtStack->next = head->next;
    head->next = prtStack;
}

 

함수의 인자로는 헤드 노드와 저장할 값을 받는다.

이때 주의할 점은 스택은 연결리스트와 알고리즘이 다르기 때문에, 로직에 있어 주의해야 한다. 해당 함수를 설명하기 전에 스택이 저장되는 알고리즘에 대해 살펴보자.

	인간의 기준으로 바라본 스택
스택이 선언되고 값이 저장되지 않은 경우	end 🔄 (링크를 본인으로 가짐) ⬆ head
push 함수 실행 1 (A)	end 🔄 ⬆ prtStack(A) ⬆ head
push 함수 실행 2 (B)	end 🔄 ⬆ prtStack(A) ⬆ prtStack(B) ⬆ head
…	…

위와 같이 컴퓨터는 스택을 일자형식으로 '인지'하므로 우리는 이를 세로로 세워 스택형식으로 다시 '해석'할 수 있어야 한다. 이러한 배경을 가지고 위의 Push 함수를 살펴보자.

• 가장 먼저 새로운 스택 노드를 동적할당하여 생성하고 값을 초기화한다.
• 새로 생성한 스택 노드의 다음 링크를 헤드 노드의 다음 링크로 저장한다. 스택은 가장 늦게 입력된 값이 가장 먼저 나가기 때문이다!  가장 주의해야 할 점이다.
• 헤드 노드의 다음 링크를 새로 생성한 스택 노드로 설정한다. 다시 말해 스택의 가장 첫 번째 값은 가장 최근에 들어온 값이 되는 것이다.

스택의 함수: Pop 함수

pop 함수는 매개변수로 헤드 노드 위치를 받고 반환값을 가진다. 이 반환값은 현재 스택에 저장돼 있는 최상위 값으로 설정한다.

int pop(IntStack *head){
    IntStack *delStack = (IntStack*)malloc(sizeof(IntStack));

    delStack = head->next;
    delStack->next = delStack->next->next;
    int val = delStack->data;
    free(delStack);

    return val;
}

Pop 함수는 Push 함수보다 설명이 길 뿐 비교적 간단하다. 로직은 다음과 같다.

• 먼저 삭제할 스택노드를 저장하기 위해 임시 삭제 노드를 생성한다.
• 삭제할 노드를 저장할 노드에 head의 다음 링크를 선언한다. 이는 배열의 첫 번째 값이 저장된 노드이다.
• 배열의 첫 번째 값이 저장된 노드값 즉, delStack-> data를 임의의 변수 val에 저장한다. 이는 반환값으로 사용한다.
• 헤드 노드의 다음 링크를 헤드노드의 (다음다음) 링크로 지정한다. 다시 말해 링크 하나를 뛰어넘는다.
• 노드를 삭제하기 위해 생성한 delStack 노드를 동적해제하여 메모리 공간에서 삭제한다.

Pop 함수의 알고리즘을 표를 통해 다시 알아보자.

	인간의 기준으로 바라본 스택
Push 함수가 실행된 상태 (스택에 값이 저장되있음)	end 🔄 ⬆ prtStack(A) ⬆ prtStack(B) ⬆ head
Pop 함수 실행 (i) ( 삭제할 노드(delStack) = head -> next )	end 🔄 ⬆ prtStack(A) ⬆ prtStack(B) ▶delStack ⬆ head
반환값 초기화	int val = delStack->data;
삭제할 노드 삭제 / 스택 삭제 ( head -> next = head -> next->next )	end 🔄 ⬆ prtStack(A) ⬆ head

전체 코드

#include  <stdio.h>
#include  <string.h>
#include  <stdlib.h>
/*스택을 구현하는 구조체*/
typedef struct Stack{
    int data;
    struct Stack *next;
}IntStack;

// void InitializeStack(IntStack *head, int data){}

void Push(IntStack *head, int ipt){
    IntStack *prtStack = (IntStack*)malloc(sizeof(IntStack));
    prtStack->data = ipt;

    prtStack->next = head->next;
    head->next = prtStack;
}

int Pop(IntStack *head){
    IntStack *delStack = (IntStack*)malloc(sizeof(IntStack));

    delStack = head->next;
    head->next = head->next->next;
    int val = delStack->data;    
    free(delStack);

    return val;
}

void Print(IntStack *head,IntStack *tail){
    /*순회용 노드*/
    printf("[스택의 값 출력]\n");
    IntStack *cnt = head->next;
    while(cnt != tail){
        printf("%d",cnt->data); if(cnt->next != tail)printf("\n");
        cnt = cnt->next;
    }
}

int main(){
    IntStack *head = (IntStack*)malloc(sizeof(IntStack));
    IntStack *tail = (IntStack*)malloc(sizeof(IntStack)); 

    head->next = tail;
    tail->next = tail;

    for(int i=0;i<5;i++){
        Push(head,(i+1)*10);
    }
    Print(head,tail);
    // if(cnt != tail)
    printf("\n\n--Pop 함수 사용--\n\n");
    Pop(head); Print(head,tail);
}

[알고리즘 문제 풀이 전략] 교재와는 조금 다르게 프로그래밍하였지만 기존 함수의 로직은 그대로 사용하였음.