Stack, Queue ,Deque 이해하기

스택, 큐, 덱 이해하기

코딩 테스트를 준비할때마다, 스택(Stack), 큐(Queue), 덱(Deque)같은 기본 자료구조를 인터넷 글들을 간단히 보고 사용하고 치우는게 효율적이지않아 정리하는 글입니다.

스택 (Stack)

스택은 후입선출(LIFO) 원칙을 따르는 매우 직관적인 자료구조.
책을 쌓아 올리고 가장 위에 있는 책부터 다시 꺼내는 것을 생각해보면 이해하기 쉽습니다. (중력이 있거나, 한쪽통로가 막힌곳에서 순서대로 쌓는다는 개념으로 이해함)

주요 연산 (추가,제거 후 반환, 조회, 확인)

• push: 스택의 맨 위에 요소를 추가합니다.
• pop: 스택의 맨 위에 있는 요소를 제거하고 그 값을 반환합니다.
• peek 또는 top: 스택의 맨 위에 있는 요소를 조회합니다.
• isEmpty: 스택이 비어있는지 확인합니다.

코딩 테스트에서의 활용

괄호 검사, 후위 표기법 변환, 함수 호출 관리(재귀 포함) 등에 활용됩니다.

큐(Queue)

큐는 FIFO(First In First Out)의 특성을 가진 자료구조입니다.
첫 번째로 삽입된 요소가 첫 번째로 나오는 구조를 가지고 있어, 일렬로 줄을 서는 대기열과 유사합니다.

주요 연산

• enqueue: 큐의 뒤쪽에 요소를 추가합니다.
• dequeue: 큐의 앞쪽에서 요소를 제거하고 그 값을 반환합니다.
• front: 큐의 첫 번째 요소를 조회합니다.
• isEmpty: 큐가 비어있는지 확인합니다.

코딩 테스트에서의 활용

너비 우선 탐색(BFS) 알고리즘, 캐시 구현, 프린터 대기열 관리 등에 활용됩니다.

덱(Deque)

덱은 스택과 큐의 특성을 모두 가진 자료구조로, 양쪽 끝에서 삽입과 삭제가 가능합니다.
이로 인해 더 유연한 자료구조 운영이 가능합니다.

주요 연산

• addFirst: 덱의 앞쪽에 요소를 추가합니다.
• addLast: 덱의 뒤쪽에 요소를 추가합니다.
• removeFirst: 덱의 앞쪽에서 요소를 제거하고 그 값을 반환합니다.
• removeLast: 덱의 뒤쪽에서 요소를 제거하고 그 값을 반환합니다.
• getFirst: 덱의 첫 번째 요소를 조회합니다.
• getLast: 덱의 마지막 요소를 조회합니다.

코딩 테스트에서의 활용

양방향 큐로서의 기능을 활용하여 양쪽에서의 접근을 요구하는 문제
슬라이딩 윈도우, 팰린드롬 검사 등에 활용됩니다.