[자료구조] 스택(stack), 큐(Queue)

1. 스택 (Stack)

스택이란 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.

📌 스택의 특징

스택은 정해진 방향으로만 쌓을수 있고, 정해진 방향 이외에는 쌓을수 없습니다. 또한 뺄 때는 정해진 방향 반대방향 에서만 뺄 수있습니다. 이 것을 LIFO (Last in First Out) 이라고 합니다. 가장 마지막에 들어온 자료가 가장 먼저 나가게 됩니다.

스택의 변화는 모두 top 이라는 위치에서 실행됩니다. 삽입되는 새 자료는 top 이 가르키는 자료 위에 쌓이고 자료를 삭제할 때도 top을 통해서만 가능합니다.

스택에서 top을 통해 삽입하는 연산을 "push", 스택에서 top을 통해 삭제하는 연산을 "pop" 이라고 합니다.

스택이 비어있을 때 stack.pop 을 시도하면 stack underflow 라 하고 스택의 크기가 비어있을 때 stack.push 를 시도하면 stack overflow 가 발생한다.

✅ 시간 복잡도 - top 위치의 데이터에 바로 접근이 가능하기 때문에 데이터 삽입, 삭제의 복잡도는 O(1) 입니다.

📌 장단점

• 장점 - top 을 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠르다.
• 단점 - top 위치 이외의 데이터에 접근할 수 없기 때문에 탐색이 불가능하다.

📌 스택의 활용 예시

• 깊이 우선 탐색 (DFS, Depth-First Search) 활용
• 웹 브라우저 방문 기록
• 역순 문자열 만들기

2. 큐 (Queue)

큐는 순서대로 줄을 서서 기다리는 것을 뜻합니다.

📌큐의 특징

큐는 한쪽 끝에서 자료를 삽입하고, 반대쪽 끝에서 빠지는 작업이 양쪽으로 이루어집니다.

이 특성을 FIFO(First in First Out) 선입선출 이라 칭합니다. 가장 처음 들어온 친구가 가장 먼저 나가게 됩니다.
큐의 변화는 양쪽 끝에서 이루어집니다.

삽입연산 요소를 리어(rear) 삭제연산 요소를 프론트(front) 로 정하며 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue) 라 하고 큐의 프론트에서 이루어지는 삭제연산을 디큐(dnQueue)라 합니다.

큐 역시 크기가 정해져 있으며 크기 이상으로 무언가를 넣는다면 QueueOverflow가 발생하고, 빈 스택에서 무언가 빼내려면 QueueUnderflow가 발생합니다.

✅ 시간 복잡도 - front, rear 의 위치로 데이터 삽입 삭제가 바로 이루어지기 때문에 시간 복잡도는 O(1) 입니다.

📌 장단점

• 장점 - 데이터 접근, 삽입, 삭제가 빠르다.
• 단점 - 스택과 마찬가지로 중간에 위치한 데이터에 접근이 불가능하다.

📌 큐의 활용 예시

• 너비 우선 탐색 (BFS, Breadth-First Search) 구현
• 우선순위가 같은 작업 예약
• 은행 업무
• 프로세스 관리
• 캐시(Cashe) 구현

Reference

자료구조 스택 큐에 관한 블로그