队列
和栈相反，队列（Queue）是一种先进先出（First In First Out，缩写为FIFO）的线性表。
它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就要按请求输出的先后次序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中退出输出操作。凡是申请输出的作业都从队尾进入队列。
在队列中，允许插入的一端叫队尾（rear），允许删除的一端则称为队头（front）。
除了栈和队列之外，还有一种限定性数据结构是双端队列（Deque）。
双端队列是限定插入和删除操作在表的两端进行的线性表。
在实际使用中，还可以有输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入的双端队列）和输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除的双端队列）。
而如果限定双端队列从某个端点插入的元素只能从该端点删除，则双端队列就蜕变为两个栈底相邻的栈了。
尽管双端队列看起来似乎比栈和队列更灵活，但实际上在应用程序中远不及栈和队列有用。
SingleLinkedListQueue.c文件
#include <stdio.h>
#include <malloc.h>
#include "SingleLinkedListQueue.h"
static void clear(SingleLinkedListQueue *This);
static int isEmpty(SingleLinkedListQueue *This);
static int length(SingleLinkedListQueue *This);
static QNode *getHead(SingleLinkedListQueue *This);
static int enQueue(SingleLinkedListQueue *This,QNode *n);
static int deQueue(SingleLinkedListQueue *This,QNode *n);
static int traverse(SingleLinkedListQueue *This,int (*visit)(QNode *n));
SingleLinkedListQueue *InitSingleLinkedListQueue(){
SingleLinkedListQueue *Q = (SingleLinkedListQueue *)malloc(sizeof(SingleLinkedListQueue));
QNode *p = (QNode *)malloc(sizeof(QNode));
Q->This = p;
Q->front = p;
Q->tear = Q->front;
p->next = NULL;
Q->clear = clear;
Q->isEmpty = isEmpty;
Q->length = length;
Q->getHead = getHead;
Q->enQueue = enQueue;
Q->deQueue = deQueue;
Q->traverse = traverse;
return Q;
}
void DestroySingleLinkedListQueue(SingleLinkedListQueue *Q){
Q->clear(Q);
free(Q->This);
free(Q);
Q = NULL;
}
static void clear(SingleLinkedListQueue *This){
QNode *p = This->This->next;
QNode *temp = NULL;
while(p){
temp = p;
p = p->next;
free(temp);
}
p = This->This;
p->next = NULL;
This->front = p;
This->tear = This->front;
}
static int isEmpty(SingleLinkedListQueue *This){
QNode *p = This->This;
if(p->next){
return 0;
}else{
return 1;
}
}
static int length(SingleLinkedListQueue *This){
int j = 0;
QNode *p = This->This->next;
while(p){
j++;
p = p->next;
}
return j;
}
static QNode *getHead(SingleLinkedListQueue *This){
return This->front->next;
}
static int enQueue(SingleLinkedListQueue *This,QNode *n){
if(!n) return -1;
This->tear->next = n;
n->next = NULL;
This->tear = n;
return 0;
}
static int deQueue(SingleLinkedListQueue *This,QNode *n){
if(This->front == This->tear){
n = NULL;
return -1;
}
QNode *temp = This->front->next;
*n = *(temp);
This->front->next = temp->next;
if(This->tear == temp) This->tear = This->front;
free(temp);
return 0;
}
static int traverse(SingleLinkedListQueue *This,int (*visit)(QNode *n)){
if(This->front == This->tear){
return -1;
}
QNode *temp = This->front->next;
while(temp){
if(visit(temp) != 0) break;
temp = temp->next;
}
return 0;
}
SingleLinkedListQueue.h文件
/* Define to prevent recursive inclusion -------------------------------------*/
#ifndef _SINGLELINKEDLISTQUEUE_H
#define _SINGLELINKEDLISTQUEUE_H
/* Includes ------------------------------------------------------------------*/
/* Exported types ------------------------------------------------------------*/
typedef struct QElemType{
int id;
char name[20];
}QElemType;
typedef struct QNode{
QElemType elem; //存储空间
struct QNode *next;
}QNode,*Queueptr;
typedef struct SingleLinkedListQueue{
QNode *This;
Queueptr front; //队头
Queueptr tear; //队尾
void (*clear)(struct SingleLinkedListQueue *This);
int (*isEmpty)(struct SingleLinkedListQueue *This);
int (*length)(struct SingleLinkedListQueue *This);
QNode *(*getHead)(struct SingleLinkedListQueue *This);
int (*enQueue)(struct SingleLinkedListQueue *This,QNode *n);
int (*deQueue)(struct SingleLinkedListQueue *This,QNode *n);
int (*traverse)(struct SingleLinkedListQueue *This,int (*visit)(QNode *n));
}SingleLinkedListQueue;
/* Exported macro ------------------------------------------------------------*/
SingleLinkedListQueue *InitSingleLinkedListQueue();
void DestroySingleLinkedListQueue(SingleLinkedListQueue *Q);
#endif
testSingleLinkedListQueue.c文件
#include <stdio.h>
#include <malloc.h>
#include "SingleLinkedListQueue.h"
char name[][3] = {"xw","xh","xm","xg","xl","xz"};
void strCopy(char *str_a,char *str_b){
while(*str_b != '\0'){
*str_a++ = *str_b++;
}
*str_a = '\0';
}
int printQnode(QNode *node){
printf("id:%d,name:%s\n",node->elem.id,node->elem.name);
return 0;
}
int main(void){
int i;
QNode *node = NULL;
SingleLinkedListQueue *queue = InitSingleLinkedListQueue();
printf("queue is empty:%d\n",queue->isEmpty(queue));
for(i=0;i<6;i++){
node = (QNode *)malloc(sizeof(QNode));
node->elem.id = i;
strCopy(node->elem.name,name[i]);
queue->enQueue(queue,node);
}
queue->traverse(queue,printQnode);
printf("queue is empty:%d\n",queue->isEmpty(queue));
printf("queue length:%d\n",queue->length(queue));
queue->clear(queue);
for (i = 10; i < 16; i++){
node = (QNode *)malloc(sizeof(QNode));
node->elem.id = i;
strCopy(node->elem.name,name[i-10]);
queue->enQueue(queue,node);
}
queue->traverse(queue,printQnode);
while(queue->length(queue)){
node = queue->getHead(queue);
printf("present client: id=%d, name=%s\n",node->elem.id,node->elem.name);
node = (QNode *)malloc(sizeof(QNode));
queue->deQueue(queue,node);
printf("client :id=%d,name=%s finish!\n",node->elem.id,node->elem.name);
free(node);
node = NULL;
}
DestroySingleLinkedListQueue(queue);
return 0;
}
编译：
gcc SingleLinkedListQueue.c SingleLinkedListQueue.h testSingleLinkedListQueue.c -o testSingleLinkedListQueue
运行testSingleLinkedListQueue：
queue is empty:1
id:0,name:xw
id:1,name:xh
id:2,name:xm
id:3,name:xg
id:4,name:xl
id:5,name:xz
queue is empty:0
queue length:6
id:10,name:xw
id:11,name:xh
id:12,name:xm
id:13,name:xg
id:14,name:xl
id:15,name:xz
present client: id=10, name=xw
client :id=10,name=xw finish!
present client: id=11, name=xh
client :id=11,name=xh finish!
present client: id=12, name=xm
client :id=12,name=xm finish!
present client: id=13, name=xg
client :id=13,name=xg finish!
present client: id=14, name=xl
client :id=14,name=xl finish!
present client: id=15, name=xz
client :id=15,name=xz finish!
网友评论