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

Last updated

Was this helpful?