隊(duì)列 (queue) 是先進(jìn)先出（FIFO, First In First Out）的線性表。隊(duì)列只允許在后端 (稱為rear) 進(jìn)行插入操作，在前端 (稱為front) 進(jìn)行刪除操作。
/**
* <!--
* 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;
//隊(duì)列構(gòu)造器,創(chuàng)建空隊(duì)列
void queueConstructor(Queue &queue){
queue->front = (QNode)malloc(sizeof(Node)); //頭結(jié)點(diǎn)
if(!queue->front){
printf("\n為隊(duì)列結(jié)點(diǎn)分配內(nèi)存空間失敗!\n");
exit(0);
}
queue->front->next = NULL;
queue->rear = queue->front; //空隊(duì)列,rear == front
}
//是否為空隊(duì)列
bool isEmpty(Queue queue){
if(queue->front == queue->rear){
return true;
}
return false;
}
//入隊(duì)
void enqueue(Queue &queue, Element e){
QNode node = (QNode)malloc(sizeof(Node)); //新結(jié)點(diǎn)
if(!node){
printf("\n為隊(duì)列結(jié)點(diǎn)分配內(nèi)存空間失敗!\n");
exit(0);
}
node->data = e;
node->next = NULL;
queue->rear->next = node; //新結(jié)點(diǎn)排在隊(duì)尾
queue->rear = node; //隊(duì)尾指針指向新插進(jìn)的結(jié)點(diǎn)
}
//出隊(duì)
Element dequeue(Queue queue){
if(isEmpty(queue)){
printf("\n隊(duì)列為空,出隊(duì)操作失敗!\n");
return ' ';
}
QNode node = queue->front->next; //隊(duì)頭結(jié)點(diǎn)
Element e = node->data;
queue->front->next = node->next; //隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
if(queue->rear == node){ //隊(duì)列的最后一個(gè)結(jié)點(diǎn)出隊(duì)
queue->rear = queue->front; //隊(duì)尾結(jié)點(diǎn)重新指向頭結(jié)點(diǎn)
}
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)
評(píng)論(0) 編輯 收藏