队列是一种只允许在队尾插入元素,在队头插入元素的一种数据结构。就比如我们生活中的排队。队列最主要的是判断队空或者队满。队列的静态方式实现,利用数组设置一个循环的队列。代码如下:
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
/*
判断队列空满:
方案一:代码(浪费一个存储空间,用来判断队满和队空)
方案二:增加一个变量表示队列长度(初始化为0),每增加一个元素长度加一,每删除一个元素
减一。最后长度为MaxSize的队满,长度为0的队空(不浪费)
方案三:增加一个判断型变量表示最近一次插入(0)或者删除的操作 (1),每次增加元素都使
变量置为0,删除元素都使变量置为1。这样结合队头和队尾指针指向同一个地方就可以判断(不浪费)
*/
//静态方式定义队列
typedef struct {
int data[MaxSize];//用静态数组存放元素
int front,rear;//队头指针和队尾指针
}SqQueue;
//静态方式初始化队列(队头队尾都指向0)
void InitQueue(SqQueue &Q){
Q.front = 0;
Q.rear = 0;
}
//静态方式判断是否为空队列
bool isEmpty(SqQueue Q){
if(Q.front==Q.rear){
return true;
}else{
return false;
}
}
//静态方式入队
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;//队尾+1取模(形成循环结构队列)
return true;
}
//静态方式入队
bool DeQueue(SqQueue &Q,int &x){
if(Q.front==Q.rear){//队空报错
return false;
}
x = Q.data[Q.rear];
Q.front = (Q.front+1)%MaxSize;//队头+1取模(形成循环结构队列)
return true;
}
//静态方式获得队头元素
bool GetQueue(SqQueue &Q,int &x){
if(Q.front==Q.rear){//队空报错
return false;
}
x = Q.data[Q.rear];
return true;
}
//队列元素个数计算((rear+MaxSize-front)%MaxSize)
int main(int argc, char** argv) {
SqQueue Q;
InitQueue(Q);
return 0;
}