SMALL

일반 큐의 문제점

일반적인 큐는 배열로 일직선으로 구현되어짐. 그리고 선입 선출이라 맨앞에 데이터가 빠져나가면 한칸씩 앞으로 당겨야되기때문에 성능적으로 좋지 않음

 

원형 큐

말그대로 큐를 선형이 아닌 원형으로 생각하여 구현 하는 것이다.

  • enqueue() : 원소 뒤에서 삽입
  • dequeue() : 원소 앞에서 삭제
  • isEmpty() : 공간 확인
  • getSize() : 사이즈 반환

lastOp 변수를 사용하여 큐의 공간 전부를 사용할 수 있게 한다. (즉 원형 큐 문제점 해결방안)

쉽게 이야기하면 마지막 연산을 기록해두는 변수이다.

삽입이 마지막이면 push, 삭제가 마지막이면 pop로 설정하여 front == rear 일때 lastOp가 push이면 포화, lastOp가 pop이면 공백

하지만 큐의 삽입 삭제 연산이 느려짐...

LIST

'전공 > 자료구조' 카테고리의 다른 글

Stable Sort, Unstable Sort  (0) 2021.07.13
삽입정렬  (0) 2021.06.07
B-tree, B+tree  (0) 2021.06.05
AVL 트리 vs Red Black 트리  (0) 2021.06.05
정렬 시간복잡도  (0) 2021.06.05

+ Recent posts