隊列 (queue) 是先進先出（FIFO, First In First Out）的線性表。隊列只允許在后端 (稱為rear) 進行插入操作，在前端 (稱為front) 進行刪除操作。
/**
* <!--
* File : queue.h
* Author : fancy
* Email : fancydeepin@yeah.net
* Date : 2013-02-03
* --!>
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define Element char
typedef struct Node {
Element data;
struct Node *next;
} *QNode;
typedef struct TQueue {
struct Node *front;
struct Node *rear;
} *Queue;
//隊列構造器,創建空隊列
void queueConstructor(Queue &queue){
queue->front = (QNode)malloc(sizeof(Node)); //頭結點
if(!queue->front){
printf("\n為隊列結點分配內存空間失敗!\n");
exit(0);
}
queue->front->next = NULL;
queue->rear = queue->front; //空隊列,rear == front
}
//是否為空隊列
bool isEmpty(Queue queue){
if(queue->front == queue->rear){
return true;
}
return false;
}
//入隊
void enqueue(Queue &queue, Element e){
QNode node = (QNode)malloc(sizeof(Node)); //新結點
if(!node){
printf("\n為隊列結點分配內存空間失敗!\n");
exit(0);
}
node->data = e;
node->next = NULL;
queue->rear->next = node; //新結點排在隊尾
queue->rear = node; //隊尾指針指向新插進的結點
}
//出隊
Element dequeue(Queue queue){
if(isEmpty(queue)){
printf("\n隊列為空,出隊操作失敗!\n");
return ' ';
}
QNode node = queue->front->next; //隊頭結點
Element e = node->data;
queue->front->next = node->next; //隊頭指針指向隊頭結點的下一個結點
if(queue->rear == node){ //隊列的最后一個結點出隊
queue->rear = queue->front; //隊尾結點重新指向頭結點
}
free(node); //釋放空間
return e;
}
/**
* <!--
* File : Queue.cpp
* Author : fancy
* Email : fancydeepin@yeah.net
* Date : 2013-02-03
* --!>
*/
#include "queue.h"
int main() {
Queue queue;
queueConstructor(queue);
enqueue(queue, 'f');
enqueue(queue, 'a');
enqueue(queue, 'n');
printf("%c", dequeue(queue));
printf("%c", dequeue(queue));
printf("%c", dequeue(queue));
//output[result]:fan
return 0;
}
posted on 2013-02-03 08:22
fancydeepin 閱讀(1068)
評論(0) 編輯 收藏