데이터 구조 (스택, 큐)

스택(stack)

데이터 구조의 하나로서 데이터를 1열로 나열

새롭게 추가한 데이터에만 접근 가능.

- 예시 : 서류를 쌓아 놓은 경우처럼 새로운 서류가 도착하면 현재 서류 더미의 가장 위에 올려두고 서류를 꺼낼 때는 가장 위에서부터 꺼냄

 

스택

스택에 데이터를 추가할 때는 가장 위에 추가된다.

- push (푸쉬) : 스택에 데이터를 추가하는 작업

- pop (팝) : 스택에 데이터를 꺼내는 작업

 

스택처럼 나중에 넣은 것을 먼저 꺼내는 후입선출 구조를 'Last In First Out' 이라고 하며, LIFO 라고도 한다.

 

리스트나 배열과 마찬가지로 스택도 데이터를 1열로 나열한 것이지만,

데이터 추가나 삭제가 단방향으로만 가능하다는 제약이 있다.

또한, 데이터 접근도 스택의 가장 위에 있는 데이터만 가능.

=> "항상 최신 데이터만 접근할 수 있도록 하는 구조에서는 편리하게 사용된다."

 

 

 

큐(queue)

데이터 구조의 하나로, 마찬가지로 데이터를 1열로 나열한 구조.

추가하는 측과 삭제하는 측이 반대. '대기 행렬' 이라고도 불린다.

- 예시 : 줄 서 있는 행렬에서 새롭게 온 사람이 가장 뒤에 서며, 가장 앞에 있는 사람부터 순서대로 처리

큐

큐에서 데이터를 꺼낼 때는 가장 아래, 즉 가장 오래된 데이터부터 꺼낸다.

- enqueue (인큐) : 큐에 데이터를 추가하는 작업

- dequeue (디큐) : 큐에 데이터를 꺼내는 작업

 

큐와 같이 먼저 넣은 것을 먼저 꺼내는 선입선출 구조를 'First In First Out' 이라고 하며, FIFO 라고도 한다.

 

스택에서는 추가와 삭제를 같은 쪽에서 하지만, 큐에서는 추가하는 쪽과 삭제하는 쪽이 반대

=> 오래된 데이터부터 순서대로 처리해야 하는 것은 매우 자연스러운 방식이어서 폭넓게 활용되고 있다.

 

 

> 깊이 우선 탐색에서는 탐색 후보 중에서 항상 최신의 것을 선택해야 하며, 이때 후보 관리에 스택 사용 가능

> 너비 우선 탐색에서는 탐색 후보 중에서 항상 가장 오래된 것을 선택하므로 후보 관리에 큐 활용

 

 

---

참고 서적

: '알고리즘 도감 : 그림으로 배우는 알고리즘 26 (지은이 : 이시다 모리테루, 미야자키 쇼이치 / 옮김 : 김완섭)'