[자료구조] 스택(stack)

* 스스로 공부한 내용을 바탕으로 작성한 글입니다. 부정확한 부분이나 오류가 있을 수 있으며, 발견 시 댓글로 알려주세요!

 

 

---

파이썬의 다양한 자료구조 중, 스택이라는 개념이 있다. 스택이란 무엇이고, 파이썬에서 어떻게 활용하는지 알아보겠다.

 

스택이란?

  스택은 가장 나중에 들어온 정보가 가장 먼저 처리되는 후입선출 LIFO(Last In First Out) 구조의 자료구조이다. 가장 쉽게 떠올릴 수 있는 예시로는 프링글스 통을 생각하면 된다. 빈 프링글스 통에 과자를 채울 때는 가장 밑바닥부터 채우게 된다. 우리가 과자를 꺼내 먹을 때는 가장 윗부분의 과자부터 먹게 된다. 이처럼 스택도 입력된 순서대로 앞에서부터 채워나가고, 저장된 데이터를 꺼내려고 하면 가장 최근 저장된 데이터부터 꺼낼 수 있다. 파이썬에서의 스택은 리스트를 사용하여 구현하거나 덱이라는 라이브러리를 이용하여 구현할 수 있다. 

 

스택에 사용할 수 있는 파이썬의 내장 함수는 다음과 같다.

append()	리스트의 맨 뒤에 요소 추가
pop()	리스트의 가장 뒤쪽에서 데이터 꺼내고 삭제
size()	스택의 크기를 반환한다.

 

스택의 연산을 위해 보편적으로 다음과 같은 함수를 정의하고 만들어 사용한다.

push()	스택의 맨 뒤에 요소 추가
peek(), top()	스택의 마지막 요소를 반환 (pop과 다르게 요소를 삭제하지 않음)
isEmpty()	스택이 비었는지에 대해 True/False 반환

 

스택의 연산 함수를 파이썬 코드로 구현하면 다음과 같다.

# 파이썬의 List로 스택 구현하기
class Stack:
    # 스택 선언
    def __init__(self):
        self.stack = []

    # 연산 1. 스택의 맨 뒤에 요소 삽입
    def push(self, item):
        self.stack.append(item)

    # 연산 2. 스택의 맨 위에 있는 요소를 삭제하고 반환
    def pop(self):
        if self.isEmpty():
            print("This Stack is Empty")
        else:
            return self.stack.pop(-1)

    # 연산 3. 스택의 맨 위에 있는 요소를 삭제하지 않고 반환
    def peek(self):
        if self.isEmpty():
            print("This Stack is Empty")
        else:
            return self.stack[-1]

    # 연산 4. 스택이 비어있는 지를 bool값으로 반환
    def isEmpty(self):
        if len(self.stack)==0:
            return True
        else:
            return False

 

  덱 라이브러리를 가져와서 스택처럼 사용하기도 한다. 덱에 대해서는 다음에 더 자세히 다루어보겠다. 스택이라는 자료구조를 구현하기 위해 활용하는 덱의 내장 함수들은 다음과 같다.

from collections import deque

# 덱 선언
dq = deque()

# 덱의 가장 오른쪽에 요소 삽입
dq.append()
# 덱의 가장 왼쪽에 요소 삽입
dq.appendleft()
# 덱 초기화 - 덱 안의 모든 요소 삭제
dq.clear()
# 덱 복사
dq.copy()
# 덱 내부의 요소 x의 개수 세기
dq.count(x)
# 덱의 특정한 위치(i번째)에 요소 x 삽입
dq.insert(i,x)
# 덱의 가장 오른쪽 요소를 삭제하며 반환 (빈 덱일 때는 IndexError 발생)
dq.pop()
# 덱의 가장 왼쪽 요소를 삭제하며 반환 (빈 덱일 때는 IndexError 발생)
dq.popleft()
# 덱의 가장 첫번째 x값 삭제 (값이 없으면 ValueError 발생)
dq.remove(x)