출처: Unsplash

스택 (Stack)

📌 목차

1. 정의
2. 특징
3. 구현
   a. 코드
   b. 테스트
   c. 결과
4. 문제
5. 답안

---

📌 정의

사전

스택을 영어사전에서 찾아 보면 '무더기', '더미'라는 의미의 단어다.

위아래의 돌탑을 떠올리면 쉽게 이해할 수 있다.

자료구조

Stack is an ordered list in which insertions and deletions are made at one end called the top.
스택은 상단이라 불리는 한쪽 끝에서 삽입과 삭제가 이루어지는 선형적 자료구조이다.

쉽게 말하여 스택은 밑에서 점차 위로 쌓아올리는 선형적 자료구조이다.

출처: Unsplash

📌 특징

후입선출 (LIFO, Last In First Out)

• 앞의 정의에서 "한쪽 끝에서 삽입과 삭제가 이루어지는" 특징을 후입선출(LIFO)이라 한다.
• 데이터를 추가하는 것을 Push, 자료를 꺼내는 것을 Pop이라 한다.

[!] 다크모드를 해제해야 아래의 이미지가 보입니다.

출처: Wikipedia

📌 구현

Python에서 기본적으로 제공하는 자료형인 list를 활용하면 쉽게 구현할 수 있다.

코드

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

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

    def pop(self):
        self.items.pop()

    def size(self):
        return len(self.items)

    def top(self):
        if self.empty():
            return "stack is empty."
        return self.items[-1]

    def empty(self):
        return not self.items

    def __str__(self):
        return f"{self.items}"

테스트

if __name__ == "__main__":
    stack = Stack()
    print(f"Make a stack : {stack}")
    print(f"Is stack empty? {stack.empty()}")
    print()

    stack.push(2)
    print(f"Push 2 : {stack}")
    stack.push(3)
    print(f"Push 3 : {stack}")
    stack.push(9)
    print(f"Push 9 : {stack}")
    print(f"Is stack empty? {stack.empty()}")
    print()

    stack.pop()
    print(f"pop : {stack}")
    stack.pop()
    print(f"pop : {stack}")
    stack.pop()
    print(f"pop : {stack}")
    print(f"Is stack empty? {stack.empty()}")
    print()

    stack.push(1)
    print(f"Push 1 : {stack}")
    print(f"size of stack : {stack.size()}")
    stack.push(7)
    print(f"Push 7 : {stack}")
    print(f"Is stack empty? {stack.empty()}")
    print(f"size of stack : {stack.size()}")

    print()
    print(stack)
    print(f"top of stack : {stack.top()}")

결과

Make a stack : []
Is stack empty? True

Push 2 : [2]
Push 3 : [2, 3]
Push 9 : [2, 3, 9]
Is stack empty? False

pop : [2, 3]
pop : [2]
pop : []
Is stack empty? True

Push 1 : [1]
size of stack : 1
Push 7 : [1, 7]
Is stack empty? False
size of stack : 2

[1, 7]
top of stack : 7

📌 문제

[백준] 10828번: 스택

백준에서 실제 stack을 구현해 보는 문제가 있다.

클래스를 구현하지 않고 if 문으로 문제를 풀 수 있겠지만,
위의 클래스를 활용해서 풀어보자.

📌 답안

import sys

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

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

    def pop(self):
        if len(self.items) == 0:
            return -1
        else:
            return self.items.pop()

    def size(self):
        return len(self.items)

    def empty(self):
        if len(self.items) == 0:
            return 1
        else:
            return 0

    def top(self):
        if len(self.items) == 0:
            return -1
        else:
            return self.items[-1]

    def __str__(self):
        return str(self.items)


# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

N = int(input())
stack = Stack()

for _ in range(N):
    commands = input().split()
    command = commands[0]

    if command == "push":
        stack.push(commands[1])
        # print(stack.push(commands[1])) # None이 계속 뜬다

    elif command == "pop":
        print(stack.pop())

    elif command == "size":
        print(stack.size())

    elif command == "empty":
        print(stack.empty())

    elif command == "top":
        print(stack.top())