원형큐(Circular Queue)란?

2023. 8. 7. 16:42·CS 공부/자료구조

탄생계기

 

rear이 가르키는 포인터가 배열의 마지막 인덱스를 가르키고 있을 때 앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용할 수 없다는 선형 큐의 문제점을 보완하기 위한 자료구조이다.

 

 

기본 동작

- 포인터 증가 방식이 (rear+1)%arraysize 형식으로 변환하기 때문에 배열의 첫 인덱스부터 다시 데이터의 삽입이 가능해진다.

 

 

Enqueue

- rear+1이 배열의 끝이고 포화상태가 아니라면 데이터 삽입을 진행한다.

- (rear+1)%arraysize == front 라면 배열이 포화상태이다. (포화상태 여부를 판단하기 위해 배열의 1칸은 비워둠)

 

 

Dequeue

- front+1의 위치의 데이터를 배열에서 가지고온다.

- 배열이 공백상태가 아니라면 데이터 삭제를 진행한다.

- rear==front 라면 배열이 공백상태이다.

 

 

데이터 입출력 과정

 

→ 초기상태

- rear과 front는 0인덱스부터 시작한다.

- 현재 상태에서 dequeue가 실행되면 rear==front(공백상태)이므로 실행되지 않는다.

 

 

→ Enqueue 1 

(rear+1)%4==front 조건을 검사하고 포화상태가 아니므로 (rear+1)%4를 증가하여 해당 인덱스에 데이터 1의 값을 삽입한다.

 

 

→ Enqueue 2

마찬가지로 포화상태가 아니므로 정상적으로 데이터 2를 삽입한다.

 

 

→ Enqueue 3

이 상태에서 한번 더 enqueue를 하려고 하면 포화 조건 (rear+1)%4==front를 만족하는 포화상태이므로 더 이상 enqueue를 실행하지 못한다.

 

 

→ Dequeue

 

공백 상태 조건인 rear==front을 만족하지 않기 때문에 (front+1)%4한 인덱스에 존재하는 데이터 1을 가지고온다.

 

 

→ Dequeue

- 한번 더 dequeue를 실행한 상태로 마찬가지로 데이터 2를 가지고온다.

- 이 상태에서 두번 연속 dequeue를 실행하게 되면 두번째 dequeue에서 공백 조건에 만족하게 되므로 실행되지 못한다.

 

 

→ Enqueue 4

- 데이터 4를 삽입한 상태로 0번째 인덱스에 삽입이 이루어진다.

- rear 포인터 연산이 (rear+1)%4의 형태로 이루어져 즉, 배열의 크기로 나머지 연산을 함으로써 배열의 인덱스를 계속해서 순환할 수 있도록 한다.

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

여러 종류의 트리(Tree) 정리 (이진 트리, 전 이진 트리, 완전 이진 트리, 포화 이진 트리, 이진 탐색 트리)  (0) 2023.08.09
힙(Heap)이란?  (0) 2023.08.09
Queue & Stack  (0) 2023.06.24
Dynamic Array란?  (0) 2023.06.24
Array vs Linked List  (0) 2023.06.24
'CS 공부/자료구조' 카테고리의 다른 글
  • 여러 종류의 트리(Tree) 정리 (이진 트리, 전 이진 트리, 완전 이진 트리, 포화 이진 트리, 이진 탐색 트리)
  • 힙(Heap)이란?
  • Queue & Stack
  • Dynamic Array란?
횰쓰
횰쓰
개발 성장 블로그입니다
  • 횰쓰
    횰쓰토리
    횰쓰
  • 전체
    오늘
    어제
    • 분류 전체보기
      • CS 공부
        • 운영체제
        • 네트워크
        • 컴퓨터구조
        • 데이터베이스
        • 알고리즘
        • 소프트웨어공학
        • 자료구조
        • 웹
      • 프로그래밍
        • Python
        • NodeJS
      • 프로젝트
        • React 프로젝트
      • 개발도구
        • Git
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    멀티 프로세스
    한국사능력검정시험 심화
    자가균형 이진탐색트리
    3 Way Handshake
    Push-force
    경쟁상태(Race Condition)
    포화이진트리
    전이진트리
    Min힙
    RB트리
    멀티 스레드
    둘만의 암호
    Max힙
    Sync/Async
    운영체제
    리스트정렬여부
    AVL트리
    chrome
    카드뭉치
    페이지 교체
    tcp
    스택
    최태성인강
    프로세스 주소공간
    이진탐색트리
    4 way handshake
    큐
    SQL/NOSQL
    Git
    RB Tree
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
횰쓰
원형큐(Circular Queue)란?
상단으로

티스토리툴바