Queue Using Link List

接續上回的stack，這回做queue（佇列）。

queue像是排隊，先排進隊伍的東西，會先被取出queue，也就是(FIFO, first in first out)，因而我們可以得知queue和stack的差別即queue是一頭放入、另一頭取出，然而stack中放入、取出的都是同一邊。queue實作上我們需要有兩個指標指向分別指向頭和尾。

同時我也參考了別人的code，發現以下一些我的程式和他人的差別：

• 指向頭和尾巴的指標命名不同，有：head/trail, front/rear, etc.
• 放入、取出的函式命名不同，有：pop/push, enqueue/dequeue, etc.
• queue指標定義為廣域(global)或區域(local)
• pop函式傳回值為裡面的data或整個node
• 被handle的error數量

#include 
#include 

#define PUSH 1
#define POP  2
#define DISPLAY 3

#define EMPTY_MESSAGE 2147483647

/*
 * Struct Node Declaration
 */
struct node{ 
 int data;
 struct node *next;
};

struct node *head = NULL, *tail = NULL;

/*
 * Function Declarations
 */
static void push(int new_data);
static int pop();
static void display();

static int isEmpty();

/*
 * Function : main
 */
int main(void){

 while(1){

  // read the user's selection
  int sel;
  printf("[Queue] (1)push\t(2)pop\t(3)display >> ");
  scanf("%d", &sel);

  // do different operations according to the 
  // user's selection
  int new_data, pop_data;
  switch(sel){

   // push
   case PUSH:
    // read data from the user
    printf("push >> ");
    scanf("%d", &new_data);
    // push it in the queue
    push(new_data);
    break;

   // pop
   case POP:
    pop_data = pop();
    if(pop_data != EMPTY_MESSAGE){
     printf("pop >> %d\n", pop_data);
    }
    break;

   // display the queue
   case DISPLAY:
    display();
    break;

   // handle the problem if the user insert
   // something wrong
   default:
    printf("Wrong Selection.\n");

  }

 }

 return 0;
}

/*
 * Function : push
 * Push in a new data to the queue.
 */
static void push(int new_data){

 // create a new node and store the new data in it
 struct node *new;
 new = (struct node *)malloc(sizeof(struct node));
 new->data = new_data;


 // if there's nothing in the queue
 if(head == NULL){
  head = tail = new;
 }
 else{
  // link the new node after the original tail node
  tail->next = new;
  tail = new;
 }

}

/*
 * Function : pop
 * Pop out the topped node in the queue.
 */
static int pop(){

 int pop_data;

 // handle the issue if the queue is empty
 if(isEmpty()){
  printf("The queue is empty.\n");
  return EMPTY_MESSAGE;
 }
 else{
  // store the data of the head into pop_data
  pop_data = head->data;

  // delete the head node and free the memory
  struct node *dump = head;
  head = head->next;
  free(dump);

  // if the user pops out the last node,
  // let tail point to NULL
  if(head == NULL) tail = NULL;
 }

 return pop_data;
}

/*
 * Function : display
 * Display all the data in the queue.
 */
static void display(){

 // start from head
 struct node* ptr = head;

 // if the queue is empty
 if(isEmpty()) printf("The queue is empty.\n");

 // go through the link list
 while(ptr){
  printf("%d\n", ptr->data);
  ptr = ptr->next;
 }

}

/*
 * Function : isEmpty
 * Return whether the queue is empty or not.
 */
int isEmpty(){
 return (head == NULL);
}