queue-資料的加入以及移除

相對於stack的資料後進先出(LIFO)，在現實生活中，先排隊的就會先跟櫃台買東西(FIFO)，就會有相應的結構，就稱之為queue。通常在程式的實作上，目前的作業系統，不管是windows或是linux based(include mac)工作的排程都是採取FIFO的模式。也就是先預備執行的程式就會優先的先去執行。比如有工作ＡＢＣＤ依照順序的排入系統去執行，對於系統這種多工性的格式來說，會把每一項工作都切分開Ａ->dA+dA+dA+dA.....。如果沒有預設的優先執行緒，一般來說執行方式都會如此：dA->dB->dC->dD -> dA->dB->dC->dD.....當然就演算法來看有其他更有效率的排法。但是目前最廣泛的方式仍然是FIFO的方式去執行。

基本上只要看過了linked list那個章節，stack和queue只是其應用，並不難，所不同的只是資料的排序方式而已。

因此我們先從資料的新增開始吧。概念上很簡單，新增的資料永遠都放在尾即可(Last In Last Out)：

typedef struct queue {
   int data;
   struct queue *next;
}queue;

queue *first = NULL;
queue *end = NULL;


// add data value n to queue list
void add(int n)
{
   // create a node for n
   queue *in;
   in = (queue *) malloc(sizeof(queue));
   in->data = n;

   in->next = NULL;

   if (end == NULL)
      first = end = in;
   else {
      end->next = in;
      end = in;
   }
}

在這邊我就沒有在程式內加入英文說明了，基本上linked list那邊看過之後這邊一看就很簡潔明瞭。首先我們declare & define一個node，稱為in是專門放置新增的資料n的：

   queue *in;
   in = (queue *) malloc(sizeof(queue));
   in->data = n;

接著理所當然的linked list尾端接尾之後:in->next = NULL; 我們就先判斷目前這個queue中是否現有資料才能做link的動作(如果沒有資料而去做link，那麼pointer會沒有一個definition而終告失敗)：

   if (end == NULL)
      first = end = in;
   else {
      end->next = in;
      end = in;
   }

判斷是否為空queue的方式就是去看尾端是否有資料，沒有資料當然這邊就是空的，空的的方式就是把這個現有的node指定為頭和尾。
如果現有資料那麼我們就把資料接在尾端並把它指定為新的尾端即可。

以上就是queue的新增資料，基本上和linked list的insert_in_tail()的function是一模一樣的東西。

而如果要pop out資料呢，那麼秉持著FIFO(LILO)的演算，我們首先要pop out的就會是頭，first:

// remove and return data from first
int pop(void)
{
   queue *out = first;

   if (out != NULL) {
      first = first->next;
      int val = out->data;
      free(out);
      return val;
   }
}

首先我們需要一個暫存的Pointer是為了free用的，把他指向頭:

   queue *out = first;

接著我們仍然要先判斷目前的queue是否存有資料，所以我們就看目前的頭是不是NULL就知道了(又或者像上面的function一樣用end判斷也可以)。畢竟要指定pointer，如果沒有allocation的node在queue裡面，那麼執行就會出問題。

如果有資料在裡頭，我們就移動first到第二個node上面去，然後把要pop out的value暫存下來之後，這個node就可以free掉了。最後再回傳值就可以。

但若沒有資料在裡頭呢，我們當然可以印出message，只是這邊function沒這樣做而已。要先確定你的function的執行方式在自行決定即可