[Data Structure] 스택

스택(stack)은 프로그래밍에서 중요성과 활용도가 매우 높은 자료구조이다. 스택의 기본 개념과 구현에 대해 알아보자.

개념

스택이라는 이름에서 알 수 있듯, 자료를 쌓아 올린 형태의 자료구조이다. 스택에 저장된 자료는 선형 구조를 갖는다.

참고 : 선형 vs. 비선형

• 선형구조: 자료 간 관계가 1대 1.
• 비선형구조: 자료 간 관계까 1대 N. ex) 트리

자료를 쌓아 올린 형태이기 때문에, 당연히 자료를 삽입하거나 꺼낼 수 있다. 자료의 삽입 및 추출 시, 후입 선출(Last in First Out, LIFO)의 원칙을 따른다.

• 삽입 시 a, b, c 순으로 자료를 삽입했다면,
• 꺼낼 때는 c, b, a 순으로 꺼내야 한다.

구현

자료를 선형으로 저장할 수 있는 구조를 사용한다. 파이썬에서는 리스트를 사용하면 된다. 이 때, 좁은 의미에서는 리스트로 구현된 저장소 그 자체를 스택이라고 하기도 한다.

스택을 구현할 때 필요한 하위 개념 및 연산은 다음과 같다.

• top: 스택에서 마지막에 삽입된, 혹은, 마지막 원소의 위치.
• push: 스택에 자료를 저장하는 연산.
• pop: 스택에서 자료를 꺼내는 연산. push된 자료의 역순으로 진행.
• isEmpty: 스택이 공백인지 확인하는 연산.
• peek: 스택의 top 원소를 반환(=참조)하는 연산.

코드 예

구현 시 push, pop 연산을 수행할 때 마지막 top을 변경해주어야 함에 주의한다.

class Stack:
    def __init__(self): # 리스트로 스택 자료구조 구현
        self.itemList = []
    
    def isEmpty(self):
        return not self.itemList # 비어 있으면 True
        
    def push(self, item):
        self.itemList.append(item)
    
    def pop(self):
        if not self.isEmpty():  # 비어 있지 않을 경우만
            return self.itemList.pop(-1)
        else:
            print('Stack Underflow')
            exit()    
    
    def peek(self):
        if not self.isEmpty():
            return itemList[-1]
        else:
            print('Stack Underflow')
            exit()