队列queue的实现

顺序表实现

##list.c
#include <stdio.h>
#include <stdlib.h>
typedef int data_t;

typedef struct list{
	data_t *data; //保存数据的空间
	int size;   //容器能保存的元素个数
	int last; //保存最后一个有效元素的下标
}list_t;
/*返回创建好的 空顺序表 的地址*/

list_t *creat_list(int size)
{
	list_t *p;
	p = malloc(sizeof(list_t) + (sizeof(data_t) * size));//申请空间
	p->data = (data_t *)(p + 1);
	p->size = size;
	p->last = -1;  //初始化 结构内部相应内容

	return p;
}
/*
 * p： 顺序表的地址
 * index：插入的下标位置
 * data：插入的数据
 *
 * return：成功返回0 ；失败返回-1
 * */
int ins_index_list(list_t *p,int index,const data_t *data)
{
	//1.将插入位置的数据向下移动
	//  1.1 移动最后一个 到下一个位置   data[last + 1] = data[last];
	//  1.2 移动倒数第二个             
	//  1.3 。。。。
	//
	//2.写入数据到对应位置
	//3. last ++
	
	int i;
	if(p->size - 1 == p->last) // 如果容器满 直接退出
		return -1;
	if(index < 0 || index > p->last + 1)
		return -2;

	for(i = p->last;i >= index;i --){
		p->data[i + 1] = p->data[i];
	}

	p->data[index] = *data;
	p->last ++; // (*p).last

	return 0;
}

int del_index_list(list_t *p,int index)
{
	//1.移动删除位置之下的数据
	//   1.1 index + 1 位置的数据到 index
	//   1.2 index + 2              index + 1
	//   ....
	//2.laint main(int argc, const char *argv[])
	
	int i;
	if(-1 == p->last)  //如果为空，则退出
		return -1;
	if(index < 0 || index > p->last)
		return -2;

	for(i = index;i < p->last;i ++){
		p->data[i] = p->data[i + 1];
	}
	p->last --; //p->last // (*p).last
	
	return 0;
}

int get_index_list(list_t *p,int index,data_t *databuf)
{
	if(-1 == p->last)  //如果为空，则退出
		return -1;
	if(index < 0 || index > p->last)
		return -2;

	*databuf = p->data[index];

	return 0;
}

int change_index_list(list_t *p,int index,const data_t *newdata)
{
	if(-1 == p->last)  //如果为空，则退出
		return -1;
	if(index < 0 || index > p->last)
		return -2;

	p->data[index] = *newdata;

	return 0;
}
/*如果为满 返回 真1；非满 返回假0*/
int is_full_list(list_t *p)
{
	return (p->size - 1) == p->last;
}

int is_empty_list(list_t *p)
{
	return -1 == p->last;
}

int locate_list(list_t *p,const data_t *data)
{
	int i;

	if(NULL == p || NULL == data)
		return -2;

	for(i = 0;i <= p->last;i ++){
		if(*data == p->data[i])
			return i;
	}

	return -1;
}

int clean_list(list_t *p)
{
	p->last = -1;
	return 0;
}

int dis_list(list_t *p)
{
	free(p);
	
	return 0;
}

void print_list(list_t *p)
{
	int i;
	for(i = 0;i <= p->last;i ++){// 打印数据集合里的内容
		printf("%d ",p->data[i]);
	}
	printf("\n");
	printf("last:%d\n",p->last);//打印
	//最后一个元素位置
	return ;
}

##list.h
#ifndef __LIST_H__
#define __LIST_H__

typedef int data_t;

typedef struct list{
	data_t *data; //保存数据的空间
	int size;   //容器能保存的元素个数
	int last; //保存最后一个有效元素的下标
}list_t;
extern list_t *creat_list(int size);
extern int ins_index_list(list_t *p,int index,const data_t *data);
extern int del_index_list(list_t *p,int index);
extern int change_index_list(list_t *p,int index,const data_t *newdata);
extern int get_index_list(list_t *p,int index,data_t *databuf);
extern int is_full_list(list_t *p);
extern int is_empty_list(list_t *p);
extern int locate_list(list_t *p,const data_t *data);
extern int clean_list(list_t *p);
extern int dis_list(list_t *p);
extern void print_list(list_t *p);

#endif

##main.c
#include <stdio.h>
#include "list.h"

typedef struct list queue_list_t;

queue_list_t *creat_queue_list(int size)
{
	return creat_list(size);
}

int out_queue_list(queue_list_t *p,data_t *databuf)
{

	get_index_list(p,0,databuf);
	del_index_list(p,0);

	return 0;
}

int in_queue_list(queue_list_t *p,const data_t *data)
{
	ins_index_list(p,p->last + 1,data);

	return 0;
}


int main(int argc, const char *argv[])
{
	queue_list_t *p;
	int i;
	data_t buf;
	p = creat_queue_list(8);


	for(i = 0;i < 6;i ++){
		in_queue_list(p,&i);
	}

	i = 6;
	while(i --){
		buf = -1;
		out_queue_list(p,&buf);
		printf("out:%d\n",buf);
	}

	return 0;
}

链表实现

#include <stdio.h>        
#include <stdlib.h>
//链表队列，尾插头删

typedef int data_t;
typedef struct linkqueue_node{
	data_t data;
	struct linkqueue_node *next;
}linkqueue_node_t;

typedef struct linkqueue{
	linkqueue_node_t *head;
	linkqueue_node_t *tail;
}linkqueue_t;

linkqueue_t *creat_linkqueue_old()
{
	linkqueue_t *p;
	linkqueue_node_t *head;
	head = malloc(sizeof(linkqueue_node_t));

	head->next = NULL;
	
	p = malloc(sizeof(linkqueue_t));
	p->head = head;
	p->tail = head;

	return p;
}

linkqueue_t *creat_linkqueue()
{
	linkqueue_t *p;

	p = malloc(sizeof(linkqueue_t));
	p->head =  malloc(sizeof(linkqueue_node_t));
	p->tail = p->head;
	
	p->head->next = NULL;

	return p;
}

int in_linkqueue(linkqueue_t *p,const data_t *data)
{
	//1.执行链表尾部插入
	linkqueue_node_t *newnode;
	newnode = malloc(sizeof(linkqueue_node_t));
	newnode->data = *data;

	newnode->next = NULL;//p->tail->next; // 

	p->tail->next = newnode;
	//2.记录新的尾结点地址
	p->tail = newnode;

	return 0;
}

int out_linkqueue(linkqueue_t *p,data_t *databuf)
{

	if(NULL == p->head->next)
		return -1;

	//1.执行头部删除，并拷贝数据
	linkqueue_node_t *temp;
	temp = p->head->next;
	p->head->next = temp->next;
	
	*databuf = temp->data;

	free(temp);
	//2.判断 链表是否为空
	//  2.1 如果为空，纠正tail
	if(NULL == p->head->next)
		p->tail = p->head;

	return 0;
}

int get_head_linkqueue(linkqueue_t *p,data_t *databuf)
{
	if(NULL == p->head->next)
		return -1;

	*databuf = p->head->next->data;

	return 0;
}


void print_link(linkqueue_t *p)
{
	linkqueue_node_t *head;
	head = p->head; //注意：p->head 是p指向的堆区上的变量

	while(NULL != head->next){
		head = head->next;
		printf("%d ",head->data);
	}
	printf("\n");

	return ;
}


int main(int argc, const char *argv[])
{

	linkqueue_t *p;
	data_t buf;
	int i;

	p = creat_linkqueue();
	for(i = 0;i < 10;i ++)
		in_linkqueue(p,&i);

	//out_linkqueue(p,&buf);

	print_link(p);

	i = 13;
	while(i --){
		buf = -1;
		out_linkqueue(p,&buf);
		printf("out:%d\n",buf);
	}

	print_link(p);
	for(i = 0;i < 10;i ++)
		in_linkqueue(p,&i);
	print_link(p);

	return 0;
}

循环队列

#include <stdio.h>
#include <stdlib.h>
//循环队列
typedef int data_t;
typedef struct queue{
	data_t *data;
	int size;
	int head;
	int tail;
}queue_t;

queue_t *creat_queue(int size) //传递 可以容纳的数据个数
{ 
	queue_t *p;
	p = malloc(sizeof(queue_t));
	p->data = malloc(sizeof(data_t) * (size + 1));
	p->size = size + 1; // 保存真实的数组元素个数,实际空间大小

	p->head = 0;
	p->tail = 0;

	return p;
}

int in_queue(queue_t *p,const data_t *data)
{
	//容错：当队列满 ，直接退出   （tail + 1）% size == head
	//1.向尾部写入数据
	//2.tail ++
	if((p->tail + 1) % p->size == p->head)
		return -1;

	p->data[p->tail] = *data;

	p->tail = (p->tail + 1) % p->size;

	return 0;
}

int out_queue(queue_t *p,data_t *databuf)
{
	//容错：当队列空   head == tail
	if(p->head == p->tail)
		return -1;

	//1.读取头部数据
	//2.head ++

	*databuf = p->data[p->head];
	p->head = (p->head + 1) % p->size;

	return 0;
}

int get_length_queue(queue_t *p)
{
	return (p->size + (p->tail - p->head)) % p->size;
}


int clean_queue(queue_t *p)
{
	p->head = 0;
	p->tail = 0;
	return 0;
}

void print_queue(queue_t *p)
{
	int i;

	for(i = p->head;i != p->tail;
			i = (i + 1 ) % p->size)
	{
		printf("%d ",p->data[i]);
	}
	printf("\n");

	return ;
}



int main(int argc, const char *argv[])
{
	
	queue_t *p;
	int i;
	data_t buf;
	
	p = creat_queue(8);

	for(i = 0;i < 10;i ++){
		in_queue(p,&i);
	}
	print_queue(p);
	
	i = 5;
	while(i --){
		buf = -1;
		out_queue(p,&buf);
		printf("out:%d\n",buf);
	}

	for(i = 250;i < 256;i ++){
		in_queue(p,&i);
	}
	print_queue(p);

	i = 10;
	while(i --){
		buf = -1;
		out_queue(p,&buf);
		printf("out:%d\n",buf);
	}

	print_queue(p);
	return 0;
}