[자료구조] 스택(stack) 의 개념과 이해 | c언어 스택 구현

스택(Stack) 이란?

스택은 접시가 쌓인 것과 비슷하다

 

스택 자료구조는 마치 접시가 쌓이는 것과 비슷하다. 당신이 접시를 쌓는다면 아래부터 위로 차근차근히 접시를 쌓게 될 것이다. 이 때 가장 위에 있는 접시를 가장 먼저 꺼낼 수 있을 것이고 가장 아래에 있는 접시는 가장 나중에 꺼낼 수 있을 것이다. 스택도 이와 동일하다. Last In First Out(LIFO) 구조로 가장 나중에 들어간 원소가 가장 먼저 나오게 된다. 

 

 

 

stack의 구조

 

스택의 연산은 Push, Pop 으로 단순하다. Push 연산시 가장 위에 원소를 추가하게 되고, Pop 연산시 가장 위의 원소를 반환한다. 

 

Push 연산

Pop 연산

 

 

C언어 구현

스택을 구현 할 때는 배열로 구현할 수도 있고, 연결리스트(Linked List)를 이용해 구현할 수도 있다. 여기서는 배열을 이용해 간단히 구현해본다. 

 

 

1. 스택의 초기화

#include <stdio.h>
#define STACK_SIZE 10  // 스택의 사이즈
 
int stack[STACK_SIZE];    // 스택
int top = -1;    // 가장 위의 원소를 가리킬 top 변수

스택의 사이즈를 결정할 STACK_SIZE를 할당하고 해당 사이즈만큼의 배열을 선언한다. 또한 가장 위의 원소를 가리킬 top 변수를 -1로 초기화한다. 이는 스택의 인덱스를 0부터 시작하기 위함이다.

 

 

2. isFull() 함수, isEmpty()함수 구현

int isFull(){
    if(top >= STACK_SIZE -1){    // stack의 인덱스 0부터 시작
        printf("Error : Stack is Full!\n");
        return 1;
    }
    return 0;
}
int isEmpty(){
    if(top == -1){
        printf("Error : Stack is empty!\n");
        return 1;
    }
    return 0;
}

스택이 꽉 차있는 경우에 원소를 집어넣으려고 push 연산을 하면 어떻게 될까? 스택이 넘치게 될 것이다. 이를 스택오버플로우(stack overflow) 라고 한다. 반대로 스택이 비어있는 상태에서 pop 연산을 하면 어떻게 될까? 아무것도 없는 상태에서 원소를 반환하려고 하면 오류가 발생할 것이다. 따라서 이를 방지하기 위해 스택의 상태를 체크하는 함수인 isFull() 함수와 isEmpty() 함수가 필요하다.

 

isFull() 함수는 스택이 꽉 차있는지 검사한다. 만약 top 변수가 STACK_SIZE-1 보다 크거나 같다면 스택이 꽉차있는 상태인 것이다. 이는 스택의 인덱스가 0부터 시작하기 때문이다. 예를 들어 STACK_SIZE 를 10으로 설정했는데, 만약 top 변수가 9값을 갖고 있다면, 인덱스 0부터 9까지 총 10개의 원소가 있는 것이므로 스택이 꽉 차 있는 것이다.

 

isEmpty() 함수는 스택이 비어있는지 검사한다. 만약 top 변수가 -1 값을 갖는다면 초기 상태, 원소가 아무것도 없는 상태이므로 비어있는 것이다.

 

3. push() 함수

void push(int data){
    if(!isFull()){
        top++;
        stack[top] = data;
    }
} 

4. pop()함수

int pop(){
    if(!isEmpty()){
        return stack[top--];
    }
}

스택이 비어있는지 검사하고, 그렇지 않다면 가장 윗 원소를 반환한다. 

 

5. printStack()함수

void printStack(){int i;
   for(i=0; i<=top; i++){
        printf("%d ", stack[i]);
    }
    printf("\n");
}

간단하게 스택의 모든 원소를 출력하는 함수이다. 이 때 아래에서부터 위 순서로 원소를 출력하는 것을 유의하자.

 

전체코드

#include <stdio.h>
#define STACK_SIZE 10  // 스택의 사이즈
 
int stack[STACK_SIZE];    // 스택
int top = -1;    // 가장 위의 원소를 가리킬 top 변수
 
int isFull(){
    if(top >= STACK_SIZE -1){    // stack의 인덱스 0부터 시작
        printf("Error : Stack is Full!\n");
        return 1;
    }
    return 0;
}
int isEmpty(){
    if(top == -1){
        printf("Error : Stack is empty!\n");
        return 1;
    }
    return 0;
}
 
void push(int data){
    if(!isFull()){
        top++;
        stack[top] = data;
    }
} 
 
int pop(){
    if(!isEmpty()){
        return stack[top--];
    }
}
 
 
void printStack(){
    int i;
    for(i=0; i<=top; i++){
        printf("%d ", stack[i]);
    }
    printf("\n");
}
 
int main(){
    
    push(5);
    push(4);
    push(3);
    push(2);
    push(1);
    printStack();
    pop();
    printStack();
    
    return 0;
}

 

 

 

 

---