[Data Structure] 스택(Stack)과 큐(Queue) 개념, 특징, 활용 예시

 

🔎 스택(Stack)이란?

📘 스택의 개념

스택(stack)이란 어떠한 자료를 쌓아서 올려놓은 형태의 자료구조입니다.
책상에 쌓여있는 책들이나 싱크대의 접시를 예시로 들 수 있습니다.

 

📝 스택의 특징

스택은 위의 그림과 같이 아래에서 위로 쌓이는 형식이며 가장 최근에 들어온 자료를 top이라고 부릅니다.
뻥튀기를 꺼낼 때 가장 아래쪽의 뻥튀기를 꺼내려면 위에서부터 차례대로 뻥튀기를 꺼내야 하는 것처럼 가장 위쪽(최신)의 데이터부터 꺼낼 수 있으며 이러한 스택의 구조를 후입선출(LIFO, Last In First Out)의 구조라고 합니다.
즉, 스택의 경우 자료의 삽입과 삭제는 한 곳(top)에서만 이루어지게 됩니다.

만약 스택이 비어있을 때 자료를 꺼내려고 시도를 하면 스택 언더플로우(Stack Underflow)가 발생하고
반대로, 스택이 꽉 차있을 때 자료를 넣으려고 하면 스택 오버플로우(Stack Overflow)가 발생하게 됩니다.

 

🌏 스택의 활용 예시

• 웹 브라우저 뒤로 가기 : 가장 나중에 열린 페이지부터 뒤로 가기를 실행합니다.
• 문서작업에서 Ctrl+Z : 가장 나중에 수정한 내역부터 되돌립니다.
• 역순 문자열 만들기 : 맨 끝의 문자열부터 차례대로 만들어집니다.
• 후위 표기법 계산
• 재귀적 알고리즘

 

 

🔎 큐(Queue)란?

📘 큐의 개념

게임을 하시는 분이시라면 "큐가 빨리 안 잡히네..."라는 말의 의미를 아실 겁니다.
큐란 쉽게 말해 데이터들이 일렬로 줄 서서 기다리는 것을 뜻하는데,
놀이기구를 기다리는 줄, 음식점 번호표 같은 것을 예시로 들 수 있을 것 같습니다.

 

📝 큐의 특징

정해진 곳(top)에서만 자료의 삽입과 삭제가 이루어지는 스택과는 다르게 큐는 Rear부분에서 자료의 삽입이, Front부분에서 자료의 삭제가 이루어집니다. 
편의점에서 알바생이 음료수 냉장고 뒤편에서 채운 음료수가 먼저 나가게 되는 것처럼 큐는 선입선출(FIFO, First In First Out)의 자료구조를 가집니다.

 

🌏 큐의 활용 예시

• 은행창구 번호표 대기 : 빠른 번호표를 가진 사람이 먼저 업무를 봅니다.
• 프린터 출력 : 가장 먼저 대기열에 오른 프린트가 먼저 출력됩니다.
• 컴퓨터 운영체제의 태스크 스케쥴링 : 가장 간단한 형태의 선입선 처리 스케쥴링 정책
• 너비 우선 탐색(BFS) 알고리즘