data structure(자료 구조) - Array(배열) 기반의 Stack(스택) 구현::FBTT

지난 글에서는 스택의 개념과 정의 그리고 그 쓰임새에 대해서 알아보았습니다.

https://readytoearndon.tistory.com/36

data structure(자료 구조) - stack(스택)의 개념과 사용

이번에는 배열을 기반으로 스택을 구현해보고자 합니다.

 

배열을 기반으로 한다는 것은 다른 자료구조를 기반으로도 스택을 구현할 수 있다는 것이겠죠?

 

스택은 연결 리스트로도 구현할 수 있지만 우선 배열로 구현해보도록 하겠습니다.

 

저번 글에서 스택의 연산에 대해 간단히 설명했었습니다.

 

그 연산들을 구현해보도록 하겠습니다.

 

스택을 나타내는 구조체

배열을 기반으로 구현하는 스택이기 때문에 스택을 나타내는 구조체에는 배열과 한 쪽 끝을 나타내는 top이라는 변수가 있어야 합니다.

#include <stdio.h>
#include <stdbool.h>
#define len 100
 
typedef struct Stack {
    int stack_array[len];
    int top;
}stack;

스택의 초기화

스택을 선언하고나면 top에는 쓰레기 값이 들어가 있어 다른 기능들이 제대로 작동하지 않을 것입니다.

 

그렇기 때문에 스택을 만들고 난 후 항상 초기화를 먼저 실행해주어야 합니다.

 

초기화라고 해봤자 top을 -1로 만들어 주는 것 뿐입니다.

#include <stdio.h>
#include <stdbool.h>
#define len 100
 
typedef struct Stack {
    int stack_array[len];
    int top;
}stack;
 
void stack_init(stack* new_stack)
{
    new_stack->top = -1;
}

스택의 상태를 보는 함수

스택이 비어있는지 아니면 가득 차있는지를 확인하기 위해 실행시키는 함수으로 push와 pop을 실행하기전 스택의 상태를 확인하는 기능을 합니다.

#include <stdio.h>
#include <stdbool.h>
#define len 100
 
typedef struct Stack {
    int stack_array[len];
    int top;
}stack;
 
void stack_init(stack* new_stack)
{
    new_stack->top = -1;
}
 
int is_empty(stack* new_stack)
{
    if (new_stack->top == -1)
        return true;
    else
        return false;
}
 
int is_full(stack* new_stack)
{
    if (new_stack->top == len)
        return true;
    else
        return false;
}

16line의 is_empty는 스택이 비어있으면 true를 아니면 false를 반환하는 함수이고 24line의 is_full은 스택이 가득 차 있으면 true를 아니면 false를 반환하는 함수입니다.

 

is_full함수에서 stack_array로 판단하지 않고 top으로 판단하는 이유는 stack_array는 스택을 만들어 초기화해도 쓰레기 값으로 가득 차있기 때문에 is_full함수를 호출했을 때 항상 true를 반환하기 때문입니다.

 

스택에 자료 추가(push)

이제 본격적으로 자료를 다루기 시작합니다.

 

스택에서 자료의 추가는 top이 가리키는 곳에서 이루어집니다.

 

처음 스택을 초기화할 때 top을 -1로 초기화해주었으니 데이터를 넣기 전에 먼저 top을 1증가시켜주고 데이터를 넣으면됩니다.

#include <stdio.h>
#include <stdbool.h>
#define len 100
 
typedef struct Stack {
    int stack_array[len];
    int top;
}stack;
 
void stack_init(stack* new_stack)
{
    new_stack->top = -1;
}
 
int is_empty(stack* new_stack)
{
    if (new_stack->top == -1)
        return true;
    else
        return false;
}
 
int is_full(stack* new_stack)
{
    if (new_stack->top == len)
        return true;
    else
        return false;
}
 
void stack_push(int data, stack* new_stack)
{
    if (is_full(&new_stack))
    {
        printf("pushing in full stack");
        exit(1);
    }
    new_stack->top++;
    new_stack->stack_array[new_stack->top] = data;
}

32line의 push함수를 보면 설명했던 코드 외에 if문이 하나 있습니다.

 

이 if문은 스택에 데이터를 추가할 공간이 남아있는지 확인하는 코드입니다. 그래서 공간이 없는데 데이터를 추가하려 하면 프로그램이 종료됩니다.

 

스택에 자료 삭제(pop)

스택에서 자료를 삭제할 때는 삭제하고 나서 삭제한 자료를 반환해줍니다.

 

단순히 삭제만 한다면 그냥 top을 1감소시켜 주는것만으로 삭제가 됩니다.

#include <stdio.h>
#include <stdbool.h>
#define len 100
 
typedef struct Stack {
    int stack_array[len];
    int top;
}stack;
 
void stack_init(stack* new_stack)
{
    new_stack->top = -1;
}
 
int is_empty(stack* new_stack)
{
    if (new_stack->top == -1)
        return true;
    else
        return false;
}
 
int is_full(stack* new_stack)
{
    if (new_stack->top == len)
        return true;
    else
        return false;
}
 
void stack_push(int data, stack* new_stack)
{
    if (is_full(&new_stack))
    {
        printf("pushing in full stack");
        exit(1);
    }
    new_stack->top++;
    new_stack->stack_array[new_stack->top] = data;
}
 
int stack_pop(stack* new_stack)
{
    if (is_empty(&new_stack))
    {
        printf("poping from empty stack");
        exit(1);
    }
    int remove_idx = new_stack->top;
    new_stack->top--;
 
    return new_stack->stack_array[remove_idx];
}

하지만 반환을 해야하기 때문에 우선 삭제할 데이터(top이 가리키고 있는 데이터)의 index를 저장하는 변수를 만들어줍니다.

 

그리고 나서 top을 감소시켜주고 저장해놓았던 index의 데이터를 반환해줍니다.

 

pop함수의 if문도 마찬가지로 비어있는 스택에서 삭제를 하려고 하면 프로그램이 종료됩니다.

 

top이 가리키는 자료 반환(peek)

peek함수를 구현하는 것은 굉장히 쉽습니다.

 

단순히 top이 가리키는 데이터를 반환해주면 되니까요.

#include <stdio.h>
#include <stdbool.h>
#define len 100
 
typedef struct Stack {
    int stack_array[len];
    int top;
}stack;
 
void stack_init(stack* new_stack)
{
    new_stack->top = -1;
}
 
int is_empty(stack* new_stack)
{
    if (new_stack->top == -1)
        return true;
    else
        return false;
}
 
int is_full(stack* new_stack)
{
    if (new_stack->top == len)
        return true;
    else
        return false;
}
 
void stack_push(int data, stack* new_stack)
{
    if (is_full(&new_stack))
    {
        printf("pushing in full stack");
        exit(1);
    }
    new_stack->top++;
    new_stack->stack_array[new_stack->top] = data;
}
 
int stack_pop(stack* new_stack)
{
    if (is_empty(&new_stack))
    {
        printf("poping from empty stack");
        exit(1);
    }
    int remove_idx = new_stack->top;
    new_stack->top--;
 
    return new_stack->stack_array[remove_idx];
}
 
int stack_peek(stack* new_stack)
{
    if (is_empty(&new_stack))
    {
        printf("this stack is empty");
        exit(1);
    }
 
    return new_stack->stack_array[new_stack->top];
}

55line의 peek함수의 if문 역시 스택이 비어있는지 확인하고 스택에 데이터가 없는데 top에 접근하려고 하면 종료됩니다.

 

그러면 이제 구현을 끝냈으니 제대로 작동하는지 봅시다.

 

#include <stdio.h>
#include <stdbool.h>
#define len 100
 
typedef struct Stack {
    int stack_array[len];
    int top;
}stack;
 
void stack_init(stack* new_stack)
{
    new_stack->top = -1;
}
 
int is_empty(stack* new_stack)
{
    if (new_stack->top == -1)
        return true;
    else
        return false;
}
 
int is_full(stack* new_stack)
{
    if (new_stack->top == len)
        return true;
    else
        return false;
}
 
void stack_push(int data, stack* new_stack)
{
    if (is_full(&new_stack))
    {
        printf("pushing in full stack");
        exit(1);
    }
    new_stack->top++;
    new_stack->stack_array[new_stack->top] = data;
}
 
int stack_pop(stack* new_stack)
{
    if (is_empty(&new_stack))
    {
        printf("poping from empty stack");
        exit(1);
    }
    int remove_idx = new_stack->top;
    new_stack->top--;
 
    return new_stack->stack_array[remove_idx];
}
 
int stack_peek(stack* new_stack)
{
    if (is_empty(&new_stack))
    {
        printf("this stack is empty");
        exit(1);
    }
 
    return new_stack->stack_array[new_stack->top];
}
 
int main(void)
{
    stack nstack;
 
    stack_init(&nstack);
    stack_push(1, &nstack);
    stack_push(2, &nstack);
    stack_push(3, &nstack);
    stack_push(4, &nstack);
    stack_push(5, &nstack);
    printf("%d\n", stack_peek(&nstack));
    while (!is_empty(&nstack))
    {
        printf("%d ", stack_pop(&nstack));
    }
}

실행 결과

main의 함수들이 모두 정상적으로 작동하는 것을 볼 수 있습니다.

 

스택은 앞서 구현해봤던 연결 리스트에 비해 구현이 간단했습니다. top에서만 연산이 이루어지다보니 복잡할 것이 없었거든요.

 

스택의 연산들의 시간 복잡도 또한 O(1)로 빠릅니다.

 

 

 

되도록이면 근시일내에 연결 리스트 기반의 스택 구현을 해보도록하겠습니다.

 

감사합니다.