자료구조 - 스택/큐 O(n)

스택과 큐

배열에서 발전된 형태의 자료구조로 두 자료구조의 구조는 서로 비슷하지만 처리방식이 다르다

 

스택 (Stack)

 

삽입 / 삭제 연산이 후입선출 LIFO (LastInFirstOut) 형태로 이루어지는 자료구조이다.

LIFO : 마지막에 삽입된 값이 가장 먼저 삭제된다
FILO라고도 부른다 (최초 삽입 데이터가 가장 마지막에 삭제된다)

삽입 삭제가 한쪽에서만 발생한다. (입구와 출구가 하나)

 

<그림 설명>

 

스택에 새 값 삽입(PUSH)시 TOP은 새 값을 가리킨다.

스택에서 값 삭제(POP)시 TOP이 가리키는 값을 삭제한다.

결과적으로 스택에서 값을 삭제할경우 현재 시점에서 가장 마지막에 삽입된 값이 삭제된다.

 

<Stack 용어>

• TOP : 삽입 / 삭제가 발생하는 위치 (스택에서는 최 상단에 위치한다.)
• PUSH : TOP 위치에 새 데이터를 삽입하는 연산
• POP : TOP 위치의 데이터를 삭제한 뒤 RETURN을 통해 삭제된 데이터를 확인
• PEEK : TOP 위치의 데이터를 단순히 확인만 함

주요 알고리즘

1. DFS (DepthFirstSearch) : 깊이 우선 탐색
2. 백트래킹 종류

후입 선출 = (일맥상통) = 재귀 함수 알고리즘

따라서 실제 구현 시 Stack보다 재귀 함수 알고리즘을 더 많이 사용

큐보다 특이한 형태라 가끔 응용문제로 출제되기도 하므로 원리를 이해해 둬야한다.

큐 (Queue)

양방향 삽입삭제  즉, 삽입 / 삭제가 각각 양쪽 방향에서 발생한다 (입/출력 출입구가 양쪽으로 구성된 저장공간)

FIFO : 스택과 다르게 먼저 삽입된 데이터가 먼저 삭제된다. (선입선출)

 

<그림 설명>

데이터를 add(추가)할 경우 rear 영역에 추가된다.

데이터를 poll(삭제) 할 경우 front영역의 데이터를 삭제한다.

 

<Queue 용어>

• rear : 큐에서 가장 끝 데이터를 가리키는 영역 (삽입 발생)
• front  : 큐에서 가장 앞 데이터를 가리키는 영역 (삭제 발생)
• add  : rear부분에 새로운 데이터를 삽입하는 연산
• poll  : front부분에 존재하는 데이터를 삭제 후 확인하는 연산 (Stack의 Pop과 비슷)
• peek  : 큐의 맨 앞(front) 데이터를 단순히 확인만 하는 연산

주요 알고리즘

• BFS (Breadth First Search) 너비 우선 탐색

 

+ 번외

<우선순위 Queue>

• 들어간 순서와 상관 없이 우선순위가 높은 데이터를 먼저 추출한다. (우선순위는 Max값 기준)
• Queue 설정에 따라 front에 항상 최대/최소 값이 위치한다.
• 일반적으로 트리 종류의 하나인 힙을 이용하여 구현한다.

 

Queue와 Stack은 LIFO냐 FIFO냐 차이이다.