[자료구조] 02 스택, 큐

▶ 스택 (Stack)

: LIFO (후입선출) 구조의 자료구조

: ex) 접시 쌓기

 

 

▶

push : 삽입 (마지막 요소 위에)

pop : 삭제 (마지막 요소를)

 

 

▶ 구현 종류

배열 기반 스택 / (단순) 연결 리스트 기반 스택

 

 

▶ 구현할 만한 예시

: 계산기 (중위 표기법 → 후위 표기법)

전위 표기법	+  5  /  2  7
중위 표기법	5  +  2  /  7
후위 표기법	5  2  7  /  +

 

 

---

 

▶ 큐 (Queue)

: FIFO (선입선출) 구조의 자료구조

: ex) 선착순 줄 서기

 

 

▶

enqueue : 큐에 데이터를 삽입 연산

dequeue : 큐에서 데이터를 꺼내는 연산

 

 

▶ 배열 기반 큐

: 원형 큐 (Circular Queue)

: 배열의 끝에 도달하면 처음으로 순환할 수 있게 논리적 원형으로 구현한 큐

: 하지만 큐의 가득찬 상태와 모두 비워진 상태 구분 불가

: 해결방법

enqueue	Rear가 가리키는 위치 한 칸 이동시킨 다음에 Rear가 가리키는 위치에 데이터 저장한다.
dequeue	Front가 가리키는 위치를 한 칸 이동한 다음에 Front가 가리키는 위치에 저장된 데이터를 반환 및 소멸

 

원형 큐가 텅 빈 상태	Front와 Rear이 동일한 위치를 가리킨다.
원형 큐가 꽉 찬 상태	Rear이 가리키는 위치의 앞을 Front가 가리킨다.

 

 

▶ 덱 (Deque) (Double - Ended Queue)

: 양방향으로 넣고 뺄 수 있는 자료구조로 스택과 큐의 특성을 모두 가지고 있다.

: 양방향 연결리스트 기반 덱