[CS] 스택(Stack)과 큐(Queue)에 관해서

스택(Stack)이란

책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료 구조를 말하며, 데이터를 기록하는 구조로 객체들의 집합소이다.

주요 용도는 아래와 같다.

1. 웹 브라우저 뒤로가기
2. 실행 취소(undo)
3. 문자열 역순 만들기  

또한, 같은 구조와 크기의 데이터를 한 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근 가능하다.

가장 최근에 삽입된 자료는 가장 위에 있는 top에 위치하고 있으며, 스택에서 자료를 삭제할 떄도 top을 통해서만 가능하다.

• push: 삽입하는 연산
• pop, peek: 삭제하는 연산

LIFO(Last In First Out)

 

위 사진과 같이 데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조이므로

LIFO( 후입선출, Last-In-First-Out ) 구조라고 함.

---

큐(Queue)이란

 

앞서 얘기한 스택(Stack)과는 다르게 먼저 들어온 것이 먼저 나가는 "선입선출"의 개념으로, FIFO(First-In-First-Out)의 구조를 가진다.

주요 용도는

1. 우선순위의 작업 예약
2. 콜센터 고객 대기
3. 너비 우선 탐색(BFS)

데아터를 한 방향으로만 쌓을 수 있고, top을 통해서 접근가능 한 스택과는 달리,

큐는 삽입 작업과 삭제 작업이 양쪽에서 이루어진다.

• front: 삭제연산만 수행되는 위치
• rear: 삽입연산만 수행되는 위치

또한, rear에서 이루어지는 삽입연산을 인큐(eaqueue), front에서 이루어지는 삭제연산을 디큐(dequeue)라고 부른다.