[자료구조] 스택(Stack)과 큐(Queue)

❓ 스택(Stack)이란?

스택(Stack)은 "쌓다"라는 의미로 데이터를 차곡차곡 쌓아 올린 형태의 자료구조입니다. 덧붙여 설명하자면 데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조(LIFO)를 가지고 있습니다.

 

스택은 정해진 방향으로만 쌓을 수 있으며, top으로 정한 곳을 통해서만 접근할 수 있습니다. 새로 삽입되는 자료는 top이 가리키는 가장 맨 위에 쌓이게 되며, 자료를 삭제할 때도 top을 통해서 삭제가 가능합니다.

 

⛏️ 스택의 작동 원리

 

 

 

스택(Stack)은 기본적으로 후입선출(나중에 들어온 데이터가 가장 먼저 나가는)인 LIFO(Last-In-First-Out)구조로 이루어져 있습니다.

 

✅ 스택 제공 연산 종류

• pop( ): 스택에서 가장 위에 있는 항목을 제거합니다. (삭제 연산)
• push(item): item 하나를 스택의 가장 윗 부분에 추가합니다. (삽입 연산)
• peek( ): 스택의 가장 위에 있는 항목을 반환합니다.
• isEmpty( ): 스택이 비어 있을 때 true를 반환합니다.

 

✅ 스택의 구조

 

 

Bottom: 가장 밑에 있는 데이터 또는 인덱스

Top: 가장 위에 있는 데이터 또는 인덱스

Capacity: 스택에 담을 수 있는 데이터의 총 용량

Size: 현재 스택에 담겨져 있는 데이터의 개수

 

✅ 스택(Stack)의 사용 사례

• 웹 브라우저 방문기록(뒤로 가기)
• 실행 취소(undo)
• 역순 문자열 만들기
• 후위 표기법 계산

 

 

❓ 큐(Queue)란?

큐(Queue)는 스택(Stack)과 다르게 먼저 들어온 것이 먼저 나가는 "선입선출"로 FIFO(First-In-First-Out)의 구조를 가지고 있습니다.

 

쉽게 생각하자면 은행에서 먼저 상담 접수를 한 손님이 먼저 상담을 받는 것을 예시로 들 수 있습니다. 만약 예를 들어 대기 순번이 만약 큐(Queue) 형태가 아닌 스택(Stack) 형태라고 가정한다면 먼저 온 손님은 결국 마지막에 상담을 받게 되는 불합리가 이루어질 것입니다.

 

 

삭제 연산이 수행되는 곳을 프론트(front), 삽입 연산이 이루어지는 곳은 리어(rear)로 FIFO구조를 위해서 스택과 다르게 큐의 한 쪽 끝에는 삽입 작업이, 다른 한 쪽 끝에서는 삭제 작업이 나뉘어서 이루어집니다.

 

큐는 리어에서 이루어지는 삽입 연산을 인큐(Enqueue)라고 부르며, 프론트에서 이루어지는 삭제 연산을 디큐(Dequeue)라고 부릅니다.

 

✅ 큐(Queue)의 사용 사례

• 은행 업무
• 콜센터 고객 대기시간
• 대기열 순서와 같은 우선순위의 작업 예약 등
• 프로세스 관리