큐 (queue)

큐 (queue)는 먼저 들어온 데이터가 먼저나가는 선입선출 (First-in First-out)이라고 한다.

구조상 큐가 스택과 다른점은 스택은 삽입과 삭제가 같은 쪽에서 일어나지만 큐는 다른 쪽에서 일어난다.

큐에서 삽입이 일어나는 곳을 rear라 하고 삭제가 일어나는 곳을 front라고 한다.

ADT queue

• 객체 : 0개 이상의 요소들로 구성된 선형 리스트
• 연산:
  • create(max_size) ::= 최대 크기가 max_size인 공백큐를 생성한다.
  • init(q) ::= 큐를 초기화한다.
  • is_empty(q) ::= q가 공백이면 TRUE, else FALSE
  • is_full(q) ::= q가 full이면 TRUE, else FALSE
  • enqueue(q,e) ::= if(is_full(q) ) else q의 끝에 e를 추가한다.
  • dequeue(q) ::= if( is_empty(q)) else q의 맨 앞에 있는 e를 제거하여 반환한다.
  • peek(q) ::= if( is_empty(q)) else q의 맨 앞에 있는 e를 읽어서 반환한다.
   

 

선형큐 (linear queue)

1차원 배열을 이용하여 큐를 구현해보자.

우선 정수의 1차원 배열을 정의하고 삽입, 삭제를 위한 변수인 front와 rear를 만든다.

front는 큐의 첫번째 요소를 가리키고, rear는 큐의 마지막 요소를 가리킨다.

front와 rear의 초기값은 -1이다.

데이터가 삽입되면 rear를 하나 증가하고 그 위치에 데이터가 저장된다.

삭제할때는 front를 하나 증가하고 front가 가리키는 위치에 있는 데이터를 삭제한다. (0->1)

이러한 큐를 선형큐 (linear queue)라고 한다.

 

선형큐의 구현

#include <iostream>
#include <stdexcept>
#define MAX_QUEUE_SIZE 5

typedef int element;

class Queue {
private:
    int front;
    int rear;
    element data[MAX_QUEUE_SIZE];

public:
    Queue() {
        front = -1;
        rear = -1;
    }

    void print() {
        for (int i = 0; i < MAX_QUEUE_SIZE; i++) {
            if (i <= front || i > rear)
                std::cout << "   | ";
            else
                std::cout << data[i] << " | ";
        }
        std::cout << std::endl;
    }

    bool is_full() {
        return rear == MAX_QUEUE_SIZE - 1;
    }

    bool is_empty() {
        return front == rear;
    }

    void enqueue(int item) {
        if (is_full()) {
            throw std::overflow_error("Queue is full.");
        }
        data[++rear] = item;
    }

    int dequeue() {
        if (is_empty()) {
            throw std::underflow_error("Queue is empty.");
        }
        return data[++front];
    }
};

int main() {
    int item = 0;
    Queue q;

    try {
        q.enqueue(10); q.print();
        q.enqueue(20); q.print();
        q.enqueue(30); q.print();

        item = q.dequeue(); q.print();
        item = q.dequeue(); q.print();
        item = q.dequeue(); q.print();
    } catch (const std::exception& e) {
        std::cerr << e.what() << std::endl;
    }

    return 0;
}