c语言实现循环队列

　

循环队列

• 接口参考严蔚敏老师的数据结构
• 难点
  • 开始队列为空时front = rear = 0，队列满时如果也是front = rear，则很难判断空满两个状态，因此队列空出一个空间专门用来放尾指针。
  • 循环队列如何达到循环状态，接口函数实现的过程最好画图来形象的展示，实现后一个个调试，因为一不小心就可能出错误。
• 实现环境：linux

下面是实现过程

数据结构：

typedef struct {
	Item *base;
	int front;
	int rear;
}queue;

queue.h

#ifndef QUEUE_H_
#define QUEUE_H_
#include <stdbool.h>

#define MAXQSIZE 6
#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef int Item;

typedef struct {
	Item *base;
	int front;
	int rear;
}Queue;

/*initialize the queue*/
void InitQueue(Queue *q);

/*return the length of the queue*/
unsigned int QueueLength(Queue q);

/*Destroy the queue*/
void DestroyQueue(Queue *q);

/*determine if the queue is empty*/
bool IsEmpty(Queue q);

/*determine if the queue is full*/
bool IsFull(Queue q);

/*return the head elem of the queue*/
Item Top(Queue q);

/*return the back elem of the queue*/
Item Back(Queue q);

/*enqueue, insert the rear*/
bool EnQueue(Queue *q, Item e);

/*dequeue, pop the front*/
bool DeQueue(Queue *q);

/*print the queue*/
void PrintQueue(Queue q);

#endif

queue.c

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

void InitQueue(Queue *q) {
	q->base = (Item*)malloc(MAXQSIZE * sizeof(Item));
	if (q->base == NULL)
		exit(OVERFLOW);
	q->front = 0;
	q->rear = 0;
}

/*return the length of the queue*/
unsigned int QueueLength(Queue q) {
	return (q.rear - q.front + MAXQSIZE) % MAXQSIZE;
}
/*Destroy the queue*/
void DestroyQueue(Queue *q) {
	q->base = NULL;
	q->rear = 0;
	q->front = 0;
	free(q->base);
}

/*determine if the queue is empty*/
bool IsEmpty(Queue q) {
	return q.rear == q.front;
}

bool IsFull(Queue q) {
	return (q.rear + 1) % MAXQSIZE == q.front;
}

/*return the head elem of the queue*/
Item Top(Queue q) {
	return q.base[q.front];
}

/*return the back elem of the queue*/
Item Back(Queue q) {
	return q.base[(q.rear - 1 + MAXQSIZE) % MAXQSIZE];
}

/*enqueue, insert the rear*/
bool EnQueue(Queue *q, Item e) {
	if (IsFull(*q))
		return ERROR;
	q->base[q->rear] = e;
	q->rear = (q->rear + 1) % MAXQSIZE;
	
	return OK;
}
/*dequeue, pop the front*/
bool DeQueue(Queue *q) {
	if(IsEmpty(*q))
		return ERROR;
	q->front = (q->front + 1) % MAXQSIZE;
	return OK;
}

/*print the queue*/
void PrintQueue(Queue q) {
	int i, j;
	for (i = 0, j = q.front; i < QueueLength(q); i++, j = (j + 1) % MAXQSIZE) {
		printf("%d\n",q.base[j]);
	}
}

main.c

#include "queue.h"
#include <stdio.h>
int main () {
	Queue q;
	InitQueue(&q);
	EnQueue(&q, 1);
	EnQueue(&q, 2);
	EnQueue(&q, 3);
        EnQueue(&q, 4);
	EnQueue(&q, 5);
	if (IsFull(q))
		printf("hihi\n");
	DeQueue(&q);
	printf("%d\n%d\n", q.front, q.rear);
        EnQueue(&q, 6);
	printf("%d\n", Top(q));
	//printf("%d\n", q.base[0]);
	printf("%d\n", Back(q));
	PrintQueue(q);
	DestroyQueue(&q);	
}

makefile

object = main.o queue.o

test : $(object)
	gcc -g -Wall -o test $(object)

main.o : queue.h
queue.o : queue.h

.PHONY : clean
clean :
	rm -rf *.o

相关阅读

新浪博客账号快速收录技巧，实现百度霸屏效果！

今天给大家分享一篇如何利用SEO技术快速获取博客关键词排名的技巧！主要有三个方面： 博客SEO 第一：黏住粉丝 用户浏览我们的博客，无非

为什么编程语言以及数据库要从1970年1月1日开始计算时

今天在看Python API时，看到time模块: The epoch is the point where the time starts. On January 1st of that year, at 0 hours

C语言的字符串数组

在C语言当中，字符串数组可以使用： char a[] [10]; 或者 char *a[]; 表示 第一种表示方式固定了每个字符串的最大大小。第二种

循环队列 基本概念

循环队列是 队列的一种特殊形式。首先介绍队列，然后引申出循环队列。 队列又称为“先进先出”(FIFO)线性表 限定插入操作只能在队

实现数据权限控制的一种方法

在企业管理系统中，常常有这样的要求： 1. 用户一般只能查看自己部门的数据 2. 可以设置用户可以查看哪些部门的数据 这种权限的控