Stack

파이썬의 기본 자료구조에 대해 알아보고자 한다.
오늘 포스팅에서 다룰 내용은 스택과 큐의 정말 기본적인 기초 내용과 백준 기본 자료구조 문제를 통해서 스택과 큐를 구현한 예제를 살펴볼 것이다 !

💡 Stack

첫 번째로 스택에 대해서 알아보자.
스택이란 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO)방식이다.

스택에서 데이터를 다루는 작업에 대한 몇 가지 단어에 대해 알아보자.

• push 데이터를 넣는 작업
• pop 데이터를 꺼내는 작업
• top 푸시하고 팝하는 맨 윗부분
• bottom 맨 아랫부분
  
  

스택에서 데이터는 먼저 넣는 순서대로 아래로 깔린다고 생각하면 간단하다. 이렇게 깔린 데이터는 맨 마지막에 꺼낼 수 있고 맨 마지막에 넣은 데이터가 제일 top에 위치하므로 제일 먼저 꺼낼 수 있다.

위의 그림처럼 이런식으로 데이터가 입출력된다고 이해하면 된다.

• capacity 스택의 최대 크기를 나타내는 int형 정수이다. 이 값은 스택의 원소 수인 len(stk)와 일치한다.
• ptr 스택 포인터로 스택에 쌓여있는 데이터의 개수를 나타내는 정숫값을 스택 포인터라고 한다. 비어있으면 0, 가득 차 있으면 capacity의 값과 일치한다.

두 용어의 차이를 아래 그림으로 이해하면 쉽다 !

다음으로는 스택에서 사용하는 클래스와 함수들에 대해서 알아보자.

예외 처리 클래스 Empty / Full

• Empty 클래스 : pop() 함수 또는 peek() 함수를 호출할 때 스택이 비어 있으면 내보내는 예외 처리이다.
• Full 클래스 : push() 함수를 호출할 때 스택이 가득 차 있으면 내보내는 예외 처리이다.

함수

• __init__() 스택 배열을 생성하는 등의 준비 작업을 수행. 매개변수인 capacity로 전달받은 값을 스택의 크기를 나타내는 필드인 capacity로 복사해 해당 크기의 스택을 생성.
• __len__() 스택에 쌓여 있는 데이터 개수를 반환한다. 스택 포인터 ptr값을 그대로 반환한다.

  예를 들어 스택 s의 원소 수는 해당 메서드를 통해서도 알아볼 수 있지만 추가로 len(s)로도 알아볼 수 있다!

• is_empty() 스택이 비어있는 지를 판단하는 함수. 비어있으면 True, 그렇지 않으면 False를 반환한다.
• is_full() 스택이 가득 차 있는지를 판단하는 함수. 가득 차 있으면 True, 그렇지 않으면 False를 반환한다.
• push() 스택에 데이터를 추가하는 함수이다. 스택이 가득 차서 더 이상 푸시할 수 없는 경우에는 FixedStack.Full을 통해 예외 처리를 내보낸다. 그렇지 않으면 데이터를 저장하고 스택 포인터를 1 증가 시킨다.
• pop() 스택의 top에 위치한 데이터를 꺼내서 그 값을 반환한다. 스택이 비어 팝할 수 없다면 FixedStack.Empty를 통해 예외 처리를 내보낸다. 그렇지 않으면 값을 내보내고 스택 포인터를 1 감소시킨다.
• peek() 스택의 top에 위치한 데이터를 들여다본다. pop과 같이 top의 위치한 데이터의 값을 반환하지만 입출력 과정이 아니므로 스택 포인터에는 변화가 없다. 이 경우에도 스택이 비어있다면 FixedStack.Empty를 통해 예외 처리를 내보낸다.
• clear() 스택에 쌓여 있는 모든 데이터를 삭제하여 빈 스택을 만든다. 스택 포인터의 값은 0이 된다.
• find() 스택 내에 value와 값이 같은 데이터가 포함되어 있는지 확인하고 있다면 어디에 있는지를 검색한다. 즉, 값이 같은 데이터가 존재한다면 해당 데이터가 있는 인덱스를 반환하고 실패하면 -1을 반환한다.
• count() 스택에 쌓여 있는 데이터(value)의 개수를 구해 반환한다.
• __contains__() 스택에 데이터가 있는지 판단한다. 있으면 True, 아니면 False를 반환한다.

  이와 같은 과정은 해당 메서드 뿐만이 아니라 멤버십 판단 연산자인 in을 사용해 x in s로 수행할 수 있다!

• dump() 스택에 쌓여 있는 ptr개의 모든 데이터를 바닥부터 꼭대기까지 순서대로 출력한다. 스택이 비어있다면 '스택이 비어 있습니다.'를 출력한다..

스택을 구현해보기 위해서 백준 10828번 문제를 풀어보았다.

📌 문제
- 정수를 저장하는 스택을 구현한다, 입력으로 주어지는 명령을 처리하는 프로그램 작성한다.

[ 명령어 종류 ]
- push x : 정수 x를 스택에 넣는 연산 (출력되는 결과 없음)
- pop : 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력. 만약 스택이 비어있다면 -1을 출력한다.
- size : 스택에 들어있는 정수의 개수를 출력한다.
- empty : 스택이 비어있으면 1, 아니면 0을 출력한다.
- top : 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없으면 -1을 출력

문제의 내용은 위와 같고 우선 코드를 먼저 살펴보자

import sys

input = sys.stdin.readline # 얘로 시간 초과 문제 해결

N = int(input())
stack = [] # 빈 스택 선언

for i in range(N):
    command = input().split() # push 에서 값을 받아서 필요
    if command[0] == "push":
        stack.append(command[1])
    elif command[0] == "pop":
        # 스택이 비어있으면 -1
        if len(stack) == 0:
            print(-1)
        else:
            print(stack.pop())
    elif command[0] == "size":
        print(len(stack))
    elif command[0] == "empty":
        # 스택이 비어있으면 1, 아니면 0
        if len(stack) == 0:
            print(1)
        else:
            print(0)
    elif command[0] == "top":
        # 들어있는 정수가 없으면 -1
        if len(stack) == 0:
            print(-1)
        else:
            print(stack[-1])

처음 스택을 구현할 때에는 스택 자체를 클래스로 생성하는 방식으로 하고 해당 클래스 안에 함수를 선언하는 방식으로 했다.
하지만 본 문제는 여러가지의 스택을 다루는 것도 아니고 하나의 스택만 다루기 때문에 굳이 클래스까지 생성하지 않고 명령어 별로 분기하여 바로 함수를 작성해주었다.

위의 문제에서 활용한 방법 외의 스택 클래스를 생성하는 방법으로도 코드를 작성해보자.
위에서 정리한 스택에서 사용되는 예외 처리 클래스와 함수들을 모두 포함한 클래스를 생성해보았다.

from typing import Any

class FixedStack:
    # 고정 길이의 스택 클래스
    class Empty(Exception): # 스택이 비어있을 때 예외 처리 클래스
        pass

    class Full(Exception): # 스택이 가득 차 있을 때 예외 처리 클래스
        pass

    def __init__(self, capacity: int = 256) -> None:
        # capacity가 256인, 모든 원소가 None인 스택 생성
        # 스택이 비어있으므로 ptr은 0
        self.stk = [None] * capacity
        self.capacity = capacity
        self.ptr = 0

    def __len__(self) -> int:
        # 스택에 쌓여있는 데이터의 개수를 반환
        return self.ptr
    
    def is_empty(self) -> bool:
        # 스택이 비어 있는 지를 판단
        # 스택 포인터가 0보다 작거나 같으면 스택이 비어 있는 것으로 true반환, 아니면 false
        return self.ptr <= 0 
    
    def is_full(self) -> bool:
        # 스택이 가득 차 있는 지를 판단
        # 스택 포인터가 capacity보다 크거나 같으면 가득 차 있는 것으로 true, 아니면 false
        return self.ptr >= self.capacity
    
    def push(self, value: Any) -> None:
        # 스택이 가득 차 있으면 예외 처리 발생
        if self.is_full():
            raise FixedStack.Full
        self.stk[self.ptr] = value # value값을 넣어주고
        self.ptr += 1 # 스택 포인터 1 증가

    def pop(self) -> Any:
        # 스택이 비어 있으면 예외 처리 발생
        if self.is_empty():
            raise FixedStack.Empty
        self.ptr -= 1 # 스택 포인터 1 감소
        return self.stk[self.ptr] # 팝한 데이터의 값 반환

    def peek(self) -> Any:
        # 스택이 비어 있으면 예외 처리 발생
        if self.is_empty():
            raise FixedStack.Empty
        return self.stk[self.ptr-1]

    def clear(self) -> None:
        # 스택을 모두 비우는 것으로 스택 포인터를 0으로 
        self.ptr = 0

    def find(self, value:Any) -> Any:
        for i in range(self.ptr-1, -1, -1): # 스택의 맨 위에서부터 한 칸 씩 내려오면서 탐색
            if self.stk[i] == value:
                return i # 인덱스를 반환
        return -1 # 못 찾으면 -1 반환

    def count(self, value:Any) -> int:
        # 스택에 있는 value의 개수 반환 (int)
        count = 0
        for i in range(self.ptr):
            if self.stk[i] == value:
                count += 1
        return count

    def __contains__(self, value:Any) -> bool:
        # 스택에 value가 있는지 판단 (bool)
        # value의 count개수가 0보다 크면 1개 이상 존재하는 것이므로 true, 아니면 false
        return self.count(value) > 0
    
    def dump(self) -> None:
        # 모든 데이터를 바닥에서 꼭대기 순으로 출력
        if self.is_empty():
            print("스택이 비어 있습니다")
        else:
            print(self.stk[:self.ptr])

위에서 알아본 스택과 관련한 모든 함수들과 예외 처리 클래스들을 스택 클래스 내에서 구현하면 위의 코드와 같다. 다음 포스팅에서는 큐에 대해서 알아볼 예정이다 !