[Python] 선형 자료구조 - 스택(Stack)과 큐(Queue)

자료구조는 선형 구조와 비선형 구조로 나눌 수 있다.

선형 구조는 자료들이 순서를 가지고 있는 연속된 자료구조를 뜻한다. 선형 구조를 갖는 대표적인 자료구조는 스택(Stack)과 큐(Queue)가 있는데, 이 글은 이 둘에 대한 개념과 구조, 구현 소스 코드 등을 정리했다.

 

1. 스택(Stack)

한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조로써, 후입선출, LIFO(Last In First Out) 등의 성격을 갖는다.

배열, 연결 리스트 등의 자료구조로 구현할 수 있으며, 파이썬의 리스트도 거의 스택과 비슷한 방식으로 동작한다. push, pop, size, empty, top 등의 연산을 구현할 수 있으며 이를 구현한 코드와 다른 책을 참조한 소스 코드는 각각 아래 링크에 있다.

1) 간단하게 구현한 스택: https://github.com/sjan137/my_useful_python_module/blob/main/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0/simpleStack.py

2) 책을 참조한 스택(<Do it! 자료구조와 함께 배우는 알고리즘 입문> 참조): https://github.com/sjan137/my_useful_python_module/blob/main/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0/stack.py

스택은 컴퓨터 내에서 가장 기본적인 형태의 자료구조 중 하나이며, 발생하는 작업들 사이에 의존 관계가 존재할 때 이용하면 유리하다. 대표적으로 Call Stack, 재귀 함수 등에서 이용된다.

 

2. 큐(Queue)

입구와 출구가 각각 한 쪽 끝에 존재하는 자료구조로써, 선입선출, FIFO(First In First Out) 등의 성격을 갖는다.

큐 또한 배열과 연결 리스트로 각각 구현할 수 있다. 반면 파이썬 내장 라이브러리로도 존재하기 때문에 별도 구현 없이 라이브러리를 이용하는 방법도 있다. 임의로 구현한 코드에서는 push, pop, front, back, empty 등의 연산을 구현했으며, 내장 라이브러리에서도 아래 코드와 같은 메서드가 존재한다.

1) 파이썬 내장 라이브러리 큐

import queue  # 파이썬 기본 라이브러리
q = queue.Queue()

# 또는

from queue import Queue
q = Queue()  # deque([])


q.put(1)  	# deque([1])
q.queue  	# deque([1]) -> 실제 큐 안의 자료 목록을 확인할 수 있음.
q.queue[0]  # 1
q.get(1)  	# deque([])
q.queue 	# deque([])
q.qsize() 	# 0
q.empty()	# True

2) 연결 리스트로 간단하게 구현한 큐: https://github.com/sjan137/my_useful_python_module/blob/main/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0/linkedListQueue.py

운영 체제가 프로세스를 관리하는 기법으로, 동시에 실행되는 여러 프로세스 CPU 등의 자원 배정을 적절히 함으로써 성능 개선이 가능한 자료구조이다. 어떤 작업이 병렬적으로 이루어져도 괜찮고, 작업들 사이에 의존 관계가 존재하지 않을 때 이용하기 유리하다.