스택(Stack), 큐(Queue), 덱(Deque)

마구잡이로 코딩테스트 문제를 풀다가 머리에 자료구조에 대한 정리가 안되어 실제 문제를 풀때 활용하지 못하는 경우가 다수 발생한다. 아래와 같이 간단히라도 머리에 넣고 활용하자.

첫 번째 주제로 스택(Stack), 큐(Queue), 덱(Deque)를 선정했다.

스택(Stack)

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다.

자료를 넣는 것을 Push, 자료를 꺼내는 것을 Pop이라고 한다. Python에서는 List의 append와 pop을 이용하여 쉽게 구현이 가능하다.

시간복잡도

• 데이터를 추가: O(1)
• 데이터를 삭제: O(1)
• 맨 위의 데이터를 확인: O(1)

스택 사용의 예

• 수식의 괄호 체크
• 후위표기법(postfix notation) (ex. AB+)
• DFS (깊이 우선 탐색)

큐(Queue)

스택과는 다르게 먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장되는 형식을 말한다.

Python에서는 collection 라이브러리의 deque를 사용하여 구현 합니다.

시간복잡도

• 데이터를 추가: O(1)
• 데이터를 삭제: O(1)
• 맨앞/맨뒤의 데이터를 확인: O(1)

큐 사용의 예

• 프린터의 대기열
• 메세지 큐
• BFS (넓이 우선 탐색)

덱(Deque)

덱은 double-ended-queue의 줄임말로 스텍과 큐를 합친 형태로 생각하면 됩니다.

Python에서는 덱도 큐와 마찬가지로 collection 라이브러리의 deque를 사용하여 구현 합니다.

시간복잡도

• 데이터를 추가(양쪽): O(1)
• 데이터를 삭제(양쪽): O(1)
• 맨앞/맨뒤의 데이터를 확인: O(1)

덱 사용의 예

• 회문 (ex. level)

레퍼런스

위키백과 - 스택
위키백과 - 큐
위키백과 - 덱
BaaaaaaaarkingDog - 스택, 큐, 덱_구버전