[자료구조와 알고리즘 with Python] 1. 스택

1 - 1 스택이란?

스택(Stack)은 마지막에 들어간 자료가 가장 먼저 나오는 구조이다.

예) 설거지를 한 그릇을 설거지통에 넣어놓으면 요리사가 맨 위에 놓인 접시를 가져가 음식을 담아 손님들에게 제공

예) 웹 브라우저의 뒤로가기, 네이버 홈페이지 -> 뉴스 -> 스포츠 뉴스에서 뒤돌아가면 뉴스 -> 네이버

 

스택은 예시들처럼 후입선출(Last In First Out) 형태의 자료구조이다.

설거지통에서 맨 윗 부분을 상단(stack top)이라고 하고 스택에 저장되는 데이터를 요소라고 한다.

스택은 요소의 삽입과 삭제가 상단에서만 이루어진다.

 

스택의 연산

push(item): item이라는 요소를 맨 위에 넣음

pop(): 스택의 맨 위의 요소를 꺼내 return

is_empty(): 스택이 비어있으면 True, 아니면 False

is__full(): 스택이 꽉 차있으면 True, 아니면 False

peek(): 스택의 맨 위의 요소의 값만 받아옴

size(): 스택의 전체 요소 갯수

 

만약 지정한 용량을 넘어서게 push를 한다면 입력이 불가하고 이를 stack overflow라고 한다.

반대로 빈 스택을 peek하거나 pop하면 stack underflow라고 한다.

1 - 2 배열 구조로 스택 구현하기

모든 요소가 인접한 메모리 공간에 저장된 배열 구조가 있고,

인접한 메모리 공간이 아니라 흩어져 있는 요소들을 연결해 하나로 관리하는 방법인 연결된 구조가 있다. 배열구조보다 유연하게 사용 가능하지만 관리가 복잡하다.

capacity = 10
array = [None] * capacity
top = -1

def is_empty():
    return top == -1

def is_full():
    return top == capacity - 1

def push(e):
    global top
    if is_full():
        return "stack overflow"
    top += 1
    array[top] = e
    
def pop():
    global top
    if is_empty():
        raise IndexError("stack underflow")
    item = array[top]
    array[top] = None
    top -= 1
    return item

def peek():
    if is_empty():
        raise IndexError("stack underflow")
    return array[top]

def size():
    return top + 1

스택의 연산을 코드로 구현해봤다. 하지만 자료구조는 함수를 기반으로 하는 절차적 프로그래밍보다 클래스를 기반으로 하는 객체 지향 프로그래밍 기법을 이용하는 것이 더 좋기 때문에 클래스를 이용해 다시 만들어보겠다.

class ArrayStack:
    def __init__(self, capacity):
        self.capacity = capacity
        self.array = [None] * capacity
        self.top = -1
        
    def isEmpty(self):
        return (self.top == -1)
    
    def isFull(self):
        return (self.top == self.capacity - 1)
    
    def push(self, item):
        if self.isFull():
            raise OverflowError("stack overflow")
        self.top += 1
        self.array[self.top] = item
        
    def pop(self):
        if self.isEmpty():
            raise IndexError("stack underflow")
        p = self.array[self.top]
        self.array[self.top] = None
        self.top -= 1
        return p
    
    def peek(self):
        if self.isEmpty():
            raise IndexError("stack underflow")
        return self.array[self.top]
    
    def size(self):
        return self.top + 1

다른 언어들과는 다르게 파이썬 클래스는 객체 자신을 나타내는 self를 모든 멤버함수의 첫번째 매개변수로 넣어야한다.

또한 생성자는 클래스의 객체가 만들어질 때마다 자동으로 호출되는 함수다.

1 - 3 스택의 응용: 괄호 검사

위의 ArrayStack 클래스를 활용해 괄호 검사를 해보았다.

from prac_stack import ArrayStack

def checkBrackets(statement):
    stack = ArrayStack(100)
    for bracket in statement:
        if bracket in '({[':
            stack.push(bracket)
        elif bracket == ')':
            if not stack.isEmpty() and stack.peek() == '(':
                stack.pop()
            else:
                return False
        elif bracket == '}':
            if not stack.isEmpty() and stack.peek() == '{':
                stack.pop()
            else:
                return False
        elif bracket == ']':
            if not stack.isEmpty() and stack.peek() == '[':
                stack.pop()
            else:
                return False
    return stack.isEmpty()

# 테스트
print(checkBrackets('{ A[(i+1)]=0;}'))  # True
print(checkBrackets('if ((x<0) && (y<3)'))  # False
print(checkBrackets('][qewr]'))  # False

괄호 검사 프로그램을 만들고 테스트를 해봤다.

1 - 4 파이썬에서 스택 사용하기

파이썬 리스트를 스택으로 사용해봤다.

연산	ArrayStack	파이썬 list	사용 예
삽입	push(item)	메서드 append() 사용	li.append(item)
삭제	pop()	메서드 pop() 사용	li.pop()
요소의 수	size()	내장 함수 len() 사용	len(li)
공백 검사	is_empty()	요소의 수가 0인지 검사	len(li) == 0
포화 상태 검사	is_full()	의미 없음, 항상 False	False
상단 들여보기	peek()	맨 마지막 요소 참조	li[-1]

 

또한 파이썬 queue 모듈에서 큐(Queue), 스택(LifoQueue), 우선순위큐(PriorityQueue)등을 클래스로 제공해준다.

1 - 5 시스템 스택과 순환 호출

운영체제에서도 스택이 중요한 역할을 하는데 다양한 함수들이 호출되고 다시 돌아가는데 사용된다.  이러한 시스템 스택을 활용하는 프로그래밍 기법이 순환이다.

예를 들어 팩토리얼 계산을 하는 코드를 만드려고 하는데 계속 곱하는게 아닌

def factorial(n):
    result = 1
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)
        
print(factorial(10))

이렇게 만들면 결국 팩토리얼 계산이 된다.

 

반복문과 연산의 횟수 차이는 없지만 순환은 트리와 같은 특정한 문제에서 훨씬 명확하고 간결한 코딩이 가능하다.

 

★ ★ ★ ★ ★

이 블로그는 수익창출을 목적으로 하지 않고, 제가 공부를 하기 위해 운영하고 있습니다.

따라서, 블로그 내의 모든 콘텐츠는 제 주관적인 의견과 경험을 바탕으로 작성되었으며, 모든 정보의 정확성을 보장할 수 없습니다.

만약 블로그 내의 정보에 대해 의문이 있으시거나, 정확하지 않은 정보를 발견하신다면, 언제든지 저에게 알려주시기 바랍니다.

이 블로그가 여러분의 공부에 도움이 되기를 바랍니다.

감사합니다.

★ ★ ★ ★ ★

참고한 교재 : 자료구조와 알고리즘 with 파이썬

https://www.booksr.co.kr/product/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-with-%ED%8C%8C%EC%9D%B4%EC%8D%AC/