c语言数据结构--队列


队列简介

队列也是一种在线性表基础上扩展的数据的结构
队列的数据进出方式为先进先出原则
队列数据从一端进入,另一端离开


队列中的几个概念:
数据离开的一端称之为队头
数据进入的一端称之为队尾



定义一个队列

typedef struct QNode{
数据类型 data;
struct QNode *next;
} QNode,*QPtr;

typedef struct{
QPtr f;//队头
QPtr e;//队尾
} duiLie;


创建一个队列
init(duiLie *q){
q->f=q->e =(QPtr)malloc(sizeof(QNode));
if(!q->f) exit(0);
(q->f->next = NULL;
}


入队列

insert(duiLie *q,数据类型 data){
QPtr p = (QPtr)malloc(sizeof(QNode));
p->data = data;
p->next =NULL;

q->e->next=q;
q->e=p;
}


出队列

数据类型 out(duiLie *q){
if(q->f == q->e) return ;//队列为空
数据类型 t;
QPtr p;
t = q->f->data;
p=q->f->next;
q->f->next =p->next;
free(p);
return t;
}


销毁一个队列

void delAll(duiLie *a){
while(a->f){
a->e = a->f->next;
free(a->f);
a->f = a->e;
}
}


循环一个队列


队列的应用 及 队列的优点

#include "stdio.h"
#include "stdlib.h"
typedef struct Q{
   char  data;
   struct Q *next;
}QN,*QPtr;
typedef struct {
   QPtr f; //队头 出队使用
   QPtr e; //队尾 入队使用
} duiLie;

void init(duiLie *q){
   q->f=q->e =(QPtr)malloc(sizeof(QN)); //初始化队列 队列的第一个元素永远是一个空位
   if(!q->f) exit(0);
   q->f->next =NULL;
   
}

void insert(duiLie *q,char e){
     QPtr t;
     t = (QPtr)malloc(sizeof(QN));
     if(!q->f) exit(0); //无头节点
     t->data =e;
     t->next =NULL; 
     q->e->next =t;
     q->e =t;
}

char outDuiLie(duiLie *q)
{ 
  
   QPtr t;
   char t2;
   if(q->f == q->e) exit(0);
   
   t = q->f->next;
   t2 = t->data;
   q->f->next = t->next;
   if(t==q->e){q->e =q->f;} //判断是不是最后一个元素
   free(t);
   return t2;
}

void delDuiLie(duiLie *q)
{
   while(q->f)
   {
     q->e = q->f->next;
     free(q->f);
     q->f = q->e;
   }
}

int main()
{
  char i;
  duiLie *q1;
  init(q1);
  printf("请输入字符串:输入@时结束输入:\n");
  scanf("%c",&i);
  while(i !='@')
  {
    insert(q1,i);
    scanf("%c",&i);
  }

  while(q1->f != q1->e)
      printf("%c",outDuiLie(q1));    


  delDuiLie(q1); //销毁队列
  
  return 1;
}

[root@localhost ~]#./t
请输入字符串:输入@时结束输入:
this is dui lie test!@
this is dui lie test!