顺序队列基本操作：初始化、销毁、判断是否为空、进队出队
循环队列基本操作：已知队尾指针和元素个数可以计算出队头指针，设计这种环形队列的初始化、进队、出队判断是否为空
链队：类型定义、初始化、判断是否为空、销毁
注释要尽量详细，让初学者看得懂
#include<stdio.h>
#define MaxSize 5
typedef int ElemType;
struct Queue
{
ElemType data[MaxSize];
int rear,front; //队尾，队头下标
};
//判断队列是否为空
int isEmpty(struct Queue *Q){
return Q->rear==Q->front;
}
//初始化队列
int InitQueue(struct Queue *Q){
Q->rear=0;
Q->front=0;
}
//入队
int EnQueue(struct Queue *Q,ElemType x){
if (Q->rear>=MaxSize)
{
return 0;
}
Q->data[Q->rear++]=x;
return 1;
}
//出队
int DeQueue(struct Queue *Q,ElemType *x){
if (isEmpty(Q))
{
return 0;
}
*x=Q->data[Q->front++];
return 1;
}
//销毁队列
int DestroyQueue(struct Queue *Q){
ElemType x;
while (!isEmpty(Q))
{
DeQueue(Q,&x);
}
return 1;
}
#include<stdio.h>
#define MaxSize 5
typedef int ElemType;
struct CQueue
{
ElemType data[MaxSize];
int rear,num; //num是队列元素个数
};
int InitCQueue(struct CQueue *Q){
Q->rear=0;
Q->num=0;
return 1;
}
int isEmpty(struct CQueue *Q){
return Q->num==0;
}
int EnQueue(struct CQueue *Q,ElemType x){
if (Q->num>=MaxSize)
{
return 0;
}
Q->data[Q->rear]=x;
Q->rear=(Q->rear+1)%MaxSize;
Q->num++;
return 1;
}
int DeQueue(struct CQueue *Q,ElemType *x){
if (isEmpty(Q))
{
return 0;
}
int front=(Q->rear-Q->num+MaxSize)%MaxSize;
*x=Q->data[front];
Q->num--;
return 1;
}
int DestroyCQueue(struct CQueue *Q){
ElemType x;
while (!isEmpty(Q))
{
DeQueue(Q,&x);
}
return 1;
}
#include<stdio.h>
#include<malloc.h>
typedef int ElemType;
//链式队列
//链队的数据存储方式
struct LinkNode
{
ElemType data;
struct LinkNode *next;
};
//链队的头尾指针
struct LinkQueue
{
struct LinkNode *front,*rear;
};
int InitQueue(struct LinkQueue *Q){
Q->front=Q->rear=(struct LinkNode *)malloc(sizeof(struct LinkNode)); //建立头节点
Q->front->next=NULL;
return 1;
}
int isEmpty(struct LinkQueue *Q){
return Q->front==Q->rear;
}
//入队
int EnQueue(struct LinkQueue *Q,ElemType x){
//链队一般不会存满，无需判满
struct LinkNode *s=(struct LinkNode *)malloc(sizeof(struct LinkNode));
s->data=x;
s->next=NULL;
Q->rear->next=s;
Q->rear=s;
return 1;
}
//出队
int DeQueue(struct LinkQueue *Q,ElemType *x){
if(isEmpty(Q)){
return 0;
}
struct LinkNode *p=Q->front->next;
*x=p->data;
Q->front->next=p->next;
if (Q->rear==p)
{
Q->rear=Q->front; //如果队列里只剩下一个要删除的节点，那么此节点删除后，头尾指针要指向同一个地方
}
free(p);
return 1;
}
//销毁队列
int DestroyQueue(struct LinkQueue *Q){
ElemType x;
while (!isEmpty(Q))
{
DeQueue(Q,&x);
}
return 1;
}
循环队列
在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。自己真从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。
循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件时front=rear，而队列判满的条件时front=（rear+1）%MaxSize。
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define Maxsize 100
using namespace std;
typedef struct quenue{
int data[Maxsize];
int fronts;
int rear;
}SqQuenue;
//初始化
int Init_SqQuenue(SqQuenue &S)
{
S.fronts=S.rear=0;
}
//入队
bool EnQuenue(SqQuenue &Q,int x)
{
if((Q.rear+1)%Maxsize==Q.fronts)
return false;
Q.data[Q.rear]=x;
Q.rear=(Q.rear+1)%Maxsize;
return true;
}
//出队
bool DeQuenu(SqQuenue &Q,int &x)
{
if(Q.rear==Q.fronts)
return false;
x=Q.data[Q.fronts];
Q.fronts=(Q.fronts+1)%Maxsize;
return true;
}
//打印
int show_SqQuenue(SqQuenue Q)
{
for(int i=Q.fronts;i<Q.rear;i++)
{
printf("%d ",Q.data[i]);
}
}
int main()
{
SqQuenue Q;
Init_SqQuenue(Q);
EnQuenue(Q,1);
EnQuenue(Q,2);
EnQuenue(Q,3);
show_SqQuenue(Q);
int x;
DeQuenu(Q,x);
printf("%d\n",x);
show_SqQuenue(Q);
return 0;
}
bool Empty(Node *l) {
if (l->len==0)
{
return false;
}
return true;//通过len的大小判断数组是否为空
}