yoongrammer

[자료구조] 스택(Stack) 구현하기 in C 본문

자료구조 (Data structure)

[자료구조] 스택(Stack) 구현하기 in C

yoongrammer 2021. 1. 13. 18:53
728x90

목차

    스택(Stack) 구현하기 in C


    스택 자료형을 구현하는 방법은 일반적으로 다음 방법들을 사용합니다.

    • 배열 기반으로 구현
    • 동적 배열을 기반으로 구현
    • 연결 리스트로 구현

    배열 기반으로 구현


    배열을 사용하여 스택을 구현하는 방법입니다.

    배열 index를 추적하는 top변수를 사용합니다.

    top은 -1로 초기화합니다.

    top이 -1이라면 스택이 비어있다는 의미이고 배열 크기-1이라면 스택이 가득 찼다는 의미입니다.

    push연산은 top을 1 증가시키고 값을 top위치에 저장하도록 구현합니다.

    pop연산은 top을 1 감소시키도록 구현합니다.

     

    C 언어로 구현하면 다음과 같습니다.

    #include <limits.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct ArrayStack {
      int top;
      int capacity;
      int* array;
    } Stack;
    
    /* 주어진 capacity 크기로 stack을 생성하는 함수 */
    Stack* createStack(int capacity) {
      Stack* stack = (Stack*)malloc(sizeof(Stack));
      if (!stack)
        return NULL;
      stack->capacity = capacity;
      stack->top = -1;
      stack->array = (int*)malloc(stack->capacity * sizeof(int));
      return stack;
    }
    
    /* 스택이 비어있는지 확인하는 함수. */
    int isEmpty (Stack* stack) {
      return (stack->top == -1);
    }
    
    /* 스택이 가득찼는지 확인하는 함수. */
    int isFull (Stack* stack) {
      return (stack->top == stack->capacity - 1);
    }
    
    /* top 위치에 있는 값을 가져오는 함수 */
    int peek (Stack* stack) {
      if(isEmpty(stack))
        return INT_MIN;  
      return stack->array[stack->top];
    }
    
    /* 스택에 값을 추가하는 함수 */
    void push(Stack *stack, int data) {
      if (isFull(stack))
        printf("Stack is full\n");
      else {
         /* top을 1증가시키고 값을 top에 저장함 */
        stack->array[++stack->top] = data;
        printf("%d pushed to stack\n", data);
      }
    }
    
    /* 스택에 값을 삭제하는 함수 */
    int pop(Stack* stack) {
      if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return INT_MIN;
      }
      else /* top의 값을 1 감소시킴 */
        return (stack->array[stack->top--]);
    }
    
    void main() 
    {
      Stack* stack = createStack(3);
      
      push(stack, 1);
      push(stack, 2);
      push(stack, 3);
      push(stack, 4);
      
      printf("%d poped from stack\n", pop(stack));
    }

    Output:

    1 pushed to stack
    2 pushed to stack
    3 pushed to stack
    Stack is full
    3 poped from stack

    배열로 구현 시 스택의 사이즈는 동적이 아니기 때문에 꽉 찬 스택에 push를 할 수 없는 문제점이 있습니다.

    동적 배열을 기반으로 구현


    배열 문제점은 동적 배열을 사용하면 해결할 수 있습니다.

    push연산 시, 배열이 꽉 차있다면 길이가 2배인 새로운 배열을 만들고 이전 배열에 있던 데이터들을 새로운 배열에 복사한 뒤 push를 수행합니다.

     

    push 함수를 동적 배열로 동작하도록 수정하면 다음과 같습니다.

    void push(struct Stack *stack, int data) {
      if (isFull(stack)) { /* stack이 가득 찼다면 크기를 2배로 늘립니다. */
        stack->capacity *= 2; 
        stack->array = realloc(stack->array, stack->capacity);
      } 
      /* top을 1증가시키고 값을 top에 저장함 */
      stack->array[++stack->top] = data;
      printf("%d pushed to stack\n", data);
    }

    하지만, 데이터를 새로운 배열에 복사하는 작업은 오버해드가 크다는 문제점이 있습니다.

    연결 리스트로 구현


    연결 리스트로 스택을 구현하면 리스트 앞에 노드를 추가하거나 삭제하면 되기 때문에 자유롭게 사이즈를 증가시키거나 줄일 수 있습니다.

    Push연산은 리스트 맨 앞에 새로운 노드를 추가하도록 구현합니다.

    Pop연산은 리스트 맨 앞 노드를 삭제하도록 구현합니다.

     

    C언어로 구현하면 다음과 같습니다.

    #include <stdio.h>
    #include <stdlib.h>
    #include <limits.h>
    
    typedef struct ListStack
    {
      int data;
      struct ListStack *next;
    } Stack;
    
    int IsEmptyStack (Stack *Top)
    {
      return (Top == NULL);
    }
    
    void push (Stack **Top, int data)
    {
      Stack *newNode = NULL;
      
      newNode = (Stack*)malloc(sizeof(Stack));
      if(newNode == NULL)
      {
        printf("Stack is full\n");
        return;
      }
      /* 리스트 맨 앞에 새로운 노드를 추가합니다. */
      newNode->data = data;
      newNode->next = *Top;
      *Top = newNode;
       
      printf("%d pushed to stack\n", data);
    }
    
    int pop (Stack **Top)
    {
      Stack *temp = NULL;
      int data = 0;
      if(IsEmptyStack(*Top))
      {
        printf("Stack is Empty\n");
        return INT_MIN;
      }
      else
      { /* Top 위치(리스트 맨 앞)에 있는 노드를 제거합니다 */
        temp = *Top;
        *Top  = temp->next;
        data = temp->data;
        free(temp);
      }
      return data;
    }
    
    void main(void)
    {
      Stack *S =NULL;
    
      push(&S, 1);
      push(&S, 2);
      push(&S, 3);
    
      printf("%d poped from stack\n", pop(&S));
    }

    Output:

    1 pushed into stack
    2 pushed into stack
    3 pushed into stack
    3 popped from stack

     

    소스 코드는 아래 깃허브에서 받을 수 있습니다.

    github.com/dev-yyh/C/tree/main/DS/stack

     

    728x90
    Comments