[자료구조&알고리즘 | WEEK02] 스택(stack) 자료구조 정리

데이터를 임시 저장하는 기본 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식이다.
LIFO(last in first out)란 가장 나중에 넣은 데이터를 가장 먼저 꺼내는 자료 구조이다.

 

용도

스택은 비교적 구현이 쉬운 편임에도 활용도가 크다. 예를 들어서 브라우저에서 우리가 이전에 들어갔던 페이지로 돌아가기 위해서 '뒤로가기' 버튼을 눌렀을 때도 스택이 사용되고, Ctrl + Z (Undo) 작업도 스택을 이용한 작업이다. 또한 함수가 함수 자신을 호출하는 것(재귀 함수)도 스택에 기반을 두고 있다.(기회가 되었을 때 메모리의 구조를 공부하여 포스팅 해봐야겠다!) 또한 우리가 코드를 돌렸을 때 수많은 에러 내용을 Traceback으로 확인할 수 있을텐데, 이것도 스택에 기반해서 에러 발생한 순서대로 스택에 쌓였다가 가장 최근에 발생한 곳부터 출력하는 (LIFO) 구조를 가지고 있다.(고 한다.)

 

스택 용어 정리

• PUSH: 스택에 데이터를 넣는 작업
• POP: 스택에서 데이터를 꺼내는 작업
• TOP: PUSH를 진행한 데이터에 대해 POP하는 맨 윗부분을 TOP이라고 부름
• BOTTOM: 맨 아랫부분을 BOTTOM이라고 한다.

스택 용어정리(PUSH, POP, TOP, BOTTOM)

 

스택은 배열을 사용하여 구현이 가능하다.
파이썬에서는 별도의 배열을 제공해주지 않기 때문에 리스트로 가능하다.
큐 또한 배열 및 리스트로 구현이 가능하다. 다음 포스팅에서 작성 예정!!

데이터가 추가되고, 추출되는 순서

시간 복잡도

• 푸시(PUSH) - O(1)
  • 스택에 데이터를 저장하는 작업은 마지막 원소 + 1
• 팝(POP) - O(1)
  • 스택에 최근에 들어간 데이터를 추출하는 작업은 마지막 원소를 빼면 되기 때문에 O(1)의 시간이 소요된다.
• 검색(Search) - O(n)
  • 스택에서 데이터를 검색하려면 마지막 데이터부터 처음 원소까지 선형 검색을 진행하므로 O(n)만큼 소요
  • 마지막 데이터부터 처음 원소까지 선형 검색을 진행하는 이유는 팝(POP)할 데이터를 찾기 위함이다.

 

파이썬으로 스택 구현하기

---

고정 길이의 스택 구현 전, 필요한 데이터 정의

스택의 크기란 스택에 쌓을 수 있는 데이터의 최대 개수를 의미한다.

 

 

책의 내용을 참고해서 stack 구현을 연습해보자.
책에서 구현한 stack은 스택을 생성할 때 크기가 결정된 고정 길이 stack이다.

stack 자료구조를 직접 구현해보면서 필요한 데이터가 어떤 것인지 알아보자!

 

Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편

 

스택 배열: stk
데이터를 저장하는 스택 본체 list형 배열이다.
아래 코드에서 __init__ 부분에 선언되어 있으며, 초기 데이터가 없을 때 고정 길이를 생성해주기 위해 [None] * capacity 로 stack의 길이를 제한하게 한다.

 

스택 크기: capacity

스택의 최대 크기를 나타내는 int형 정수이다. 위에서 설명한 stack의 고정 길이를 생성해주기 위한 작업에 속하며, 이 값은 배열 stk의 원소 수인 len(stk)와 일치하다.

 

스택 포인터: ptr

데이터의 개수를 나타내는 정숫값을 스택 포인터(stack pointer)라고 한다.
스택이 비어 있으면 ptr의 값은 0이 되고, 가득 차 있으면 capacity와 같은 값이 된다.
또한 push, pop과 같은 작업을 하면서 ptr은 항상 같이 움직인다.
예를 들어 stk.push(1) 함수를 구현하여 stk에 push 했다고 가정했을 때, 아래와 같이 ptr 값이 증가하고, stk[ptr] 값에 들어가게 된다.

 

스택 포인터의 범위를 지정할 때 주의할 점

스택 포인터 ptr 값은 반드시 0이상이거나 capacity 값 이하가 되어야한다.
따라서 is_empty(), is_full() 함수는 == 연산자를 사용해 정의할 수도 있지만, 어떤 프로그램의 오류로 인해 범위를 넘어갈 수도 있다. 따라서 프로그램의 오류를 줄이기 위해 >=, <= 연산자를 사용해서 스택 배열의 최솟값, 최댓값이 넘어가는 것을 방지할 수 있다.

stk.push(1)

class FixedStack:
    ...
    (생략)
    def push(value: Any):
        if FixedStack.Full:
            에러발생
        ptr += 1 # 스택 포인터 += 1
        stk[ptr] = value
    ...

 

예외 처리 클래스 - Empty

pop() 함수 또는 peek() 함수를 호출할 때 스택이 비어있으면 발생하는 예외처리

 

예외 처리 클래스 - Full

push() 함수를 호출할 때 스택이 가득 차 있으면 발생하는 예외처리

 

class를 초기화 하는 _init_() 함수

__init__() 함수는 스택 배열을 생성하는 등의 준비 작업을 수행
매개변수 capacity 로 전달 받은 값을 스택의 크기를 나타내는 필드인 capacity로 복사하여, 원소 수가 capacity이고, 모든 원소가 None인 리스트형 stk를 생성

 

스택 데이터의 개수를 알아내는 _len()_ 함수

스택의 원소 개수를 알아내는 함수이다. 이때는 ptr(스택 포인터)의 값을 반환하면 된다. ptr의 값이 스택의 원소 개수 + 1과 같다.
해당 함수를 구현해야 파이썬의 내장함수인 len() 함수의 호출이 가능하다. 예를 들어 FixedStack.__len__() 또는 len(FixedStack 인스턴스) 를 사용할 수 있게 된다.

 

스택이 비어있는지 판단하는 is_empty() 함수

스택이 비어 있으면 True, 그렇지 않으면 False를 반환한다.

 

스택이 가득 차 있는지 판단하는 is_full() 함수

해당 함수는 스택의 원소 수가 최대 크기(capacity)에 도달하여 데이터를 더이상 푸시할 수 없는 상태, 즉 스택이 가득 차 있는지 판단하는 함수이다. 가득 차 있으면 True, 그렇지 않으면 False를 반환한다.

 

데이터를 푸시하는 push() 함수

해당 함수는 스택에 데이터를 추가한다. 하지만 스택에 데이터가 가득 차게 되면 FixedStack.Full 예외 처리를 반환하게 된다. 스택이 가득 차 있지 않으면 전달 받은 value를 stk[ptr]에 저장하고 ptr += 1 을 진행하게 된다.

 

데이터를 꺼내는 pop() 함수

스택의 꼭대기(TOP)에서 데이터를 꺼내 그 값을 반환한다. 하지만 스택이 비어 있으면 반환할 값이 없기 때문에 FixedStack.Empty 예외 처리를 반환하게 된다. 스택이 비어 있지 않다면 전달 받은 value를 stk[ptr]의 값을 꺼내어 반환하고, ptr -= 1 을 진행하게 된다.

 

데이터를 들여다보는 peek() 함수

스택의 꼭대기 데이터(TOP)를 확인하게 된다. 하지만 스택이 비어 있으면 반환할 값이 없기 때문에 FixedStack.Empty 예외 처리를 반환하게 된다. 스택이 비어 있지 않다면 전달 받은 value를 stk[ptr]의 값을 반환하고(값을 꺼내는게 아님!!), ptr의 값도 마찮가지로 변화가 없다.(그냥 read임)

 

스택의 모든 데이터를 삭제하는 clear() 함수

해당 함수는 스택에 쌓여 있는 데이터를 모두 삭제하여 빈 스택을 만든다. 스택 포인터(ptr) 값을 0으로 만들면 끝난다.

 

데이터를 검색하는 find() 함수

해당 함수는 스택 본체의 배열 stk 안에 찾으려는 value 값과 같은 데이터가 포함되어 있는지 확인하고, 포함되어 있다면 배열 어디에 들어 있는지 검색한다.
검색은 꼭대기(TOP) 쪽에서 바닥(BOTTOM) 쪽으로 선형 검색을 진행한다.(배열의 인덱스가 큰 쪽에서 작은 쪽으로 스캔)
검색에 성공하면 처음 발견한 인덱스를 반환하고, 실패하게 되면 -1을 반환한다.
꼭대기 쪽에서부터 선형 검색을 하는 이유는 pop() 할 데이터를 찾기 위함이다.

 

데이터 개수를 세는 count() 함수

찾으려는 value 값과 같은 데이터(value)가 스택에 몇 개가 존재하는지, 개수를 구하여 반환한다.

 

데이터가 포함되어 있는지 판단하는 _contains_() 함수

스택에 데이터(value)가 있는지 판단한다. 데이터가 존재하면 True, 그렇지 않으면 False를 반환한다.
해당 함수를 구현해야 파이썬의 멤버십 판단 연산자(membership test operator) in 함수의 호출이 가능하다. 예를 들어 FixedStack.__contains__() 또는 in FixedStack-인스턴스 를 사용할 수 있게 된다.

 

여기서 말하는 FixedStack-인스턴스는 new_instance = FixedStack() 과 같다.

구현한 FixedStack 객체를 사용할 수 있도록 할당하는 개념

 

스택의 모든 데이터를 출력하는 dump() 함수

현재 스택에 쌓여 있는 ptr개의 모든 데이터를 바닥(BOTTOM)부터 꼭대기(TOP)까지 순서대로 출력한다.
print(list)를 하는 것과 같은 개념이다. 실제 구현된 부분에서는 stk[:ptr - 1] 로 반환되도록 구현되어 있다.

 

고정 길이의 스택 구현 - 전체 코드

# fixed_stack.py

from typing import Any


class FixedStack:
    """고정 길이 스택 클래스 구현"""

    class Empty(Exception):
        """비어 있는 FixedStack에 팝 또는 피크할 때 내보내는 예외 처리"""
        pass

    class Full(Exception):
        """가득 찬 FixedStack에 푸시할 때 내보내는 예외 처리"""
        pass

    def __init__(self, capacity: int = 256) -> None:
        """스택 초기화"""
        self.stk = [None] * capacity    # 스택 본체
        self.capacity = capacity        # 스택의 크기
        self.ptr = 0                    # 스택 포인터

    def __len__(self) -> int:
        """스택에 쌓여 있는 데이터 개수를 반환"""
        return self.ptr

    def is_empty(self) -> bool:
        """스택이 비어 있는지 판단"""
        return self.ptr <= 0

    def is_full(self) -> bool:
        """스택이 가득 차 있는지 판단"""
        return self.ptr >= self.capacity

    def push(self, value: Any) -> None:
        """스택에 value를 푸시(데이터를 넣음)"""
        if self.is_full():          # 스택이 가득 차 있는 경우
            raise FixedStack.Full   # 예외 처리 발생
        self.stk[self.ptr] = value
        self.ptr += 1

    def pop(self) -> Any:
        """스택에서 데이터를 팝(꼭대기 데이터를 꺼냄)"""
        if self.is_empty():         # 스택이 비어 있는 경우
            raise FixedStack.Empty  # 예외 처리 발생
        self.ptr -= 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:
        """스택을 비움(모든 데이터를 삭제)"""
        self.ptr = 0

    def find(self, value: Any) -> Any:
        """스택에서 value를 찾아 인덱스를 반환(없으면 -1을 반환)"""
        for i in range(self.ptr - 1, -1, -1):       # 꼭대기 쪽부터 선형 검색
            if self.stk[i] == value:
                return i                            # 검색 성공
        return -1                                   # 검색 실패

    def count(self, value: Any) -> int:
        """스택에 있는 value의 개수를 반환"""
        c = 0
        for i in range(self.ptr):       # 바닥 쪽부터 선형 검색
            if self.stk[i] == value:    # 검색 성공
                c += 1
        return c

    def __contains__(self, value: Any) -> bool:  # 멤버십 연산자인 in를 사용 가능하도록
        """스택에 value가 있는지 판단"""
        return self.count(value) > 0

    def dump(self) -> None:
        """덤프(스택 안의 모든 데이터를 바닥부터 꼭대기 순으로 출력)"""
        if self.is_empty():              # 스택이 비어 있음
            print('스택이 비어 있습니다.')
        else:
            print(self.stk[:self.ptr])  # 바닥부터 스택 포인터(top 값임)을 출력

 

[LAB] 위에서 구현한 FixedStack 실습

위에서 구현한 class를 사용하기 위해서는 같은 폴더 안에 fixex_stack.py 파일이 존재해야 class를 호출할 수 있다.

# [LAB] fixed_stack.py

from enum import Enum
from fixed_stack import FixedStack

Menu = Enum('Menu', ['푸시', '팝', '피크', '검색', '덤프', '종료'])


def select_menu() -> Menu:
    """메뉴 선택"""
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep='     ', end='')
        n = int(input(': '))
        if 1 <= n <= len(Menu):
            return Menu(n)


s = FixedStack(64)

while True:
    print(f'현재 데이터 개수: {len(s)} / {s.capacity}')
    menu = select_menu()        # 메뉴 선택

    if menu == Menu.푸시:        # 푸시
        x = int(input('데이터를 입력하세요.: '))
        try:
            s.push(x)
        except FixedStack.Full:
            print('스택이 가득 차 있습니다.')

    elif menu == Menu.팝:       # 팝
        try:
            x = s.pop()
            print(f'팝한 데이터는 {x}입니다.')
        except FixedStack.Empty:
            print('스택이 비어 있습니다.')

    elif menu == Menu.피크:     # 피크
        try:
            x = s.peek()
            print(f'피크한 데이터는 {x}입니다.')
        except FixedStack.Empty:
            print('스택이 비어 있습니다.')

    elif menu == Menu.검색:     # 검색
        x = int(input('검색할 값을 입력하세요.: '))
        if x in s:
            print(f'{s.count(x)}개 포함되고, 맨 앞의 위치는 {s.find(x)}입니다.')
        else:
            print('검색 값을 찾을 수 없습니다.')

    elif menu == Menu.덤프:     # 덤프
        s.dump()

    else:
        break

실습한 내용은 이미지로 대체!

 

아래 스택 구현과 실습을 통해 어떻게 작동하는지 확인하였다.
(디버깅 모드로 하나씩 찍어보니 Class의 동작 방식도 자연스럽게 한번 익힐 수 있었다.)

 

더 알아보기

---

예외 처리의 기본 구조

• 예외 처리를 수행하면 오류를 복구하여 프로그램이 실행되다가 중단되는 것을 피할 수 있다.
• try 구문(try statement)을 이용해 예외 처리가 가능하다.
  • try: 원래 처리할 로직을 담고 있다. 예외가 발생할 수 있는 가능성이 있다면 해당 스위트(suite)에 작성
  • except: 예외(오류)를 포착하고 처리하는 로직을 담고 있다. 위의 try 구문에서 에러를 발견했다면 프로그램이 중단되는 대신에 해당 스위트가 실행된다.
  • [선택사항] else: 예외(오류)가 포착되지 않았을 때, 처리할 로직을 담고있다.
  • [선택사항] finally: 예외가 발생하든 안하든 무조건 실행하는 로직을 담고있는 스위트 작성 부분

 

raise 문을 이용한 예외 처리

• raise 구문을 이용하여 프로그램의 예외 처리를 의도적으로 반환시킬 수 있다.
  • FixedStack 클래스의 push, pop, peek 함수는 스택이 가득 차 있거나, 비어 있을 때 raise 문을 통하여 예외처리를 진행하고 있다.

 

_len()__함수, __contains_() 함수, 더블 언더스코어의 의미

• 파이썬에서 시작과 끝에 언더스코어(_)가 2개 붙은 함수는 특별한 의미가 있다.(고 한다.)
• 클래스에 __len__() 함수를 정의하면 클래스형의 인스턴스를 파이썬의 내장함수인 len() 함수에 전달할 수 있다. 예를 들어 인스턴스 object에 대한 __len()__ 함수를 호출하는 obj.__len__()를 간단히 len(object) 로 사용이 가능하다.
• 클래스에 __contains__() 함수를 정의하면 클래스형의 인스턴스를 파이썬의 멤버십 판단 연산자인 in 을 적용할 수 있다. 예를 들어 인스턴스 object에 대한 __contains()__ 함수를 호출하는 obj.__contains__(x)를 간단히 x in object 로 사용이 가능하다.
• 이외에도 더블언더스코어를 사용하는 경우가 있는데 파이썬에서 특별히 정의한 변수나 함수에 대해 사용된다. 예를 들어 __init__, __name__ 등은 파이썬에서 특별히 정의된 변수이다.
• 싱글 언더스코어는 private 접근 제어자와 비슷한 기능을 하도록 할 때 사용할 수 있다.
  • 하지만 완벽하게 private 접근 제어자의 기능을 할 수는 없고, 모듈 내부에서만 사용하고자 하는 의도 등을 나타날 때 도움이 될 수 있다.(아래 이미지 참고)
  • 직접 함수를 호출하면 실행이 가능함 ex). Temp._printValue()

• printValue()는 호출되지만, _printValue() 는 호출되지 않는 모습

 

Ref

두잇파이썬
https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D
https://namu.wiki/w/%EC%8A%A4%ED%83%9D(%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0)
파이썬 - 싱글, 더블 언더스코어