[자료구조] 큐 Queue / 배열을 이용한 큐의 구현

 

What is Queue?

• 큐는 입력된 순서대로 순차적으로 처리되기 위해 기다리는 자료들의 모음이다. 
• 따라서 입력 순서에 따라 차례대로 일이 처리되는 성질을 이용하여 다음과 같은 곳에 사용된다. 
  • 운영체제의 작업 스케쥴링 
  • 공유 프린터 작업 스케쥴링 및 버퍼 
  • 데이터 통신/네트워크 등 
  • 각종 시뮬레이션 (대기열 처리, 큐잉 이론) 
• 선입선출 (FIFO : First-In First-Out) 
  • 먼저 들어 온 것이 먼저 사용 또는 제거되는 특징을 가진다. 
  • 스택의 후입선출(LIFO : Last-In First-Out)과 반대되는 개념 
• 기본적으로 첫 원소와 마지막 원소를 각각 가리키는 두개의 포인터(인덱스)를 사용한다. 
  예) front/rear 
• 실전에서는 front는 첫 원소가 아닌 바로 그 앞을 가리키도록 설정 
  (front = rear 이면, 큐가 비어있음을 의미)

  

큐의 주요 연산/함수

• createQueue() - 새로운 큐를 생성한다.
• is_empty(q) - 큐 q가 비어있는지를 검사한다.
• is_full(q) - 큐 q가 가득 찼는지를 검사한다.
• enQueue(q, e) - 큐 q의 맨 뒤에 요소 e를 추가한다.
• deQueue(q) - 큐 q의 맨 처음에 있는 요소를 삭제한다.
• peek(q) - 큐 q의 맨 처음에 있는 요소를 삭제하지 않고 반환한다.
  (비고) peek()와 dequeue()의 차이는 큐에서 해당 값을 제거하는지의 여부

 

배열을 이용한 단일 큐의 구현

#include <iostream>
using namespace std;

const int MAX_NUM = 100;
//define MAX_NUM 100
typedef int element;

class Queue{
public:
    element data[MAX_NUM];
    int front, rear; //두개의 인덱스 사용
    
    Queue(){
        front = rear = -1; //초기화

    }
    bool is_empty(){
        return(front == rear);
    }
    
    bool is_full(){
        return (rear == MAX_NUM -1);
    }
    
    void enQueue(element value){
        if(is_full()){
            cout << "Queue OVERFLOW!!!" << endl;
            exit(-1);
        }
        else{
            data[++rear] = value;
        }
    }
    element deQueue(){
        if (is_empty()){
            cout<<"Queue UNDERFLOW!!!"<<endl;
            exit(-1);
        }
        else{
            return(data[++front]);
        }
    }
    element peek(){
        if(is_empty()){
            cout<< "Queue UNDERFLOW!!!" <<endl;
            exit(-1);
        }
        else{
            return(data[front+1]);
        }
    }
    void printQueue(){
        cout << "Queue 상태: ";
        for(int i = front+1; i <= rear; i++){
            cout << data[i] <<" ";
        }
        cout << endl;
    }
};

int main(){ //void main(){
    Queue MyQueue;
    
    MyQueue.enQueue(10); MyQueue.printQueue();
    MyQueue.enQueue(20); MyQueue.printQueue();
    MyQueue.enQueue(30); MyQueue.printQueue();
    MyQueue.deQueue(); MyQueue.printQueue();
    MyQueue.enQueue(40); MyQueue.printQueue();
    MyQueue.enQueue(50); MyQueue.printQueue();
    MyQueue.deQueue(); MyQueue.printQueue();
}

Queue 상태: 10 
Queue 상태: 10 20 
Queue 상태: 10 20 30 
Queue 상태: 20 30 
Queue 상태: 20 30 40 
Queue 상태: 20 30 40 50 
Queue 상태: 30 40 50