队列的顺序实现（6种方式）

一、定义队尾指针指向队尾元素下一个位置 方案一（牺牲1个空间）：

/***判断队满条件：队尾指针的再下一个位置是队头****/ /***即：(Q.rear+1)%Maxsize == Q.front。***********/ /***代价：牺牲一个存储单元.***********************/ #include<stdio.h> /*队列定义*/ #define Maxsize 10 typedef struct{ int data[Maxsize]; //静态数组存放队列元素 int front,rear; //队头指针和队尾指针 }SqQueue; /*初始化队列*/ void InitQueue(SqQueue &Q){ Q.front = Q.rear; //初始时，队头队尾指针指向0 } /*入队操作*/ bool EnQueue(SqQueue &Q, int x){ if((Q.rear+1)%Maxsize == Q.front) //队满则报错 return false; Q.data[Q.rear] = x; //新元素插入队尾 Q.rear = (Q.rear+1)%Maxsize; //队尾指针加一取模 return true; } /*出队操作*/ bool DeQueue(SqQueue &Q, int &x){ if(Q.rear == Q.front) //队空则报错 return false; x = Q.data[Q.front]; Q.front = (Q.front+1)%Maxsize; //队头指针后移 return true; } /*获取队头元素的值，用x返回*/ bool GetHead(SqQueue Q, int &x){ if(Q.rear == Q.front) //队空则报错 return false; x = Q.data[Q.front]; return true; } int main(){ int ret; //用来获取返回值 SqQueue Q; InitQueue(Q); EnQueue(Q,1); EnQueue(Q,2); EnQueue(Q,3); GetHead(Q,ret); printf("QueueHead is:%d\n"); DeQueue(Q,ret); GetHead(Q,ret); printf("QueueHead is:%d\n"); return 0; }

方案二（size）：

/***判断队满方法:用size记录当前队列长度****/ /***即：Q.size == Maxsize表示队满************/ #include<stdio.h> /*队列定义*/ #define Maxsize 10 typedef struct{ int data[Maxsize]; //静态数组存放队列元素 int front,rear; //队头指针和队尾指针 int size; //队列当前长度 }SqQueue; /*初始化队列*/ void InitQueue(SqQueue &Q){ Q.front = Q.rear; //初始时，队头队尾指针指向0 Q.size = 0; } /*入队操作*/ bool EnQueue(SqQueue &Q, int x){ if(Q.size == Maxsize) //队满则报错 return false; Q.data[Q.rear] = x; //新元素插入队尾 Q.rear = (Q.rear+1)%Maxsize; //队尾指针加一取模 Q.size++; return true; } /*出队操作*/ bool DeQueue(SqQueue &Q, int &x){ if(Q.size == 0) //队空则报错 return false; x = Q.data[Q.front]; Q.front = (Q.front+1)%Maxsize; //队头指针后移 Q.size--; return true; } /*获取队头元素的值，用x返回*/ bool GetHead(SqQueue Q, int &x){ if(Q.size == 0) //队空则报错 return false; x = Q.data[Q.front]; return true; } int main(){ int ret; //用来获取返回值 SqQueue Q; InitQueue(Q); EnQueue(Q,1); EnQueue(Q,2); EnQueue(Q,3); GetHead(Q,ret); printf("QueueHead is:%d\n"); DeQueue(Q,ret); GetHead(Q,ret); printf("QueueHead is:%d\n"); return 0; }

方案三(tag)：

/***判断队满方法:用tag记录当前的插入(tag=1)和删除(tag=0)操作****/ /********即：(Q.front == Q.rear && tag == 1)表示队满************/ #include<stdio.h> /*队列定义*/ #define Maxsize 10 typedef struct{ int data[Maxsize]; //静态数组存放队列元素 int front,rear; //队头指针和队尾指针 int tag; //队列当前操作 }SqQueue; /*初始化队列*/ void InitQueue(SqQueue &Q){ Q.front = Q.rear; //初始时，队头队尾指针指向0 Q.tag = 0; } /*入队操作*/ bool EnQueue(SqQueue &Q, int x){ if(Q.front == Q.rear && Q.tag == 1) //队满则报错 return false; Q.data[Q.rear] = x; //新元素插入队尾 Q.rear = (Q.rear+1)%Maxsize; //队尾指针加一取模 Q.tag = 1; return true; } /*出队操作*/ bool DeQueue(SqQueue &Q, int &x){ if(Q.front == Q.rear && Q.tag == 0) //队空则报错 return false; x = Q.data[Q.front]; Q.front = (Q.front+1)%Maxsize; //队头指针后移 Q.tag = 0; return true; } /*获取队头元素的值，用x返回*/ bool GetHead(SqQueue Q, int &x){ if(Q.front == Q.rear && Q.tag == 0) //队空则报错 return false; x = Q.data[Q.front]; return true; } int main(){ int ret; //用来获取返回值 SqQueue Q; InitQueue(Q); EnQueue(Q,1); EnQueue(Q,2); EnQueue(Q,3); GetHead(Q,ret); printf("QueueHead is:%d\n"); DeQueue(Q,ret); GetHead(Q,ret); printf("QueueHead is:%d\n"); return 0; }

二、定义队尾指针指向队尾元素 方案一（牺牲1个空间）：

/***判断队满条件：队尾指针的再下一个位置是队头****/ /***即：(Q.rear+1)%Maxsize == Q.front。***********/ /***代价：牺牲一个存储单元.***********************/ #include<stdio.h> /*队列定义*/ #define Maxsize 10 typedef struct{ int data[Maxsize]; //静态数组存放队列元素 int front,rear; //队头指针和队尾指针 }SqQueue; /*初始化队列*/ void InitQueue(SqQueue &Q){ Q.front = 0; //初始时，队头指针指向0 Q.rear = Maxsize-1;//初始时，队尾指针指向Maxsize-1 } /*入队操作*/ bool EnQueue(SqQueue &Q, int x){ if((Q.rear+2)%Maxsize == Q.front) //队满则报错 return false; Q.rear = (Q.rear+1)%Maxsize; Q.data[Q.rear] = x; //队尾指针加一取模,再插入新元素 return true; } /*出队操作*/ bool DeQueue(SqQueue &Q, int &x){ if((Q.rear+1)%Maxsize == Q.front) //队空则报错 return false; x = Q.data[Q.front]; Q.front = (Q.front+1)%Maxsize; //队头指针后移 return true; } /*获取队头元素的值，用x返回*/ bool GetHead(SqQueue Q, int &x){ if((Q.rear+1)%Maxsize == Q.front) //队空则报错 return false; x = Q.data[Q.front]; return true; } int main(){ int ret; //用来获取返回值 SqQueue Q; InitQueue(Q); EnQueue(Q,1); EnQueue(Q,5); GetHead(Q,ret); printf("QueueHead is:%d\n",ret); DeQueue(Q,ret); GetHead(Q,ret); printf("QueueHead is:%d\n",ret); return 0; }

方案二（size）：

/***判断队满方法:用size记录当前队列长度****/ /***即：Q.size == Maxsize表示队满************/ #include<stdio.h> /*队列定义*/ #define Maxsize 10 typedef struct{ int data[Maxsize]; //静态数组存放队列元素 int front,rear; //队头指针和队尾指针 int size; //队列当前长度 }SqQueue; /*初始化队列*/ void InitQueue(SqQueue &Q){ Q.front = 0; //初始时，队头指针指向0 Q.rear = Maxsize-1;//初始时，队头指针指向Maxsize-1 Q.size = 0; } /*入队操作*/ bool EnQueue(SqQueue &Q, int x){ if(Q.size == Maxsize) //队满则报错 return false; Q.rear = (Q.rear+1)%Maxsize; //队尾指针加一取模,再将新元素插入队尾 Q.data[Q.rear] = x; Q.size++; return true; } /*出队操作*/ bool DeQueue(SqQueue &Q, int &x){ if(Q.size == 0) //队空则报错 return false; x = Q.data[Q.front]; Q.front = (Q.front+1)%Maxsize; //队头指针后移 Q.size--; return true; } /*获取队头元素的值，用x返回*/ bool GetHead(SqQueue Q, int &x){ if(Q.size == 0) //队空则报错 return false; x = Q.data[Q.front]; return true; } int main(){ int ret; //用来获取返回值 SqQueue Q; InitQueue(Q); EnQueue(Q,1); EnQueue(Q,2); EnQueue(Q,3); GetHead(Q,ret); printf("QueueHead is:%d\n"); DeQueue(Q,ret); GetHead(Q,ret); printf("QueueHead is:%d\n"); return 0; }

方案三(tag)：

/***判断队满方法:用tag记录当前的插入(tag=1)和删除(tag=0)操作****/ /********即：(Q.front == Q.rear && tag == 1)表示队满************/ #include<stdio.h> /*队列定义*/ #define Maxsize 10 typedef struct{ int data[Maxsize]; //静态数组存放队列元素 int front,rear; //队头指针和队尾指针 int tag; //队列当前操作 }SqQueue; /*初始化队列*/ void InitQueue(SqQueue &Q){ Q.front = 0; //初始时队头指针指向0 Q.rear = Maxsize-1;//初始时队尾指针指向Maxsize-1 Q.tag = 0; } /*入队操作*/ bool EnQueue(SqQueue &Q, int x){ if(Q.front == (Q.rear+1)%Maxsize && Q.tag == 1) //队满则报错 return false; Q.rear = (Q.rear+1)%Maxsize; //队尾指针加一取模 Q.data[Q.rear] = x; //新元素插入队尾 Q.tag = 1; return true; } /*出队操作*/ bool DeQueue(SqQueue &Q, int &x){ if(Q.front == (Q.rear+1)%Maxsize && Q.tag == 0) //队空则报错 return false; x = Q.data[Q.front]; Q.front = (Q.front+1)%Maxsize; //队头指针后移 Q.tag = 0; return true; } /*获取队头元素的值，用x返回*/ bool GetHead(SqQueue Q, int &x){ if(Q.front == Q.rear && Q.tag == 0) //队空则报错 return false; x = Q.data[Q.front]; return true; } int main(){ int ret; //用来获取返回值 SqQueue Q; InitQueue(Q); EnQueue(Q,1); EnQueue(Q,2); EnQueue(Q,3); GetHead(Q,ret); printf("QueueHead is:%d\n"); DeQueue(Q,ret); GetHead(Q,ret); printf("QueueHead is:%d\n"); return 0; }