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

[ 스택(Stack) ]

 데이터를 차곡차곡 쌓아 올린 형태의 자료구조

한쪽 끝에서만 삽입과 삭제가 이루어지는 후입선출(LIFO, Last-In-First-Out) 구조

 

스택(Stack)

 스택은 책을 쌓아놓은 것과 유사한 개념으로 이해하면 된다.

책을 쌓아놓을 때 새로운 책을 얹거나 또는 있는 책을 뺄 때는 맨 위부터 접근이 가능한 것처럼!

 

 스택에서는 Push, Pop 이 두 가지만 알면 된다!

Push(삽입): 스택에 새로운 항목을 추가하는 연산, 스택의 맨 위에 배치.

Pop(제거): 스택에서 가장 위에 있는 항목을 제거하고 반환하는 연산.

 

[ 특징 ]

후입선출(LIFO): 가장 최근에 추가된 항목이 가장 먼저되는 구조.

제한된 접근: 스택은 가장 위의 항목만 접근할 수 있으며, 데이터를 추가하거나 제거할 때는 항상 가장 위를 조작한다.

-> 중간에 있는 항목에 접근하려면 가장 위부터 차례대로 제거해야 함.

간단한 연산: Push(삽입)와 Pop(제거) 연산을 사용.

재귀적 구조: 재귀적인 알고리즘을 구현하는 데 유용.

 

 스택은 데이터를 임시로 저장하거나 역순으로 처리해야 하는 경우에 유용하다.

함수 호출 시 지역 변수와 복귀 주소를 저장하는 데에도 사용되기도 하며, 역추적 알고리즘, 웹 브라우저의 뒤로가기 버튼 등에서 스택이 활용될 수 있다.

 

 

[ 큐(Queue) ]

 먼저 삽입된 데이터가 먼저 삭제되는 선입선출(FIFO, First-In-First-Out) 구조

 

큐(Queue)

 큐는 대기열과 비슷한 개념이라고 생각하면 된다.

일상에서 줄을 설 때 먼저 온 사람이 먼저 일을 보고 가는 것처럼!

 

 큐에서는 Enqueue, Dequeue 이 두 가지만 알면 된다!

Enqueue(삽입): 큐의 가장 뒤에 새로운 항목을 추가

Dequeue(제거): 큐의 가장 앞에 있는 항목을 제거하고 반환

 

 

[ 특징 ]

선입선출(FIFO): 가장 먼저 추가된 항목이 가장 먼저 제거되는 구조

제한된 접근: 큐는 가장 앞쪽의 항목에만 접근 가능하며, 데이터를 추가하거나 제거할 때는 항상 큐의 앞쪽을 조작한다.

-> 중간에 있는 항목에 접근하려면 앞쪽부터 차례로 제거해야 함.

간단한 연산: Enqueue(삽입)와 Dequeue(제거) 연산을 사용.

재귀적 구조: 재귀적인 알고리즘을 구현하는 데 유용.

-> 너비 우선 탐색(BFS) 알고리즘과 같이 큐를 활용하는 알고리즘은 재귀 호출 대신 큐를 사용하여 데이터를 처리.

 

 큐는 데이터를 순차적으로 처리해야 할 경우에 유용하다. 

작업 큐, 프로세스 스케줄링, 그래프 알고리즘 등에서 사용된다.