Queue와 Stack

 

Queue

Queue는 FIFO(first in first out) 선입선출 구조의 자료구조이다. enqueue O(1), dequeue O(1)의 시간복잡도를 가지고 있다.

주로 Cache구현, 프로세스 관리, BFS 등에 활용된다.

데이터의 추가는 enqueue, 데이터의 추출은 dequeue

각각 추가는 가장 뒤에 추가하면 완료이기 때문에 O(1),

삭제의 경우 가장 앞의 데이터를 삭제하면 완료이기 때문에 O(1)의 시간복잡도를 가진다.

• Array-base queue
  • size가 정해진 배열에서 queue형태로 활용하는것으로 삭제(pop)가 일어날 경우 앞쪽 부분의 메모리 공간은 비어있는 채로 남기 때문에 메모리 낭비가 발생할 수 있다.
• Circular queue
  • 마찬가지의 배열 기반 queue지만 삽입하는 과정이 배열의 가장 마지막 부분에 도달했을 경우 , 삭제를 통해 앞쪽 메모리가 비어있다면 가장 앞쪽으로 돌아와 삽입하는 과정을 반복하여 메모리를 활용할 수 있다.
   

• list-base queue
  • linked list 기반으로 queue를 활용할 경우 비는 메모리 없이 queue를 사용할 수 있다는 장점이 있지만 tail에서의 삭제가 효율적이지 않기 때문에 head를 front tail을 rare로 둔 후 사용하는 편이다.

 

Stack

stack은 LIFO(last in first out)의 구조로 나중에 삽입된 데이터가 먼저 추출되는 자료구조이다.

삽입과 삭제는 O(1)의 시간복잡도를 가지며 후위 표기법 연산, 괄호 유효성 검사, 방문기록, DFS에 활용된다.

stack은 재귀적인 특징이 있어 프로그램 개발시 자주 활용된다. ex) call stack, 후위 표기법, DFS에 주로 활용된다.