[자료구조] 스택 - Stack (C, Python)

 

우측 상단에서 다크 모드를 끌 수 있습니다!

 

🖥️ 들어가며

스택(Stack)은 우리 주변에서도 흔히 볼 수 있는 자료구조입니다. 문서 수정 시 되돌리기나, Ctrl-C Ctrl-V라는 좋은 예도 있고, 가장 대표적으로 사용되는 프링글스 과자 예시도 직관적으로 다가옵니다. 즉, 스택은 말 그대로 ‘쌓아놓은 어떤 더미’를 뜻합니다.

스택

스택의 가장 큰 특징은 후입선출(LIFO : Last-In First-Out)입니다. 아래 그림을 보면 이해하기 쉽습니다.

요는 가장 최근에 들어온 데이터가 가장 먼저 나간다 입니다.

스택의 구조

• Push : 데이터 삽입 연산
• Pop : 데이터 삭제 연산
• 요소(데이터) : 삽입된 데이터
• 스택 하단 : 가장 먼저 삽입된 데이터가 있는 곳, 최하단
• 스택 상단 : 스택의 입출력이 이루어지는 곳

스택에서 구현되어야 할 연산

• init() : 스택 초기화
• isEmpty() : 스택이 비어있는지 검사
• isFull() : 스택이 가득 차있는지 검사
• push() : 스택 상단(top)에 데이터 삽입
• pop() : 스택 상단(top)에서 데이터 삭제, 반환

스택 구현 방법

스택은 두 가지 방식으로 구현할 수 있습니다.

• 배열(순차 리스트)로 구현
  • 구현하기 편하고 쉽게 쓸 수 있는 장점이 있지만, 순차 리스트의 단점을 그대로 가집니다.
• 연결 리스트로 구현
  • 메모리 관리에 용이합니다.

스택 구현

이제 하나하나 구현해 보겠습니다.

isEmpty()

배열 구조

초기 top 값은 보통 -1로 설정합니다. 배열 인덱스가 0부터 시작하기 때문에, top 이 -1이라면 스택이 빈 것으로 간주합니다.

C

int isEmpty() {
    if (top == -1)
        return 1;
    else
        return 0;
}

Python

# pop() 안에 간단하게 구현

if not self.items:
    raise IndexError("스택 언더플로우")

연결 리스트 구조

스택이 비어있으므로 Head 포인터가 Null을 가리키게 됩니다.

C

// pop 안에 간단하게 구현

if (top == NULL) {
    printf("stack is empty!");
    exit(1);
}

isFull()

배열 구조

최상단의 top 이 배열의 크기와 같거나 더 커지면 오버플로우가 일어나므로 SIZE - 1 과 top이 같으면 스택이 다 찬 것으로 간주합니다.

C

int isFull() {
    if (top >= SIZE - 1)
        return 1;
    else
        return 0;
}

Python

파이썬에서는 리스트의 크기를 딱히 정하지 않아도 되서 필요가 없습니다.

연결 리스트 구조

간단합니다. 메모리가 허용하는 만큼 만들 수 있으므로, 새로 만든 스택이 만들 수 없어 NULL 이 된다면 스택이 다 찬 것입니다.

C

// push 안에 생성
if (temp == NULL) {
    printf("stack is full!");
    exit(1);
}

push()

배열 구조

top 을 하나 늘려주고 데이터를 삽입합니다.

C

void push(int x) {
    if (top >= SIZE - 1) {
        printf("스택 오버플로우\n");
        exit(EXIT_FAILURE);
    } else {
        stack[++top] = x;
    }
}

Python

def push(self, item):
    self.items.append(item)

연결 리스트 구조

1. 스택에 추가할 노드의 next 를 현재 head (top) 으로 설정합니다.
2. 새로운 노드를 head 포인터 (top) 으로 설정합니다.

C

void push(int data) {
    stack *temp = (stack *)malloc(sizeof(stack));

    if (temp == NULL) {
        printf("stack is full!");
        exit(1);
    }

    temp->data = data;
    temp->next = top;
    top = temp;
}

pop()

배열 구조

top 에 있던 값을 반환한 후, top 을 하나 줄입니다.

당연히 배열 구조에서는 값이 남아있지만 스택의 현 크기는 top 이 결정하므로 괜찮습니다.

C

int pop() {
    if (isEmpty()) {
        printf("스택 언더플로우\n");
        exit(EXIT_FAILURE);
    }

    return stack[top--];
}

Python

def pop(self):
    if not self.items:
        raise IndexError("스택 언더플로우")
    return self.items.pop()

연결 리스트 구조

1. 현 Head 포인터 (top) 을 Head->next 주소의 노드로 변경합니다.
2. 삭제할 노드를 free 합니다.

C

int pop() {
    if (top == NULL) {
        printf("stack is empty!");
        exit(1);
    }

    stack *temp = top;

    int val = temp->data;
    top = temp->next;

    free(temp);

    return val;
}

C 코드 전문 (배열, 순차 리스트)

#include <stdio.h>
#include <stdlib.h>

#define SIZE 100

int stack[SIZE], top;

int isEmpty() {
    if (top == -1)
        return 1;
    else
        return 0;
}

int isFull() {
    if (top >= SIZE - 1)
        return 1;
    else
        return 0;
}

void push(int x) {
    if (top >= SIZE - 1) {
        printf("스택 오버플로우\n");
        exit(EXIT_FAILURE);
    } else {
        stack[++top] = x;
    }
}

int pop() {
    if (isEmpty()) {
        printf("스택 언더플로우\n");
        exit(EXIT_FAILURE);
    }

    return stack[top--];
}

void display() {
    if (top == -1) {
        printf("스택이 비어 있습니다.\n");
        return;
    }

    printf("현재 스택 상태:\n");
    for (int i = top; i >= 0; --i) {
        printf("%d\n", stack[i]);
    }
    printf("\n");
}

int main() {
    top = -1;

    push(1);
    push(2);
    push(3);
    push(4);
    push(5);

    display();

    pop();
    pop();
    display();

    return 0;
}

Python 코드 전문 (배열, 순차 리스트)

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.items:
            raise IndexError("스택 언더플로우")
        return self.items.pop()

    def __iter__(self):
        return reversed(self.items)

    def __str__(self):
        if not self.items:
            return "스택이 비어 있습니다."
        stack_representation = "현재 스택 상태:\n" + "\n".join(
            str(item) for item in self
        )
        return stack_representation + "\n"

if __name__ == "__main__":
    stack = Stack()

    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    stack.push(5)

    print(stack)  # __str__ 메서드를 통한 출력

    stack.pop()
    stack.pop()

    print(stack)  # 스택 상태 재출력

C 코드 전문 (연결 리스트)

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node *next;
} stack;

stack *top = NULL;

void push(int data) {
    stack *temp = (stack *)malloc(sizeof(stack));

    if (temp == NULL) {
        printf("stack is full!");
        exit(1);
    }

    temp->data = data;
    temp->next = top;
    top = temp;
}

// 여기에 코드를 완성하시오.
int pop() {
    if (top == NULL) {
        printf("stack is empty!");
        exit(1);
    }

    stack *temp = top;

    int val = temp->data;
    top = temp->next;

    free(temp);

    return val;
}

// 여기에 코드를 완성하시오.
void print_s() {
    stack *temp = top;

    while (temp != NULL) {
        printf("%d\n", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    push(1);
    push(2);
    push(3);
    push(4);
    push(5);

    print_s();
    pop();
    pop();
    print_s();
}