赞
踩
一、循环队列的定义
二、循环队列的实现
三、循环队列的基本操作
在数据结构中,队列(Queue)是一种常见的线性数据结构,遵循先进先出(First In First Out,FIFO)的原则。循环队列是队列的一种变体,它可以更高效地利用存储空间,并解决了普通队列可能出现的假溢出问题。本篇博客将详细介绍循环队列的定义、实现和基本操作。
循环队列是通过数组或链表实现的一种队列,它将队列的首尾相连,形成一个循环。在循环队列中,队尾指针(rear)可能在队列的前面,队头指针(front)可能在队列的后面。当队列为空时,front和rear指向同一个位置。当队列满时,front和rear之间有一个空位。
我们可以通过数组来实现循环队列。为了更好地利用存储空间,通常会预留一个位置来区分队列是空还是满。具体来说,我们需要定义一个固定大小的数组和两个指针front和rear来表示队头和队尾。
typedef int TypeData;
typedef struct Node{
TypeData *data;
int front;
int rear;
int len;
}Queue,*Pqueue;
Pqueue init_queue(Pqueue *queue, int m){
*queue = (Pqueue)malloc(sizeof(Queue));
if(*queue == NULL){
return NULL;
}
(*queue)->data = (TypeData *)malloc(sizeof(Queue) * m);
(*queue)->front = (*queue)->rear= 0;
(*queue)->len = m;
return *queue;
}
int isEmpty(Pqueue queue){
return queue->front == queue->rear;
}
int full(Pqueue queue){
return (queue->rear+1) % (queue->len) == (queue->front);
}
int queue_en(Pqueue queue, TypeData value){
if(full(queue)){
return -1;
}
queue->data[queue->rear] = value;
queue->rear = (queue->rear+ 1) % (queue->len);
return 0;
}
TypeData queue_de(Pqueue queue){
if(isEmpty(queue)){
return -1;
}
TypeData temp = queue->data[queue->front];
queue->front = (queue->front + 1) % (queue->len);
return temp;
}
int get_length(Pqueue queue){
#if 0
int a = queue->rear - queue->front;
if(a >= 0){
return a;
}else{
return (a + queue->len) % (queue->len);
}
#else
return (queue->rear - queue->front + queue->len) % queue->len;
#endif
}
void show(Pqueue queue){
for(int i = queue->front; i != queue->rear; i = (i + 1) % queue->len){
printf("%d ",queue->data[i]);
}
printf("\n");
}
循环队列常用于解决生产者-消费者问题,以及在需要定期缓存数据时。它还在计算机操作系统的进程调度中得到广泛应用,用于管理就绪队列。循环队列的高效性和简单性使其成为许多问题的理想解决方案。
①seqqueue.h
#ifndef _SEQQUEUE_H_ #define _SEQQUEUE_H_ #include <stdio.h> #include <stdlib.h> typedef int TypeData; typedef struct Node{ TypeData *data; int front; int tail; int len; }Queue,*Pqueue; Pqueue init_queue(Pqueue *queue, int m); int isEmpty(Pqueue queue); int full(Pqueue queue); int get_length(Pqueue queue); int queue_en(Pqueue queue, TypeData value); TypeData queue_de(Pqueue queue); void show(Pqueue queue); #endif
②seqqueue.c
#include "seqqueue.h" Pqueue init_queue(Pqueue *queue, int m){ *queue = (Pqueue)malloc(sizeof(Queue)); if(*queue == NULL){ return NULL; } (*queue)->data = (TypeData *)malloc(sizeof(Queue) * m); (*queue)->front = (*queue)->tail = 0; (*queue)->len = m; return *queue; } int isEmpty(Pqueue queue){ return queue->front == queue->tail; } int full(Pqueue queue){ return (queue->tail+1) % (queue->len) == (queue->front); } int get_length(Pqueue queue){ #if 0 int a = queue->tail - queue->front; if(a >= 0){ return a; }else{ return (a + queue->len) % (queue->len); } #else return (queue->tail - queue->front + queue->len) % queue->len; #endif } int queue_en(Pqueue queue, TypeData value){ if(full(queue)){ return -1; } queue->data[queue->tail] = value; queue->tail = (queue->tail + 1) % (queue->len); return 0; } TypeData queue_de(Pqueue queue){ if(isEmpty(queue)){ return -1; } TypeData temp = queue->data[queue->front]; queue->front = (queue->front + 1) % (queue->len); return temp; } void show(Pqueue queue){ for(int i = queue->front; i != queue->tail; i = (i + 1) % queue->len){ printf("%d ",queue->data[i]); } printf("\n"); }
③seqqueue_main.c
#include "seqqueue.h" #include "seqqueue.c" #include <unistd.h> int main(int argc, char *argv[]) { Pqueue queue; init_queue(&queue, 10); printf("入队:"); queue_en(queue, 20); queue_en(queue, 55); queue_en(queue, 60); queue_en(queue, 99); queue_en(queue, 22); queue_en(queue, 66); queue_en(queue, 100); show(queue); printf("出队:"); queue_de(queue); show(queue); printf("队内还有%d个元素",get_length(queue)); printf("\n"); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。