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?