今天学了队列,就本身写了一下代码,队列有顺序队列和循环队列以及链队列,因为顺序队列存在“假上溢”现象,因此基本上不用,那么主要研究循环队列和链队列,循环队列是采用数组实现的,其中分别由front 和rear指示队列的头和尾,插入和删除分别只能在队尾和队首进行,这样才能实现数据先进先出的数据结构,而栈是数据现先进后出的数据结构,与队列恰好相反,因此栈只能在栈顶进行删除与插入,这样才能实现数据先进后出,回到循环队列因为当队列空或者满时,front都与rear相等,因此就存在一个空与满的判断问题,也正是存在这个问题才有下面两种实现方法,一种是用一个type_queue类型空间来换取这个问题的解决,另外一个办法是用一个整数记录队列数据的个数,这样天然就能判断队列空或者满了,count=0为空,count=Max为满,下面分别给出相应代码:node
//循环队列 //相应操做为(进队列)Push(),出队列pop(),取队首元素Get_top(),清空队列clear_queue(),判空Is_empty(),判满Is_full() //第一种方式(利用空的结点来制造判断full的条件) //#include <iostream> #include <stdio.h> #include <stdlib.h> //#include <string.h> //using namespace std; #define Max 100 //结点个数(最大)实际存储最大数量为99(牺牲一个type_queue类型的空间) typedef int type_queue; typedef struct { type_queue s[Max]; int front; int rear; }Queue; bool Is_empty(Queue *p){ return p->front==p->rear; } bool Is_full(Queue *p){ return (p->rear+1)%Max==p->front; } void Push(Queue *p,type_queue x){ if(Is_full(p)){ printf("overflow\n"); return ; } p->s[p->rear]=x; p->rear=(p->rear+1)%Max; } type_queue Pop(Queue *p){ if(Is_empty(p)){ printf("belowflow\n"); return -1; } type_queue x; x=p->s[p->front]; p->front=(p->front+1)%Max; return x; } type_queue Get_top(Queue *p){ if(Is_empty(p)){ printf("Queue is empty\n"); return -1; } return p->s[p->front]; } void Init_queue(Queue *p){ p->front=p->rear=0; //随便为0-Max-1中的一个数值便可 } void Clear_queue(Queue *p){ p->front=p->rear=0;//随便为0-Max-1中的一个数值便可 }
//第二种方法(用一个整数count记录队列中的结点数) #include <stdio.h> #include <stdlib.h> #define Max 100 //实际上能够存储100各数据 typedef int type_queue; typedef struct { type_queue s[Max]; int front; int rear; int count; }Queue; bool Is_empty(Queue *p){ return p->count==0; } bool Is_full(Queue *p){ return p->count==Max; } void Push(Queue *p,type_queue x){ if(Is_full(p)){ printf("overflow\n"); return ; } p->s[p->rear]=x; p->rear=(p->rear+1)%Max; p->count++; } type_queue Pop(Queue *p){ if(Is_empty(p)){ printf("belowflow\n"); return -1; } type_queue x; x=p->s[p->front]; p->front=(p->front+1)%Max; p->count--; return x; } type_queue Get_top(Queue *p){ if(Is_empty(p)){ printf("Queue is empty\n"); return -1; } return p->s[p->front]; } void Init_queue(Queue *p){ p->front=p->rear=0;//随便为0-Max-1中的一个数值便可 p->count=0; } void Clear_queue(Queue *p){ p->front=p->rear=0;//随便为0-Max-1中的一个数值便可 p->count=0; } int main() { Queue q; Init_queue(&q); for(int i=0;i<100;i++) Push(&q,i); while(!Is_empty(&q)) printf("%d ",Pop(&q)); for(int i=0;i<100;i++) Push(&q,i); while(!Is_empty(&q)) printf("%d ",Pop(&q)); for(int i=0;i<100;i++) Push(&q,i); while(!Is_empty(&q)) printf("%d ",Pop(&q)); Clear_queue(&q); for(int i=0;i<100;i++) Push(&q,i); while(!Is_empty(&q)) printf("%d ",Pop(&q)); for(int i=0;i<100;i++) Push(&q,i); while(!Is_empty(&q)) printf("%d ",Pop(&q)); return 0; }
//链队列 //尾插法建链队列 //无上限,提供操做:判空Is_empty(),插入Push(),删除Pop(),清空Clear_queue(),取队首元素Get_top(),初始化队列Init_queue(); #include <stdio.h> #include <stdlib.h> typedef int type_queue; typedef struct node { type_queue x; struct node *next; }Node; typedef struct { Node *front; Node *rear; }Queue; bool Is_empty(Queue *p){ if(p->front==NULL && p->rear==NULL) return true; return false; } void Push(Queue *p,type_queue x){ Node *s=(Node*)malloc(sizeof(Node)); s->x=x; s->next=NULL; if(Is_empty(p)){ p->rear=p->front=s; return ; } p->rear->next=s; p->rear=s; } type_queue Pop(Queue *p){ if(Is_empty(p)){ printf("below flow\n"); return -1; } type_queue x=p->front->x; if(p->front->next==NULL){ free(p->front); p->front=p->rear=NULL; return x; } Node *s=p->front; p->front=s->next; free(s); return x; } type_queue Get_top(Queue *p){ if(Is_empty(p)){ printf("the Queue is empty\n"); return -1; } return p->front->x; } void Init_queue(Queue *p){ p->front=p->rear=NULL; } void Clear_queue(Queue *p){ while(!Is_empty(p)) Pop(p); } int main() { Queue q; Init_queue(&q); for(int i=0;i<101;i++) Push(&q,i); while(!Is_empty(&q)) printf("%d ",Pop(&q)); for(int i=0;i<101;i++) Push(&q,i); while(!Is_empty(&q)) printf("%d ",Pop(&q)); for(int i=0;i<101;i++) Push(&q,i); while(!Is_empty(&q)) printf("%d ",Pop(&q)); Clear_queue(&q); for(int i=0;i<101;i++) Push(&q,i); while(!Is_empty(&q)) printf("%d ",Pop(&q)); for(int i=0;i<101;i++) Push(&q,i); while(!Is_empty(&q)) printf("%d ",Pop(&q)); return 0; }