[자료구조] Queue와 Stack

큐와 스택

큐 : First-In-First-Out(FIFO) 자료구조

스택 : Last-In-Last-Out(LIFO) 자료구조

 

큐

큐의 Circular 구조

- 사용하는 이유 : enqueue, dequeue를 반복하다 보면 앞부분이 비어 버리기 때문.

- 구현법

  1) ArrayList-based 구현의 경우 : 인덱스 사용할 때 모듀로 n 연산을 하면 되지 않을까요?

  2) LinkedList-based 구현의 경우 : circular linked list를 사용한다.

- 주의사항 : 어떤 구현 방법이든, Empty, Full을 front와 tail로 판단할 수 없기 때문에 길이를 저장해 둔다.

 

큐와 스택의 적용

큐 : BFS

스택 : DFS, 후위표기법 계산기, 괄호 판별하기, 함수 호출

큐, 스택 혼합 : 팰린드롬 판별