キュー


キューとは?


スタックと同様に、位置が限られた資料構造を挿入および削除します.
要素は順番にキューに格納されるため、最初に挿入された要素は最初に削除されます.

キューの先入先出構造



キュー演算

  • enqueue:キューにデータを入れます.
  • dequeue:キューからデータを削除します.
  • キュー実装

    #define QUEUE_SIZE 100
    
    int Queue[QUEUE_SIZE];
    int front = -1, rear = -1;
    
    void enqueue(int val) {
        if (rear >= QUEUE_SIZE - 1)
        	return; // overflow
        else
        	Queue[++Rear] = val;
    }
    
    int dequeue() {
        if (front == rear)
        	return 0; // empty
        else
        	return queue[++front];
    }

    リングキュー


    線形キューの場合、前後の2つの値がアレイの最後に移動すると、キューの前半が空であってもデータを挿入できません.
    円形キューは,この問題を解決するために,配列の末尾を配列の先頭に接続する形式である.

    循環キューの実装

    #define QUEUE_SIZE 100
    
    int Queue[QUEUE_SIZE];
    int size = 0, front = -1, rear = -1;
    
    void enqueue(int val) {
        if (size >= QUEUE_SIZE)
        	return // overflow
        else {
        	size++;
            rear = (rear + 1) % QUEUE_SIZE;
            queue[rear] = val;
        }
    }
    
    int dequeue() {
        if (size == 0)
            return 0; // empty
        else {
            size--;
            front = (front + 1) % QUEUE_SIZE;
            return queue[front];
        }
    }