## Wednesday, December 28, 2011

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

• 放入、取出的函式命名不同，有：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){

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
}
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

// delete the head node and free the memory
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(){

// 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(){