C/C++ 實作資料結構的佇列(Queue/FIFO)

資料來源: https://www.rockydora.com/2020/06/c-array-queue.html

https://www.rockydora.com/2020/06/c-linked-list-queue.html

https://shengyu7697.github.io/std-queue/

佇列的基本操作，如下所示：
    1. Push(data)：在尾端加入新資料
    2. Pop：從前端取出資料
    3. getFront：回傳最舊的資料
    4. getTail：回傳最新的資料
    5. getSize：回傳Queue裡的資料個數
    6. IsEmpty：檢查Queue是否是空的

01.純C使用陣列(Array) 

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

int queue[MAXQ];
int front = -1;
int tail =-1;
int size = 0;

int main() {
  for(int i =0; i<5;i++){
    size+=1;
    Push(rand()%100);
  }  

  printf("佇列最前面的資料為:%d\n",getFront());
  printf("佇列最後面的資料為:%d\n",getTail());
  printf("佇列的總數為:%d\n\n",getSize());
  
  while(!isempty()){
    printf("佇列刪除的資料為:%d\n",pop());
  }
  return 0;
}

void Push(int a){
  if(tail==MAXQ)
    printf("佇列已滿");
  else
    queue[++tail] = a;
}

int Pop(){  
  return queue[++front];  
}

int getFront(){
  return queue[front+1];
}

int getSize(){
  return size;
}

int getTail(){
  return queue[tail];
}

int isempty(){
  if(front==tail)
    return 1;
  else
    return 0;
}

02.純C以鏈結串列(Linked List) 

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

struct Node{
  int data;
  struct Node *next;
};

typedef struct Node Queue_Node;
Queue_Node * front = NULL;
Queue_Node * tail = NULL;
int size = 0;

int main() {
  for(int i =0; i<5;i++){
    size+=1;
    push(rand()%100);
  }
  
  printf("佇列最前面的資料為:%d\n",getFront());
  printf("佇列最後面的資料為:%d\n",getTail());
  printf("佇列的總數為:%d\n\n",getSize());
  
  while(front!=NULL)
    printf("佇列刪除的資料為:%d\n",pop());
  return 0;
}

void push(int a){
  Queue_Node * new_add_node;
  new_add_node = (Queue_Node*)malloc(sizeof(struct Node));

  new_add_node->data = a;
  new_add_node->next = NULL;
  
  if(tail==NULL)
    front = new_add_node;
  else
    tail->next=new_add_node;
    
  tail=new_add_node;
}

int pop(){
  Queue_Node *pt = front;
  int i = front->data;
  front = front->next;
  free(pt);  
  return i;  
}

int isEmpty(){
  if(front==NULL)
    return 1;
  else
    return 0;
}

int getFront(){
  return front->data;
}

int getTail(){
  return tail->data;
}

int getSize(){
  return size;
}

03.純C++

以下為 c++ queue 的各種操作用法，把元素加進 queue 的尾部使用 push()，
把元素從 queue 頭部取出用 pop()，注意取出會將該元素從 queue 移除，
取得 queue 的最尾巴的元素使用 back()，
取得 queue 的最頭部的元素使用 front()，注意取得並不會將該元素從 queue 移除，
取得 queue 目前裡面有幾個元素使用 size()，

// g++ std-queue.cpp -o a.out -std=c++11
#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> q;
    q.push(1); // [1]
    q.push(2); // [1, 2]
    q.push(3); // [1, 2, 3]

    cout << q.front() << endl; // 1
    cout << q.back() << endl; // 3
    cout << q.size() << endl; // 3

    int a = q.front(); // copy
    int &b = q.front(); // reference

    cout << q.front() << " " << &q.front() << endl; // 印記體位置
    cout << a << " " << &a << endl;
    cout << b << " " << &b << endl; // 與 q.front() 記憶體位置相同

    // 印出 queue 內所有內容
    int size = q.size();
    for (int i = 0; i < size; i++) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << "\n";

    // 印出 queue 內所有內容
    /*while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << "\n";*/

    return 0;
}