[데이터구조 & 알고리즘] Stack 및 Queue 개요

Stack

- Last in, first out.

- 포인터는 항상 마지막 요소만 가르킨다.

- 마지막 요소를 삭제하는 경우 포인터만 왼쪽으로 옮긴다. 굳이 삭제한 요소를 비울 필요는 없다.

추가되는 경우 포인터가 다음으로 넘어감

 

Queue

- First in First out

- 두 포인터, 하나는 맨 앞의 요소, 하나는 다음 요소가 들어갈 위치를 가리킨다.

- 배열의 끝에 도달하면 포인터는 맨 처음 인덱스로 돌아간다.

- 배열의 크기가 n인 경우 n-1개의 요소만 저장이 가능하다. 

- 포인터가 같은 곳을 가르키면 큐는 비어졌다고 간주된다.

- 위와 같은 경우 빈 칸이 없으면, 꽉찼을 때 포인터가 같은 곳을 가르키므로 한 칸을 비워둬야 한다.

 

 

Deque/Double-ended Queue

- can remove/add data to either end.

- addLeft, addRight, removeLeft, removeRight.