Reo’s Archive
Reo’s Archive/
📚
[자료구조] 스택 - Stack (C, Python)
카테고리
[자료구조] 스택 - Stack (C, Python)
📚

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

카테고리
📋 Data Structure
작성자
박용성박용성
작성일
2024년 06월 02일
태그
C
Python
Slug
ds-stack
floatFirstTOC: right
🖥️ 들어가며스택스택의 구조스택에서 구현되어야 할 연산스택 구현 방법스택 구현isEmpty()배열 구조CPython연결 리스트 구조CisFull() 배열 구조CPython연결 리스트 구조Cpush() 배열 구조CPython연결 리스트 구조Cpop()배열 구조CPython연결 리스트 구조CC 코드 전문 (배열, 순차 리스트)Python 코드 전문 (배열, 순차 리스트)C 코드 전문 (연결 리스트)

🖥️ 들어가며

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

스택

스택의 가장 큰 특징은 후입선출(LIFO : Last-In First-Out)입니다. 아래 그림을 보면 이해하기 쉽습니다.
요는 가장 최근에 들어온 데이터가 가장 먼저 나간다 입니다.
notion image
 

스택의 구조

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

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

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

스택 구현 방법

스택은 두 가지 방식으로 구현할 수 있습니다.
notion image
  1. 배열(순차 리스트)로 구현
      2. 구현하기 편하고 쉽게 쓸 수 있는 장점이 있지만, 순차 리스트의 단점을 그대로 가집니다.
  1. 연결 리스트로 구현
      2. 메모리 관리에 용이합니다.
 

스택 구현

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

isEmpty()

배열 구조

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

C

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

Python

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

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

연결 리스트 구조

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

C

// pop 안에 간단하게 구현

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

isFull()

배열 구조

notion image
최상단의 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()

배열 구조

notion image
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)
 

연결 리스트 구조

notion image
  1. 스택에 추가할 노드의 next 를 현재 head (top) 으로 설정합니다.
  1. 새로운 노드를 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()

배열 구조

notion image
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()
 
 

연결 리스트 구조

notion image
  1. 현 Head 포인터 (top) 을 Head->next 주소의 노드로 변경합니다.
  1. 삭제할 노드를 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();
}

댓글

guest