스택

• 최근에 삽입한 데이터를 먼저 반환.
• 깊이 우선 탐색(depth-first-search)
  • 한 경로를 깊이 들어가면서 막다른 길에 도달할 때까지 탐색하는 방식

큐

• 가장 오래된 데이터를 먼저 반환.
• 너비 우선 탐색(breadth-first-search)
  • 더 깊이 파고 들어가기 전에 인접한 경로를 얕게 탐색하는 방식

Section 1. 스택

후입선출(LIFO, Last In First Out, 나중에 들어온 것이 먼저 나감) 자료구조.

• 푸쉬(push): 새로운 원소를 스택의 맨 위에 추가한다.
• 팝(pop): 스택의 맨 위에서 원소를 제거하고 반환한다.

항목이 스택의 맨 위에서 추출되기 때문에, 다음에 제거되는 항목은 항상 최근에 추가된 것이다.

예시

• push : 1 → 2 → 3 → 4 → 5
• pop: 5 → 4 → 3 → 2 → 1

1.1. 배열로 스택 구현하기

배열로 스택을 구현할 때는 배열을 사용해 스택에 저장될 값을 유지하고 스택의 맨 위(top)에 해당하는 인덱스를 추적하는 변수를 추가로 사용한다.

Stack {
	Integer: array_size
	Integer: top
	Array of values: array
}

Push(Stack:s, Type: value):
	IF s.top == s.array_size - 1:
		배열 크기를 증가시킨다
	s.top = s.top + 1
	s.array[s.top] = value

Pop(Stack: s):
	Type: value = null
	IF s.top > -1:
		value = s.array[s.top]
		s.top = s.top - 1
	return value