数据结构笔记-队列

队列

顺序队列循环顺序队列链队列

顺序队列

函数操作【入队，出队，元素个数，判队空，判队满】 #define maxlen 100 typedef struct { datatype data[maxlen]; //存储数组 int front; //数组索引—对首指针 int rear; //对尾脂针 }SeqQuene; q.rear++; q.data[q.rear] = x; q.front++; x= q.data[q.front]; //n 为个数 n = q.rear - q.front; q.front == q.rear; n == maxlen;

顺序队列

函数操作【初始化，判队空，判队满，入队，出队】 typedef struct { datatype data[maxlen]; int front,rear; int n; }CycleSeQuene; void InitSeQueue(CycleSeQueue &q) { q.front = maxlen-1;//数组存储位置在【0，maxlen-1】，将指针指向数组索引0的前一位表示队列为空； q.rear = maxlen-1; } int IsEmpty(CycleSeQueue q) { if(q.rear == q.front ) return 1; else return 0; } int IsFull(CycleSeQueue q) { if( ( (q.rear+1) % maxlen). == q.front) return 1; else return 0; } int InQueue(CycleSeQueue &q,datatype x) { if( IsFull(q)) {court<<“queue is full”; return 0;} else { q.rear = (q.rear + 1) % maxlen; q.data[q.rear] = x; return 1; } } int OutQueue (CycleSeQueue &q,datatypr &x) { if( IsEmpty(q) ) {court<<“queue is empty”;return 0;} else { q.front = (q.front + 1) % maxlen; x = q.data[q.front]; return 1; } }

链队列

函数操作【初始化，入队，出队，读队头元素，显示全部元素】 typedef struct Linkqueuenode { datatype data; struct Linkqueuenode * next; }linkqueuenode; typedef struct { linkqueuenode *front,*rear; }linkqueue; void InitLinkQueue (linkqueue &q) { q.front = NULL; q.rear = NULL: } void InQueue(link queue &q,datatype x) { linkqueuebode *p = new linkqueuenode; p->data = x; p->next = NULL; if(NULL == q.front ) q.front = p; else q.rear->next = p; q.rear = p } void OutQueue(linkqueue &q,datatype &x) { linkqueuendoe *p = q.front; if(NULL == q.front) return 0; else { q.front = p->next; if(NULL == q.front) q.rear = NULL; x = p->data; delete p; return 1; } } int ReadFront (linknode q , datatype &x) { if(NULL == q.front) return 0; else { x = q.front->data; return 1; } } void ShowQueue(linkqueue q) { linkqueuenode * p = q.front; if(NULL == q.front) court<<“queue is empty”; else while(p) { court<< p->data; p = p->next; } }

队列的应用

优先队列双队列