Data Structure: Queue
Introduction
佇列是一種先進先出的一種資料結構，類似於堆疊，但差別在於佇列刪除的元素是最早加入的元素
但是會發生陣列的前面還有空間，但因為rear已經大於等於n - 1，所以會產生佇列已滿的訊息，因此佇列常常以環狀佇列的方式來表示
Methods
Enqueue：加入資料到佇列裡Dequeue：刪除front變數所指的值isEmpty：檢查佇列是否是空的Peek：取得front變數所指的值
Time Complexity
Operation | Time Complexity | Worst Time Complexity | Space Complexity |
Enqueue | O(1) | O(n) | O(1) |
Dequeue | O(1) | O(n) | O(1) |
Peek | O(1) | O(1) | O(1) |
isEmpty | O(1) | O(1) | O(1) |
Queue Implementation
Array Implementation of the Queues
佇列的結構定義
Enqueue()
先判斷佇列是否已滿
如果還有空間就把rear變數加1
否則就顯示已滿訊息
Dequeue()
先判斷佇列是否有資料
如果有就把
front加1來刪除元素
Peek()
判斷是否有資料，否則就顯示最前面的資料
isEmpty()
如果front大於rear，代表佇列是空的，因為一開始front等於0而rear等於-1
完整的程式碼
#include <stdio.h>
#include <stdlib.h>
#define MAX 10 /*定義佇列的大小*/
void enqueueFunction(void);
void dequeueFunction(void);
void listFunction(void);
int isEmpty();
int isFull();
int clear();
int head();
int tail();
int item[MAX];
int front = 0;
int rear = -1;
int main()
{
char option;
while (1)
{
printf("\n *****************************\n");
printf(" <1> insert (enqueue)\n");
printf(" <2> delete (dequeue)\n");
printf(" <3> list\n");
printf(" <4> empty\n");
printf(" <5> full\n");
printf(" <6> clear\n");
printf(" <7> peek\n");
printf(" <8> Tail\n");
printf(" <9> quit\n");
printf(" *****************************\n");
printf(" Please enter your choice...");
option = getchar();
switch (option)
{
case '1':
enqueueFunction();
break;
case '2':
dequeueFunction();
break;
case '3':
listFunction();
break;
case '4':
printf("Is queue empty? %s", isEmpty() ? "Yes" : "No");
break;
case '5':
printf("Is queue full? %s", isFull() ? "Yes" : "No (there are 10 elements that can be accomodated)");
break;
case '6':
clear();
printf("Queue is cleared.");
break;
case '7':
printf("Head: %d", peek());
break;
case '8':
printf("Tail: %d", tail());
break;
case '9':
printf("\n");
return 0;
}
fflush(stdin);
}
}
void enqueueFunction() {
if (rear >= MAX - 1)
{
printf("\n\nQueue is full!\n");
}
else
{
rear++;
printf("\n\n Please enter item to insert: ");
scanf_s("%d", &item[rear]);
}
}
void dequeueFunction() {
if (front > rear)
{
printf("\n\n No item, queue is empty!\n");
}
else
{
printf("\n\n Item %d deleted\n", item[front]);
front++;
}
}
void listFunction() {
int count = 0;
if (front > rear)
{
printf("\n\n No item, queue is empty!\n");
}
else
{
printf("\n\n ITEM\n");
printf(" ------------------\n");
for (int i = front; i <= rear; i++)
{
printf(" %-20d\n", item[i]);
count++;
}
printf(" ------------------\n");
printf(" Total item: %d\n", count);
}
}
int isEmpty() {
if (front > rear)
return 1;
else
return 0;
}
int isFull() {
if (rear == MAX - 1)
return 1;
else
return 0;
}
int clear() {
return front = 0, rear = -1;
}
int peek() {
if (isEmpty()) {
exit(0);
}
else {
return item[front];
}
}
int tail() {
return item[rear];
}
Linked list Implementation of the Queues
佇列的結構定義
Enqueue()
基本上跟陣列的實現是差不多的，只是多了如果是空的話，就把head、rear、front都指向新結點，來代表是佇列的頭節點
Dequeue()
鏈結串列要刪除節點時，只要把head移動到下一個位址就好了
Peek()
isEmpty()
完整的程式碼
#include <stdio.h>
#include <stdlib.h>
typedef struct list
{
int data;
struct list* next;
} list;
list* head = NULL;
list* rear = NULL;
list* front = NULL;
int isEmpty()
{
if (head == NULL)
{
return 1;
}
return 0;
}
int isFull()
{
list* temp = (list*)malloc(sizeof(list));
if (temp == NULL)
{
return 1;
}
return 0;
}
void enqueue(int data)
{
if (isFull())
{
printf("\nQueue is full\n");
return;
}
if (isEmpty())
{
head = (list*)malloc(sizeof(list));
head->data = data;
head->next = NULL;
rear = head;
front = head;
return;
}
list* temp = (list*)malloc(sizeof(list));
temp->data = data;
temp->next = NULL;
rear->next = temp;
rear = temp;
}
void dequeue()
{
int data;
if (isEmpty())
{
printf("\nQueue is empty\n");
return;
}
list* temp = head;
data = temp->data;
head = head->next;
free(temp);
printf("\n%d deleted from queue\n", data);
}
void display()
{
list* temp = head;
if (isEmpty())
{
printf("\nQueue is empty\n");
return;
}
printf("\nQueue is: ");
while (temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int size()
{
int count = 0;
list* temp = head;
if (isEmpty())
{
return count;
}
while (temp != NULL)
{
count++;
temp = temp->next;
}
return count;
}
int peek()
{
if (isEmpty())
{
printf("\nQueue is empty\n");
return -1;
}
return front->data;
}
int rearElement()
{
if (isEmpty())
{
printf("\nQueue is empty\n");
return -1;
}
return rear->data;
}
int clear() {
if (isEmpty()) {
printf("\nThe queue is empty!\n");
return 0;
}
list* current = head;
list* next = NULL;
while (current != NULL)
{
next = current->next;
free(current);
current = next;
}
head = front = rear = NULL;
return isEmpty();
}
int main()
{
int choice, data, position;
while (1)
{
printf("\n1. Enqueue");
printf("\n2. Dequeue");
printf("\n3. Display");
printf("\n4. Size");
printf("\n5. Peek");
printf("\n6. Rear element");
printf("\n7. Is Empty?");
printf("\n8. Clear queue");
printf("\n9. Exit");
printf("\n\nEnter your choice: ");
scanf_s("%d", &choice);
printf("\n");
switch (choice)
{
case 1:
printf("\nEnter data: ");
scanf_s("%d", &data);
enqueue(data);
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
printf("\nSize of queue is: %d", size());
break;
case 5:
printf("\nFront element of queue is: %d", peek());
break;
case 6:
printf("\nRear element of queue is: %d", rearElement());
break;
case 7:
printf(isEmpty() ? "\nTrue\n" : "\nFalse\n");
break;
case 8:
printf(clear() ? "\nCleared\n" : "\n清除失敗\n");
break;
case 9:
exit(0);
default:
printf("\nInvalid choice\n");
}
printf("\n");
}
}
佇列的優點：
簡單易懂：佇列的操作很簡單，只需要按照先進先出的原則即可。
操作效能：佇列可以很快地在表的前端進行刪除、在表的後端進行插入等操作。
佇列的缺點：
佇列大小固定：使用陣列實現佇列時，佇列大小是固定的，如果要擴大佇列的大小需要重新分配空間，這樣會浪費很多時間。
浪費陣列空間：使用陣列實現佇列時，可能會因為佇列空間不足而無法使用，這些空間無法被重複使用，但是如果佇列空間過大，又會浪費空間。
