큐(queue)

msung99·2022년 9월 5일
1
post-thumbnail
  • FIFO

시간복잡도

  • 원소추가 : O(1)
  • 원소제거 : O(1)
  • 제일 앞/뒤의 원소 확인 : O(1)
  • 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

원형 큐(Circular queue)

  • 배열로 구현 가능
  • head 나 tail 이 끝 인덱스를 가리키는 상태에서 0번지로 다시 오도록 구현

선형배열 큐 vs 원형 큐

  • 선형 배열로 구현한 큐 : 앞쪽에 공간이 많음에도 불구하고, 새 원소를 추가할 수 없는 상황이 발생

  • 원형 큐 : head 나 tail이 다시 앞쪽으로 돌아오기 때문에 원소의 개수가 배열의 크기보다 커지지 않는 한 문제가 없다.


STL queue

  • push, pop
  • front, back (back 으로 맨뒤 원소도 조회 가능하다는 점 유의하자!)
  • empty, size

유의사항

  • 큐가 비어있는데 front(), back(), pop() 을 호출하면 runtime error가 발생

  • BFS, flood fill 유형 => STL queue 를 꼭 알아야함!!!!!!!!!

profile
블로그 이전 : https://haon.blog

0개의 댓글