[자료구조] 스택 / stack / 스택구현 / push / pop / empty / size / top

https://www.acmicpc.net/problem/10828을 풀면서 복기했던 스택에 대해 정리한다.

1. 스택(stack)이란?

컴퓨터 과학에서 요소들의 집합으로 기능하는 abstract data type. (출처: 위키백과)
쉽게 말해서 배열처럼 요소들의 집합인 자료구조이다.
스택의 강력한 특징은 LIFO(Last In - First Out)이다.
조금 더 직관적인 이해를 위해 그림을 그려봤다.

위 그림과 같이 먼저 들어간 a보다 c가 먼저 나오는 구조다.
그리고 데이터는 한쪽에서만 입출력이 가능하다.
처음 스택을 접하면 받아들이기가 힘들 수도 있다. 일반적인 상식과는 어긋나기 때문이다🤣
(먼저 들어간 사람이 먼저 나오는 게 상식적이니까..?)
이렇게 생각하다 보니까 갑자기 스택의 예시로는 뭐가 있는지 궁금해졌다.

2. 스택(stack)의 예시

- 책더미
책을 바닥에 쌓아두면 젤 위에 걸 먼저 꺼내야만 밑에 것들을 꺼낼 수 있다.
=> 책이 너무 쌓이다보면 가장 아래 있는 책을 꺼내기가 힘들어지는데, 이게 스택의 단점이다.

- 동전 쌓기

3. 스택(stack)의 대표적인 명령들

- push : 스택에 원소를 삽입한다. 차곡차곡 쌓이는 구조로 삽입된다.
- pop : 스택의 원소를 제거한다. 맨 뒤에(맨 마지막) 있는 원소 즉, top이 가리키는 원소부터 제거된다.
- top : 스택 포인터로 항상 맨 위를 가리키며, 스택의 크기와 동일하다. 원소가 push될 때마다 1씩 증가한다.
- empty : 스택이 비어있는지 아닌지 확인한다.

4. 스택(stack) 구현하기

파이썬의 List를 활용하여, 스택을 구현했다.

import sys
stack = []
num = int(sys.stdin.readline())

for _ in range(num):
    words = sys.stdin.readline().split() 
    command = words[0] # 명령어

    if command == 'push':
        stack.append(words[1])

    elif command == 'pop':
        if len(stack) == 0:
            print(-1)
        else:
            print(stack.pop())

    elif command == 'size':
        print(len(stack))

    elif command == 'empty':
        if len(stack) == 0:
            print(1)
        else:
            print(0)

    elif command == 'top':
        if len(stack) == 0:
            print(-1)
        else:
            print(stack[-1])

먼저 명령어의 개수를 입력 받고 그 개수만큼 반복문을 돌려서 명령을 수행한다.
명령어는 push 1 / pop / empty 와 같은 문자열로 입력된다.

다만 push의 경우 어떤 정수를 stack에 push할 건지 같이 입력해주어야 하기 때문에 공백을 기준으로 입력을 받는다.
공백을 기준으로 첫번째로 입력된 문자(인덱스 0)는 명령어에 속하고, 두번째로 입력된 문자(인덱스 1)는 stack에 삽입할 원소이다.