1 什么是队列？
只允许在两端进行插入和删除操作的线性表，在队尾插入，在队头删除 插入的一端，被称为"队尾"，删除的一端被称为"队头"
在队列操作过程中，为了提高效率，以调整指针代替队列元素的移动，并将数组作为循环队列的操作空间。
2 队列的特点
先进先出 FIFO first in first out
后进后出 LILO last in last out
一丶循环队列（顺序队列）
逻辑结构：线性结构
存储结构：顺序存储
操作：增删改查
1.创建空的队列
2.入列
3.求长度
#include <stdio.h>
#include <stdlib.h>
#define N 10
typedef int datatype;//重定义数据类型
typedef struct Sequeue//重定义结构体
{datatype data[N];//定义一个数组存放数据int head;//队列的头，输出数据int tail;//队列的尾，存放数据
} node_t, *node_p;
node_p CreateEmList()//建立一个新的空队列
{node_p p = (node_p)malloc(sizeof(node_t));if (NULL == p){printf("create err");return NULL;}p->head = p->tail = 0;//初始化队列元素return p;
}
int IsEmlist(node_p p)//判断队列是否为空
{return p->head == p->tail;//为空时返回1
}
int Isfull(node_p p)//判断队列是否为满
{return (p->tail + 1) % N == p->head;//为满时返回1
}
int Lenlist(node_p p)//计算队列长度
{return (p->tail - p->head + N) % N;
}
void Clear(node_p p)//清空队列
{p->head = p->tail;
}
int Pushdata(node_p p, int data)//入列
{if (Isfull(p)){printf("Push err");return -1;}p->data[p->tail] = data;p->tail = (p->tail + 1) % N;//更新队尾tailreturn 0;
}
int Popdata(node_p p)//输出数据
{if (IsEmlist(p))//判空{printf("pop err");return -1;}datatype temp = p->data[p->head];//将输出数据存放到temp中p->head = (p->head + 1) % N;//更新队头headreturn temp;
}
int main(int argc, char const *argv[])
{node_p p = CreateEmList();Pushdata(p, 1);Pushdata(p, 2);Pushdata(p, 3);while (!IsEmlist(p)){printf("%d ", Popdata(p));}Pushdata(p, 4);Pushdata(p, 5);Pushdata(p, 6);printf("\n");while (!IsEmlist(p)){printf("%d ", Popdata(p));}printf("\n");Popdata(p);free(p);p = NULL;return 0;
}
二丶链式队列
逻辑结构：线性结构
存储结构：链式存储
1.创建一个空的队列
2.入列
3.出列
#include <stdio.h>
#include <stdlib.h>
typedef int datatype;//重定义数据类型
typedef struct queueLink//重定义结构体名
{datatype data;//数据域struct queueLink *next;//指针域
} node_t, *node_p;
typedef struct
{node_p head;//队头node_p tail;//队尾
} node;
node *CreateEmpty()//创建空表
{node *p = (node *)malloc(sizeof(node));//开辟一个包含队头队尾的堆区空间if (NULL == p){printf("Create Empty err");return NULL;}p->head=p->tail=(node_p)malloc(sizeof(node_t));//对队头队尾开辟空间if (NULL==p->head){printf("head err");return NULL;}p->head->next=NULL;//初始化队列return p;
}
int Isempty(node *p)//判空
{return p->head==p->tail;
}
int Pushdata(node *p,int data)//入队
{node_p p_new=(node_p)malloc(sizeof(node_t));//开辟一个新的堆区空间if(NULL==p_new){printf("p_new err");return -1;}p_new->data=data;p->tail->next=p_new;//连接新节点p->tail=p_new;//更新尾节点return 0;
}
int Popdata(node *p)//出队
{if(Isempty(p))//判空{printf("popdata err");return -1;}node_p p_del=p->head;p->head=p->head->next;free(p_del);return p->head->data;//返回输出数据
}
int LenLink(node *p)//计算队列长度
{int len=0;node_p p1=p->head->next;while(p1){len++;p1=p1->next;}return len;
}
void Cleardata(node *p)//清空队列
{while(!Isempty(p))Popdata(p);
}
int main(int argc, char const *argv[])
{node *p=CreateEmpty();Pushdata(p,1);Pushdata(p,2);Pushdata(p,3);Pushdata(p,4);Pushdata(p,5);Pushdata(p,6);printf("len=%d\n",LenLink(p));while(!Isempty(p))printf("%d ",Popdata(p));printf("\n");Cleardata(p);return 0;
}