队列(循环队列)的顺序存储实现

2019/7/24 17:06:59 人评论 次浏览 分类:学习教程

//
//

/************************************队列的顺序存储实现********************************************/
/**
 * 1、队列:一端进,另一端出;队列由两个参数决定,front(头),rear(尾);
	头指针指向头一个元素,尾指针指向指向最后一个元素的下一存储单元;若数组长度为n,当元素个数为n-1时就认为队列已满。r指向最后一个空的元素空间。

	出队:头指针往上移动,

	入队:尾指针向上移动,故:静态队列只能是循环队列,不然出队的元素占用的空间
	永远无法重复利用。

	1):队列的初始化:front,rear的值都是零、
	2):队列非空:front代表的是队列的第一个元素,rear代表的是队列的最后一个元素的下个存储单元
	3)  :队列空:front和rear的值相等,但不一定是零
	4):动态队列:链表实现
	     静态队列:数组实现

2、循环队列:
	出队:f = (f+1) % 数组长度
	入队:r = (r+1) % 数组长度

		+++++++++++++++++++++
		+		    +
		+		    +<----r
		+		    +
		+++++++++++++++++++++
		+		    +
		+	c	    +
		+		    +
		+++++++++++++++++++++
		+		    +
		+	b	    +
		+		    +
		+++++++++++++++++++++
		+		    +
 f ---> +	 a	    +
		+		    +
		+++++++++++++++++++++

	如何判断循环队列是否为空: 如果f == r 就一定为空
	如何判断队列已满:
		1)增加一个标志n记录队列元素的个数,当n = 数组长度-1时,就满了。
		2)if((r+1)%arr.length == f){
			队列已满
		}
		通常使用第二种
 * **/


#include <stdio.h>
#include <stdlib.h>

/**
 * 循环队列
 */
typedef  struct array_queue{
    int * data; //数组
    int limit; //队列容量
    int size;//队列中元素个数
    int head;//队首
    int tail;//队尾
}ArrayQueue;


/**
 * 创建队列
 * @param limit
 * @return
 */
static ArrayQueue * createArrayQueue(int limit){
    ArrayQueue * queue = (ArrayQueue *)calloc(1, sizeof(ArrayQueue));
    int * data = (int *)calloc(limit + 1, sizeof(int)); //因为队尾指向最后一个元素的下一个位置,所以数组大小为limit+1
    queue->data = data;
    queue->size = 0;
    queue->limit = limit;
    queue->head = 0;
    queue->tail = 0;
}

/**
 * 队列是否满了
 * @param queue
 * @return
 */
static int isFull(ArrayQueue * queue){
    if((queue->tail + 1) % (queue->limit+1) == queue->head){
        return 1;
    }
    return 0;
}

/**
 * 是否空
 * @param queue
 * @return
 */
static int isEmpty(ArrayQueue * queue){
    if(queue->head == queue->tail){
        return 1;
    }
    return 0;
}

/**
 * 入队
 * @param queue
 * @param data
 */
static  void enqueue(ArrayQueue *queue, int data){
    if(isFull(queue)){
        printf("queue is full\n");
        return;
    }
    queue->data[queue->tail] = data;
    queue->tail = (queue->tail+1) % (queue->limit+1);
    queue->size++;
}

/**
 * 出队
 * @param queue
 * @return
 */
static int dequeue(ArrayQueue * queue){
    if(isEmpty(queue)){
        printf("queue is empty\n");
        return -1;
    }
    int data = queue->head;
    queue->head = (queue->head+1) % (queue->limit+1);
    return data;
}
void freeQueue(ArrayQueue * queue){
    free(queue->data);
    free(queue);
}

int main(){
    ArrayQueue * queue = createArrayQueue(10);
    for(int i = 0; i < 12; i++){
        enqueue(queue, i);
    }
    for(int i = 0; i < 12; i++){
        printf("%d\n", dequeue(queue));
    }
    freeQueue(queue);
    return 0;
}

 

相关资讯

  • 那些我们不愿意承认的事

    很久没有见的老朋友,准确的说应该是很久没有见过的老师,一个比我大两岁的老师,我上初中的时候他从高中回来教我了一年。后来又回去上高中,我上高中的时候他上大学,现在我刚大学毕业他创办了公司。昨日一见依然如故,他还是热爱销售,而我却成了纯粹的技术人员。 看到他…

    2015/6/22 13:12:47

学习教程

共有访客发表了评论 网友评论

验证码: 看不清楚?

    立即查看