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

  • 

• 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];
         }