[ 자료구조 ] enQueue( )와 deQueue( ) 함수를 이용한 원형큐

스택에 대한 설명 👇🏻

https://tildacoderecorder.tistory.com/101

[자료구조] push( ) 와 pop( ) 함수를 이용한 스택

큐의 개념과 구조

큐 : 스택과 다르게 "선입선출"의 구조를 가지고 있다. 먼저 들어간 것이 먼저 나오는 구조. FIFO = First In First Out

순차큐의 문제점을 보완해 나온 것이 원형큐 = 1차원 배열을 사용하면서 논리적으로 처음과 끝이 원처럼 연결되어 있다고 가정하고 사용. ( 순차큐 설명 생략 )

크기가 8인 1차원 배열의 원형큐

front = 저장된 원소 중에서 첫번째 원소를 가리키는 변수, rear = 저장된 원소 중 마지막 원소를 가리키는 변수

배열이 원으로 이어져 있다고 가정하기 때문에 배열의 마지막 인덱스인 n-1에서 다음 자리인 인덱스 0으로 이동하기 위해 나머지 계산을 함. 

ex ) 위 그림처럼 크기가 8인 배열이 있을 때, 마지막 인덱스인 7에서 다음 인덱스인 0으로 이동하려면 (인덱스+1) % (배열의 크기)를 해야 한다. ( 7 + 1 ) % 8 = 1...0 인덱스는 0

 

즉, 삽입 위치는 각각 front = (front+1) % n, rear = (rear+1) % n이다.

초기 공백 상태는 front = rear = 0

! 조건 : 공백 상태와 포화 상태를 구분하기 위해서 front는 빈 자리로 남겨둠.

 

기본 설정

#define N 10
int Q[N], front=0, rear=0;

 

크기가 10인 1차원 배열 Q를 만들고 front와 rear를 0으로 초기화시킨다.

 

원형큐의 삽입 함수 enQueue( )

: 먼저 원형큐가 포화 상태인지 확인해야 한다. front를 비워둔 채 원소를 꾸준히 삽입해 큐가 가득찬 상태라면 마지막 원소를 가리키는 rear의 다음은 front여야 한다. (front를 빼고 모든 원소가 차 있기 때문)

#include<stdio.h>
 
#define N 10
int Q[N], front=0, rear=0;
 
int enQueue(int num) {
  if ((rear+1) % N == front) printf("ERROR!"); return 0;
 
  rear = (rear+1) % N;
  Q[rear] = num;
  return 1;
 
}

 

if문으로 포화 상태인지 아닌지 확인한다. ( rear + 1 ) % N == front로 rear의 다음이 front인지 판별.

포화 상태라면 에러 메세지를 출력하고 0을 리턴하며 종료.

포화 상태가 아니라면 rear = ( rear+1 ) % N로 위치를 이동하고 이동한 자리에 삽입할 원소 num을 넣어준다. Q[rear] = num. 정상적으로 삽입이 되었으므로 1을 리턴하며 종료.

 

원형큐의 삭제 함수 deQueue()

: 원형큐가 공백 상태인지 확인해야 한다. front와 rear의 초기값은 0이므로 삽입된 만큼 똑같이 삭제 되었다면 둘의 위치는 같다. ex) 크기가 5인 배열에서 2번 삽입하면 front의 위치는 0, rear의 위치는 2이지만 같은 횟수로 2번 삭제하면 front의 위치는 2, rear의 위치도 2.

#include<stdio.h>
 
#define N 10
int Q[N], front=0, rear=0;
 
int deQueue() {
  if( front == rear ) printf("ERROR!"); return 0;
 
  front = (front+1) % N;
  return Q[front];
 
}

 

참조 : C로 배우는 쉬운 자료구조 / 이지영 / 한빛아카데미