04 数据结构之队列

循环队列

/* squence_queue.h */
#ifndef _SQUENCE_QUEUE_H_
#define _SQUENCE_QUEUE_H_


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

#define QUEUE_SIZE 128
#define DEBUG(msg) \
	printf("--%s--, %s", __func__, msg)

typedef int data_t;
typedef struct {
	data_t arr[QUEUE_SIZE];
	int front, rear;
}squence_queue_t;

squence_queue_t *SqQueue_Create(void);
int SqQueue_Free(squence_queue_t *q);
int SqQueue_Clear(squence_queue_t *q);
int SqQueue_Entry(squence_queue_t *q, data_t value);
data_t SqQueue_Departure(squence_queue_t *q);
int SqQueue_Isempty(squence_queue_t *q);
int SqQueue_Isfull(squence_queue_t *q);


#endif

/* squence_queue.c */
#include "squence_queue.h"


/*brife: create a cycle queue
 *para: none
 *ret: heap zone addrees
 * */
squence_queue_t *SqQueue_Create(void)
{
	squence_queue_t *q = NULL;

	q = (squence_queue_t *)malloc(sizeof(squence_queue_t));
	if(q == NULL) {
		DEBUG("malloc failed\n");	
		return NULL;
	}

	memset(q->arr, 0, sizeof(data_t) * QUEUE_SIZE);
	q->front = 0;
	q->rear = 0;

	return q;
}


/*brife: free a cycle in heap space
 *para: cycle queue pointer
 *ret: 0 succsess  other failed
 * */
int SqQueue_Free(squence_queue_t *q)
{
	if(q == NULL) {
		DEBUG("param is invalid!\n");	
		return -1;
	}

	free(q);
	q = NULL;
	
	return 0;
}

/*brife: clear cycle queue content
 * 
 * */
int SqQueue_Clear(squence_queue_t *q)
{
	if(q == NULL) {
		DEBUG("param is invalid!\n");	
		return -1;
	}

	memset(q->arr, 0, sizeof(data_t) * QUEUE_SIZE);
	q->front = q->rear = 0;

	return 0;
}

/*brife: cycle queue entry operator
 *
 * */
int SqQueue_Entry(squence_queue_t *q, data_t value)
{
	if(q == NULL) {
		DEBUG("param is invalid!\n");	
		return -1;
	}

	if((q->rear + 1) % QUEUE_SIZE == q->front) {
		DEBUG("queue is full, entry failed!\n");	
		return -1;
	}

	q->arr[q->rear] = value;
	q->rear = (q->rear + 1) % QUEUE_SIZE;

	return 0;
}


/*brife: cycle queue departure operator
 *
 * */
data_t SqQueue_Departure(squence_queue_t *q)
{
	if(q == NULL) {
		DEBUG("param is invalid!\n");	
		return -1;
	}

	data_t ret;
	ret = q->arr[q->front];
	q->front = (q->front + 1) % QUEUE_SIZE;

	return ret;
}


/*brife: judge cycle queue is empty?
 *ret: 1---empty
 * 	   0---no empty	
 * */
int SqQueue_Isempty(squence_queue_t *q)
{
	if(q == NULL) {
		DEBUG("param is invalid!\n");	
		return -1;
	}

	return (q->front == q->rear ? 1 : 0);
}

/*brife: judge a cycle queue is full?
 *ret: 1---full
 *     0---no full
 * */
int SqQueue_Isfull(squence_queue_t *q)
{
	if(q == NULL) {
		DEBUG("param is invalid!\n");	
		return -1;
	}

	return ((q->rear + 1) % QUEUE_SIZE == q->front ? 1 : 0);
}

链式队列

/* link_queue.h */
#ifndef _LINK_QUEUE_H_
#define _LINK_QUEUE_H_

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

#define DEBUG(msg) \
	printf("--%s--, --%s--\n", __func__, msg);

typedef int data_t;
typedef struct link_queue {
	data_t data;
	struct link_queue *next;
}queue_t;
typedef struct {
	queue_t *head;
	queue_t *rear;
}linkqueue_t;

linkqueue_t *link_queue_create();
int link_queue_free(linkqueue_t *lq);
int link_queue_entry(linkqueue_t *lq, data_t value);
data_t link_queue_departure(linkqueue_t *lq);
int link_queue_clear(linkqueue_t *lq);
int link_queue_isempty(linkqueue_t *lq);

#endif

/* link_queue.c */
#include "link_queue.h"


linkqueue_t *link_queue_create()
{
	linkqueue_t *p = NULL;

	p = (linkqueue_t *)malloc(sizeof(linkqueue_t));
	if(p == NULL) {
		DEBUG("malloc failed\n");
		return NULL;
	}

	p->head = p->rear = (queue_t *)malloc(sizeof(queue_t));
	if(p->head == NULL) {
		DEBUG("malloc failed\n");
		return NULL;
	}

	p->head->data = 0;
	p->head->next = NULL;


	return p;
}


int link_queue_free(linkqueue_t *lq)
{
	if(lq == NULL) {
		DEBUG("param is invalid\n");
		return -1;
	}

	queue_t *p = lq->head;

	while(lq->head != NULL) {
		p = lq->head;
		lq->head = lq->head->next;
		free(p);
	}

	free(lq);
	lq = NULL;

	return 0;

}


int link_queue_entry(linkqueue_t *lq, data_t value)
{
	if(lq == NULL) {
		DEBUG("param is invalid\n");
		return -1;
	}

	queue_t *p = (queue_t *)malloc(sizeof(queue_t));
	if(p == NULL) {
		DEBUG("new node malloc failed\n");
		return -1;
	}

	p->data = value;
	p->next = NULL;

	lq->rear->next = p;
	lq->rear = lq->rear->next;

	return 0;
	
}

data_t link_queue_departure(linkqueue_t *lq)
{
	if(lq == NULL) {
		DEBUG("param is invalid\n");
		return -1;
	}

	data_t ret = 0;
	queue_t *p;

	ret = lq->head->next->data;
	p = lq->head;
	lq->head = lq->head->next;

	free(p);

	return ret;
}


int link_queue_clear(linkqueue_t *lq)
{
	if(lq == NULL) {
		DEBUG("param is invalid\n");
		return -1;
	}

	queue_t *p;

	while(lq->head->next != NULL) {
		p = lq->head->next;
		lq->head = p->next;
		free(p);
		p = NULL;
	}

	return 0;
}


int link_queue_isempty(linkqueue_t *lq)
{
	if(lq == NULL) {
		DEBUG("param is invalid\n");
		return -1;
	}

	return (lq->head == lq->rear ? 1 : 0);
}