队列 (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 阅读(1062)
评论(0) 编辑 收藏