欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

队列queue的实现

程序员文章站 2024-03-18 08:15:52
...

顺序表实现

##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;
}