> For the complete documentation index, see [llms.txt](https://jen-hsuan-hsieh.gitbook.io/c-programming/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jen-hsuan-hsieh.gitbook.io/c-programming/1.5.-data-structure/1.5.2.queue.md).

# Queue

* 概念
  * linear data structure which follows a particular order in which the operations are performed.
  * 順序: FIFO(先進先出)
* 主要Function
  * Enqueue: 加入新item到queue中, 如果queue已滿稱為overflow condition
  * Dequeue: 將item從queue移除, 如果queue是空的稱為underflow
  * Front: 取得最前方的item
  * Rear: 取得最後方的item
  * ![](https://github.com/jenhsuan/c-programming/tree/c4549a40f83f3e618feabe284de6c9b80359577f/assets/螢幕快照%202017-03-04%20上午8.27.42.png)
* Implement Queue
  * Array (code in C)

    ```
        #include <stdio.h>
        #include <stdlib.h>
        #include <limits.h>

        // A structure to represent a queue
        struct Queue
        {
            int front, rear, size;
            unsigned capacity;
            int* array;
        };

        // function to create a queue of given capacity. It initializes size of
        // queue as 0
        /*
         * front: 0
         * rear: capacity-1
         * array: int[]
         */
        struct Queue* createQueue(unsigned capacity)
        {
            struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
            queue->capacity = capacity;
            queue->front = queue->size = 0;
            queue->rear = capacity - 1;  // This is important, see the enqueue
            queue->array = (int*) malloc(queue->capacity * sizeof(int));
            return queue;
        }

        // Queue is full when size becomes equal to the capacity
        int isFull(struct Queue* queue)
        {  return (queue->size == queue->capacity);  }

        // Queue is empty when size is 0
        int isEmpty(struct Queue* queue)
        {  return (queue->size == 0); }

        // Function to add an item to the queue.  It changes rear and size
        /*
         * rear加1
         * size加1
         */
        void enqueue(struct Queue* queue, int item)
        {
            /*
             *如果queue滿了則return
             */
            if (isFull(queue))
                   return;
             /*
             * rear值加1
             */
             queue->rear = (queue->rear + 1)%queue->capacity;
            /*
             * 將item的值assign給queue[rear]
             */
            queue->array[queue->rear] = item;
            /*
             * size值加1
             */
            queue->size = queue->size + 1;
            printf("%d enqueued to queue\n", item);
        }

        // Function to remove an item from queue.  It changes front and size
        int dequeue(struct Queue* queue)
        {
             if (isEmpty(queue))
                return INT_MIN;
             /*
              * 取出queue[front]得值並回傳
              */
              int item = queue->array[queue->front];
              /*
               * front值加1
               */
               queue->front = (queue->front + 1)%queue->capacity;
              /*
               * size值減1
               */
              queue->size = queue->size - 1;
              return item;
         }

        // Function to get front of queue
        int front(struct Queue* queue)
        {
            if (isEmpty(queue))
                  return INT_MIN;
            return queue->array[queue->front];
         }

        // Function to get rear of queue
        int rear(struct Queue* queue)
        {
            if (isEmpty(queue))
               return INT_MIN;
            return queue->array[queue->rear];
         }
    ```