이번 스터디 그룹 모임의 주제는 "Queue" 그리고 "Deque"이다.

효율적인 데이터 처리를 위해 반드시 알아두어야 할 개념이라고 생각해서 주제로 선정했고 실용적인 것 같아서 재미있게 공부할 수 있었다. 더불어 "Queue"와 함께 많이 거론되는 "Stack"이라는 개념까지 자연스럽게 학습하게 됐다.

이번 글에서는 "Queue"과 "Deque" 개념을 공부하고 Python 언어를 통해 [Baekjoon Online Judge] 사이트에 있는 큐, 덱 문제들을 풀고 스터디 그룹원들과 함께 리뷰해 보는 과정에서 배운 점들에 대해 기록해 본다.

Stack & Queue

Stack의 개념

LIFO (Last In First Out)

• 가장 마지막에 들어간 것이 가장 처음 나오는 방식의 자료구조 개념 혹은 데이터 처리 방식

예를 들자면 지금 당장 이 글을 보고 있는 브라우저에서 [뒤로 가기] 버튼을 누른다면 브라우저는 바로 직전에 보고 있던 화면을 출력하게 된다.

즉, 현재 페이지를 제외하고 가장 마지막으로 "방문 기록"에 입력된 페이지를 불러오는 것이다.

PC 작업 중 Ctrl + z를 눌러 실행 취소를 할 때도 마찬가지, 이러한 데이터 처리 방식을 Stack이라고 한다.

Stack, 동사로 "쌓이다"라는 의미처럼 밑에부터 쌓아서 가장 위에부터 꺼내 먹는 과자 프링글스 같은 것.

Queue의 개념

FIFO (First In First Out)

• 가장 처음에 들어간 것이 가장 처음 나오는 방식의 자료구조 개념 혹은 데이터 처리 방식

편의점에서 진열대에 물건을 놓을 때 먼저 입고된 물건이 먼저 판매될 수 있도록 하기 위해 사용하는 방식도 FIFO, 흔히 말하는 선입선출이다.

일상생활에서 예를 들면 마트에서 한 줄(Queue)로 서서 계산대에서 계산을 하고 나오는 것을 방식이라고 할 수 있다.

즉, 계산대에 가장 먼저 줄을 선 사람(First in)이 가장 먼저 계산을 마치고 나올 수 있는 것(First out)이다.

우리가 코드를 실행할 때도 먼저 입력된 순서에 따라 코드가 실행되는 것도 이런 방식이라고 볼 수 있을 것 같다.

자료구조 개념 혹은 데이터 처리 방식

Stack과 Queue는 앞서 지속 언급된 것처럼 하나의 개념, 방식이라는 것을 기억해야 할 것이다.

List나 Tuple 등의 실존하는 Data Container가 아니라는 것이다.

Deque

Double Ended Queue

• "양방향 큐"라는 의미로 양쪽 끝에서 빠르게 추가 및 삭제가 가능한 Data Container

Stack과 Queue가 개념이었다면, Deque는 Queue의 개념을 활용한 실존하는 Container Data Type 중 하나다.

collections라는 모듈을 호출한 후 deque() 함수를 호출하여 객체화해서 사용해야 한다.

list처럼 활용할 수 있으면서 "양방향 큐"라는 이름답게 양쪽 끝의 데이터 처리 속도가 빠르다.

간단히 비교해 보면 아래와 같다.

1. 가장 마지막 순서에 데이터 저장

• <list name>.append(<Data>)의 시간 복잡도: $O(1)$
• <deque name>.append(<Data>)의 시간 복잡도: $O(1)$

2. 가장 앞 순서에 데이터 저장

• <list name>.insert(0, <Data>)의 시간 복잡도: $O(n)$
• <deque name>.appendleft(<Data>)의 시간 복잡도: $O(1)$

데이터 처리에서 약 8배의 차이를 보이기 때문에 시간 효율적인 측면에서 필요하다면 적극 활용해야 할 것이다.

단, 빠른 처리 속도를 위해 사용하는 메모리 사용 방식이 Cache Miss를 일으킬 가능성이 있다고 하니 남용하지 않도록 주의하자.