[자료구조] 스택

Jean·2022년 1월 20일

[자료구조 & 알고리즘] Python

목록 보기

8/9

오랜만에 쓰는 글이다. 정말이지...재귀를 접해보지 않았던 나에게 트리 자료구조는 너무나도 끔찍했기 때문에 금방 손을 놔버렸고 어언 2주 정도가 지나서야 정신을 차리고 다시 공부를 시작했던 것 같다.

트리 자료구조에 대한 공부를 가까스로 마친 후에 근 며칠 간 간단하게 스택과 데크, 큐에 대해서 공부했고 글을 다시 쓰며 이 자료구조들에 대해 정리해보고자 한다.

그 전에 지난번에 정리했던 트리에 대해서 간단히 정리하고 넘어가도록 하자.

트리 자료구조의 특징

트리는 최상위 노드인 루트를 기점으로 하위 노드가 뻗어져 나가 나무와 비슷하게 생긴 비선형 자료구조이다.

대개 이진 트리를 사용하며, 같은 자료양을 탐색하더라도 배열에 비해 O(n^2)의 시간복잡도가 나온다.

재귀적인 성질을 이용하는 데에도 자주 사용된다.

이진 트리의 순회 방식에는 전위, 중위, 후위 순회 방식이 있다.

이진 트리의 종류는 정 이진 트리, 완전 이진 트리, 편향 이진 트리, 포화 이진 트리 등이 있다.

📘 사실 많이들 사용했을걸...?

스택이라는 자료구조는 사실 배열이나 연결 리스트로도 쉽게 구현이 가능하고, 사람들이 많이 사용했기에 용어로써 정의하고 이 자료구조는 어떤 형태를 지니고 있는지 정리한 것이라고 한다.

스택 자료구조는 우리가 흔히 접할 수 있는 스마트폰 어플의 게임으로도 있는데
이 게임은 맨 아래층부터 블록을 쌓아올려 최대한 높이 탑을 쌓는데 목적이 있다.

우리가 배우려는 스택도 이와 같다.

다만, 탑을 쌓았다면 내릴 수도 있어야하는 법.
어떻게 해야 탑이 무너지지 않고 다시 아무것도 없던 초기 상태로 돌려놓을 수 있을까??

📘 삽입과 삭제는 뒤에서 이루어진다

탑이 무너지지 않고 처음 상태로 돌려놓을 수 있는 가장 좋은 방법은 가장 윗칸의 블록부터 차례로 제거하는 것이다. 중간도 맨 아래도 아닌 맨 위에서부터 블록을 빼야 탑이 무너지지 않고 아무것도 없던 처음 상태로 쉽게 돌아갈 수 있을 것이다.

스택도 동일하다.
삽입이 가장 뒤에서 이루어지고, 동일하게 삭제도 뒤에서 이루어진다.

따라서 삽입과 삭제가 모두 뒤에서 이루어지기 때문에 제일 먼저 들어온 자료가 가장 나중에 나가게 되는 선입후출(First In Last Out) 형태의 자료구조이다.

보통 이러한 스택 자료구조는 컴퓨터의 프로세스 실행이나 함수의 실행에 자주 활용되며, 뒤에서부터 삽입과 삭제가 이루어지기 때문에 삽입과 삭제는 O(1)의 시간복잡도가 걸리도록 작성되어야 한다.

📌 구현 자료형

자주 사용되는 자료구조인만큼 구현 자료형과 구현 방식 자체도 그리 어렵지 않다. 가장 흔하고 쉽게 사용할 수 있는 자료형은 연결 리스트와 배열이 있으며, 배열은 보통 동적 배열을 사용한다.

해당 정리글에서 정리해놓은 구현체는 Python3 바탕이기 때문에 동적 배열이라 할 수 있는 파이썬의 List 자료형을 사용하였다.

📘 Programming

구현체는 기본적으로 스택을 구현하도록 되어있는 10828번 스택을 통해 풀이하였다.

💻 init(생성자)

import sys

class stack:
    def __init__(self) -> None:
        self.stack = []
        self.cnt = 0

클래스 이름은 stack으로 정해주었고, 생성자에서 객체변수 stack 리스트와 cnt를 생성하여 자료형 선언을 해주었다.

여기서 사용되는 stack은 stack 자료구조를 뜻하고, cnt는 자료가 삽입되고 삭제됨에 따라 증감되며 자료의 갯수나 비어있는 등의 확인을 위해 선언해주었다.

💻 push

def push(self, num):
    self.stack.append(num)
    self.cnt += 1

push 메서드는 append 함수를 통해 stack의 가장 뒤에 값을 추가하도록 하였고 값이 추가될 때마다 cnt 변수의 값을 증가시켜주었다.

💻 pop

def pop(self):
    if self.cnt == 0:
        print(-1)
    else:
        print(self.stack.pop())
        self.cnt -= 1

pop 메서드는 pop 함수를 통해 stack의 가장 뒤에 값을 삭제하고 출력하도록 하였고 값이 삭제될 때마다 cnt 변수의 값을 감소시켜주었다.

💻 size

def size(self):
    print(self.cnt)

size 메서드는 스택에 들어가있는 전체 자료의 갯수를 세어 출력하도록 하였다. 이때 값의 증감에 따라 자료의 갯수를 cnt 변수에 지정해주었기에 cnt의 값을 직접적으로 출력해주었다.

💻 top

def top(self):
    if self.cnt == 0:
    	print(-1)
    else:
    	print(self.stack[-1])

top 메서드는 스택의 가장 위(리스트의 맨 뒤)에 해당하는 값을 출력해주는 것으로 이때는 pop과 다르게 값만 출력해줄뿐 삭제는 이루어지지 않는다.

💻 empty

def empty(self):
    if self.cnt == 0:
    	print(1)
    else:
    	print(0)

empty 메서드는 stack 내 값이 비어있는 지 여부를 판단하는 메서드로 cnt 변수를 통해 값의 존재 여부를 확인하도록 하였다.

💻 main

st = stack()
for _ in range(int(input())):
    test_list = sys.stdin.readline().split()

    if test_list[0] == 'push':
        st.push(test_list[1])

    if test_list[0] == 'pop':
        st.pop()

    if test_list[0] == 'size':
        st.size()
    
    if test_list[0] == 'top':
        st.top()

    if test_list[0] == 'empty':
        st.empty()

st라는 이름의 객체를 생성해주었고, 가장 먼저 처음 명령어를 입력할 횟수를 입력받아 for문의 반복 횟수를 정해주었다.

다음으로 명령어의 형태가 push 1 / pop / size / top / empty의 형태로 이루어져 있었기 때문에 입력받은 문자열을 공백으로 쪼개 리스트로 반환해주는 split 함수를 사용해 push 메서드에 들어갈 명령어와 값을 구분해주었고 if문 조건을 통해 알맞는 명령어가 입력되면 해당 메서드를 실행하도록 작성하였다.