[파이썬(python) 자료구조] 스택(Stack), 큐(Queue)

스택(Stack)

 스택은 후입선출(LIFO)로 처리되는 자료구조이다. 즉, 스택에 가장 마지막에 들어간 요소가 가장 처음으로 꺼내진다. Stack은 무엇인가가 쌓여있는 걸 지칭한다는 점을 생각해보면 가장 마지막에 쌓여진 것이 가장 처음으로 꺼내진다는 것의 개념은 쉽게 이해될 것이다.

 스택은 흔히 연결리스트로 구현된다. 이 경우에 스택 선언을 위해 메모리 내의 연속된 공간을 할당할 필요가 없어지며, 실제로 스택 내의 요소 간 순서가 메모리 내의 물리적 순서와는 무관하게 될 것이다. 그러나 파이썬에서는 리스트가 스택으로 충분히 기능할 수 있기 때문에 연결리스트로 스택을 구현하지 않아도 된다.

 스택의 주 연산은 삽입(push)와 제거(pop)이다. 삽입은 스택의 가장 마지막 자리에 요소가 추가되는 것이고, 제거는 스택의 가장 마지막 요소가 제거되는 것이다. (마지막이라는 단어 선택이 조금 애매할 수는 있으나, 이 정도로 넘어가도록 한다)

 

 

스택의 삽입(push)과 제거(pop)

연결 리스트를 이용하여 스택 구현

# 연결리스트를 담을 Node 클래스 정의
class Node:
	def __init__(self, item, next):
    	# 노드의 값은 item으로, 다음 노드를 가리키는 포인터는 next로 정의
    	self.item = item
        self.next = next

# 스택 클래스 - push() & pop()
class Stack:
	def __init__(self):
    	self.last = None # 스택의 가장 마지막 자리(포인터로 구현)를 None으로 초기화
    
    def push(self, item):
    	# 연결리스트로 스택을 표현 -> 연결리스트 삽입이 앞부분에서 이루어지도록 함
        # 또한 스택 포인터는 가장 마지막에 추가된 연결리스트 노드를 가리키면 됨.
    	self.last = Node(item, self.last)
        
    def pop(self):
    	# 값을 꺼내고, 스택 포인터를 다음 노드로 이동시킴
        item = self.last.item
        self.last = self.last.next
        return item

스택에 순서대로 1,2,3,4를 push했다고 가정한다면, 해당 스택을 그림으로 표현하면 다음과 같다.

 

연결리스트로 구현한 스택

위의 스택에 5를 push하는 과정을 표현하면 다음과 같다. (연결리스트에 삽입 & 스택 포인터 이동)

 

스택의 push

 

스택에서 pop하는 과정을 표현하면 다음과 같다. 값을 복사한 후, 스택포인터 last를 다음 노드로 이동시킨다. 주의할 점은 여기서 연결리스트의 노드 삭제가 일어나는 것이 아니라, 단순히 스택포인터 last만 이동한다는 점이다.

 

스택의 pop

Stack in Python

 파이썬에서의 스택 자료형을 별도로 제공하지는 않지만, 앞서 말한 바와 같이 기본 자료형인 리스트로 스택의 모든 연산을 수행할 수 있다. push 연산은 append로, pop연산은 pop으로 수행 가능하다. 

 

 

---

큐(Queue)

 스택은 Last In First Out의 LIFO 구조였지만, 반대로 큐는 선입선출(First in First Out)의 FIFO 구조이다. 쉽게 말해 대기열을 생각하면 된다. 프린터의 출력 처리나 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다. 큐에는 선형 큐와 환형 큐가 있는데, 선형 큐와 달리 환형 큐는 큐의 head와 rear가 연결되어 있는 구조이다. 큐 역시 주요 연산은 삽입과 삭제가 있다.

 파이썬에서 큐 연산은 리스트로도 충분히 가능하지만, 파이썬의 리스트는 배열로 구현되어 있기 때문에 큐의 제거 연산 시 O(n)의 시간이 소요된다. (첫번째 요소를 제거하고 뒤의 요소를 모두 당겨와야 하기 때문) 따라서 성능을 좀 더 제고하기 위해서는 데크 자료형(deque)을 사용하는 것이 낫다.