数据结构——顺序队列与链式队列的实现

2024-01-03 07:09:55

一、概念

1、队列的定义

2、队首

一、概念

1、队列的定义

??队列?是仅限在?一端?进行?插入，另一端?进行?删除?的?线性表。
??队列?又被称为先进先出（First In First Out）的线性表，简称 FIFO 。

2、队首

??允许进行元素删除的一端称为?队首。如下图所示：

3、队尾

??允许进行元素插入的一端称为?队尾。如下图所示：

二、接口

1、可写接口

1）数据入队

??队列的插入操作，叫做?入队。它是将?数据元素?从?队尾?进行插入的过程，如图所示，表示的是?插入?两个数据（绿色和蓝色）的过程：

2）数据出队

??队列的删除操作，叫做?出队。它是将?队首?元素进行删除的过程，如图所示，表示的是依次?删除?两个数据（红色和橙色）的过程：

3）清空队列

??队列的清空操作，就是一直?出队，直到队列为空的过程，当?队首?和?队尾?重合时，就代表队尾为空了，如图所示：

2、只读接口

1）获取队首数据

??对于一个队列来说只能获取?队首?数据，一般不支持获取其它数据。

2）获取队列元素个数

??队列元素个数一般用一个额外变量存储，入队?时加一，出队?时减一。这样获取队列元素的时候就不需要遍历整个队列。通过?O(1)?的时间复杂度获取队列元素个数。

3）队列的判空

??当队列元素个数为零时，就是一个?空队，空队?不允许?出队?操作。

三、队列的顺序表实现

1、数据结构定义

对于顺序表，在 C语言中表现为?数组，在进行?队列的定义?之前，我们需要考虑以下几个点：
??1）队列数据的存储方式，以及队列数据的数据类型；
??2）队列的大小；
??3）队首指针；
??4）队尾指针；

我们可以定义一个?队列?的?结构体，C语言实现如下所示：

#define MAXSIZE 10
typedef int datatype;

typedef struct seqqueue{
	datatype data[MAXSIZE];
	int front,rear;
}seq_queue,*seq_pqueue;

2、初始化创造队列

第一种无形参，C语言实现如下所示：

seq_pqueue init1_seqqueue(void)
{
	seq_pqueue q;
	q=(seq_pqueue)malloc(sizeof(seq_queue));
	if(q==NULL)
	{
		perror("malloc");
		exit(-1);
	}
	q->front=q->rear=MAXSIZE-1;

	return q;
}

第二种有形参，C语言实现如下所示：

void init_seqqueue(seq_pqueue *Q)
{
	*Q=(seq_pqueue)malloc(sizeof(seq_queue));
	if((*Q)==NULL)
	{
		perror("malloc");
		exit(-1);
	}
	(*Q)->front=(*Q)->rear=MAXSIZE-1;
	
	return;
}

3、判断队列是否满

C语言实现如下所示：

bool is_full_seqqueue(seq_pqueue q)
{
	if((q->rear+1)%MAXSIZE == q->front)
		return true;
	else
		return false;
}

4、判断队列是否空

C语言实现如下所示：

bool is_empty_seqqueue(seq_pqueue q)
{
	if(q->rear == q->front)
		return true;
	else
		return false;
}

5、入队

C语言实现如下所示：

bool in_seqqueue(datatype data,seq_pqueue q)
{
	//判断队列是否满
	if(is_full_seqqueue(q)){
		printf("队列已满!\n");
		return false;
	}

	//入队
	q->rear=(q->rear+1)%MAXSIZE;
	q->data[q->rear]=data;
	return true;
}

6、出队

C语言实现如下所示：

bool out_seqqueue(seq_pqueue q,datatype *D)
{
	//判断队列是否空
	if(is_empty_seqqueue(q)){
		printf("队列已空!\n");
		return false;
	}

	//出队
	q->front=(q->front+1)%MAXSIZE;
	*D=q->data[q->front];

	return true;
}

7、打印队列

C语言实现如下所示：

void show_seqqueue(seq_pqueue q)
{
	int i;
	if(is_empty_seqqueue(q))
		return;
	//非空时，从对头打印到队尾
	for(i=(q->front+1)%MAXSIZE;i!=(q->rear+1)%MAXSIZE;i=(i+1)%MAXSIZE)
	{
		printf("%d\t",q->data[i]);
	}
	printf("\n");
}

8、队列的顺序表实现源码

seqqueue.h

#ifndef __SEQQUEUE_H__
#define __SEQQUEUE_H__

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

#define MAXSIZE 10
typedef int datatype;

typedef struct seqqueue{
	datatype data[MAXSIZE];
	int front,rear;
}seq_queue,*seq_pqueue;

extern seq_pqueue init1_seqqueue(void);
extern void init_seqqueue(seq_pqueue *Q);
extern bool is_full_seqqueue(seq_pqueue q);
extern bool is_empty_seqqueue(seq_pqueue q);
extern bool in_seqqueue(datatype data,seq_pqueue q);
extern bool out_seqqueue(seq_pqueue q,datatype *D);
extern void show_seqqueue(seq_pqueue q);

#endif

seqqueue.c

#include "seqqueue.h"

seq_pqueue init1_seqqueue(void)
{
	seq_pqueue q;
	q=(seq_pqueue)malloc(sizeof(seq_queue));
	if(q==NULL)
	{
		perror("malloc");
		exit(-1);
	}
	q->front=q->rear=MAXSIZE-1;

	return q;
}

void init_seqqueue(seq_pqueue *Q)
{
	*Q=(seq_pqueue)malloc(sizeof(seq_queue));
	if((*Q)==NULL)
	{
		perror("malloc");
		exit(-1);
	}
	(*Q)->front=(*Q)->rear=MAXSIZE-1;
	
	return;
}

//判断队列是否满
bool is_full_seqqueue(seq_pqueue q)
{
	if((q->rear+1)%MAXSIZE == q->front)
		return true;
	else
		return false;
}

//入队
bool in_seqqueue(datatype data,seq_pqueue q)
{
	//判断队列是否满
	if(is_full_seqqueue(q)){
		printf("队列已满!\n");
		return false;
	}

	//入队
	q->rear=(q->rear+1)%MAXSIZE;
	q->data[q->rear]=data;
	return true;
}

//判断队列是否空
bool is_empty_seqqueue(seq_pqueue q)
{
	if(q->rear == q->front)
		return true;
	else
		return false;
}

//出队
bool out_seqqueue(seq_pqueue q,datatype *D)
{
	//判断队列是否空
	if(is_empty_seqqueue(q)){
		printf("队列已空!\n");
		return false;
	}

	//出队
	q->front=(q->front+1)%MAXSIZE;
	*D=q->data[q->front];

	return true;
}

void show_seqqueue(seq_pqueue q)
{
	int i;
	if(is_empty_seqqueue(q))
		return;
	//非空时，从对头打印到队尾
	for(i=(q->front+1)%MAXSIZE;i!=(q->rear+1)%MAXSIZE;i=(i+1)%MAXSIZE)
	{
		printf("%d\t",q->data[i]);
	}
	printf("\n");
}

test.c

#include "seqqueue.h"
/* 用循环队列实现如下功能：
 * 用户从键盘输入整数，程序将其入队;
 * 用户从键盘输入字母，程序将队头元素出队;
 * 并在每一次出队和入队之后打印队列元素。
 */
int main(int argc, const char *argv[])
{
	seq_pqueue q;
	datatype data,t,ret;
	
	init_seqqueue(&q);

	while(1)
	{
		printf("请输入一个整数或字符:");
		ret=scanf("%d",&data);
		
		//输入整数时，入队
		if(ret == 1)
		{
			if(in_seqqueue(data,q))
				show_seqqueue(q);
		}
		else
		{
			//输入为字符时
			if(out_seqqueue(q,&t))
			{
				printf("out:%d\n",t);
				show_seqqueue(q);
			}
			//清空输入缓冲区
			while(getchar()!='\n');
		}
	}
	return 0;
}

Makefile

CC = gcc
CFLAGS = -o0 -g -Wall

SRC=seqqueue.c test.c
OBJS=test

$(OBJS):$(SRC)
	$(CC) $(CFLAGS) -o $@ $^

.PHONY:clean
clean:
	rm -rf $(OBJS) *.o

"-o0"表示优化级别为0，即关闭优化。这将导致生成的可执行文件较大，但是可以方便地进行调试。
"-g"表示生成调试信息，以便在调试程序时可以查看变量的值、函数的调用栈等信息。
"-Wall"表示启用所有警告，编译器将会显示所有可能的警告信息，帮助开发人员发现潜在的问题。

编译结果测试:

四、队列的链表实现

1、数据结构定义

对于链表，在进行?队列的定义?之前，我们需要考虑以下几个点：
??1）队列数据的存储方式，以及队列数据的数据类型；
??2）队列的大小；
??3）队首指针；
??4）队尾指针；

我们可以定义一个?队列?的?结构体，C语言实现如下所示：

typedef int datatype;

typedef struct linkqueuenode{ 
	datatype data;                    /* 数据域 */
	struct linkqueuenode *next;       /* 指针域 */
}linkqueue_node,*linkqueue_pnode;

typedef struct linkqueue{
	linkqueue_pnode front,rear;       /* 链队列指针 */
}link_queue,*link_pqueue;

2、初始化创造队列

C语言实现如下所示：

void init_linkqueue(link_pqueue *Q)
{
	//申请front和rear的空间
	*Q=(link_pqueue)malloc(sizeof(link_queue));
	if((*Q)==NULL)
	{
		perror("malloc");
		exit(-1);
	}
	//申请头结点空间
	(*Q)->front=(linkqueue_pnode)malloc(sizeof(linkqueue_node));
	if((*Q)->front==NULL)
	{
		perror("malloc");
		exit(-1) ;
	}

	(*Q)->front->next=NULL;
	(*Q)->rear=(*Q)->front;

	return;
}

3、判断队列是否空

C语言实现如下所示：

bool is_empty_linkqueue(link_pqueue q)
{
	if(q->rear == q->front)
		return true;
	else
		return false;
}

4、入队

C语言实现如下所示：

bool in_linkqueue(datatype data,link_pqueue q)
{
	linkqueue_pnode  new;

	//申请数据结点空间
	new=(linkqueue_pnode)malloc(sizeof(linkqueue_node));
	if(new==NULL)
	{
		puts("入队失败！");
		return false;
	}
	//将数据存储在申请的空间
	new->data=data;
	
	//将new指向的结点插入到链式队列中
	new->next=q->rear->next;
	q->rear->next=new;
	
	//让rear指针指向新的队尾结点
	q->rear=q->rear->next;

	return true;
}

5、出队

C语言实现如下所示：

bool out_linkqueue(link_pqueue q,datatype *D)
{
	linkqueue_pnode t;
	//判断队列是否空
	if(is_empty_linkqueue(q)){
		printf("队列已空!\n");
		return false;
	}

	//出队
	t=q->front;
	q->front =q->front->next;
	*D=q->front->data;
	free(t);

	return true;
}

6、打印队列

C语言实现如下所示：

void show_linkqueue(link_pqueue q)
{
	linkqueue_pnode p;
	if(is_empty_linkqueue(q))
		return;
	//非空时，从对头打印到队尾
	for(p=q->front->next;p!=NULL;p=p->next)
	{
		printf("%d\t",p->data);
	}
	printf("\n");
}

7、队列的链表实现源码

linkqueue.h

#ifndef __LINKQUEUE_H__
#define __LINKQUEUE_H__

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

typedef int datatype;

typedef struct linkqueuenode{
	datatype data;
	struct linkqueuenode *next;
}linkqueue_node,*linkqueue_pnode;

typedef struct linkqueue{
	linkqueue_pnode front,rear;
}link_queue,*link_pqueue;

extern void init_linkqueue(link_pqueue *Q);
extern bool is_empty_linkqueue(link_pqueue q);
extern bool in_linkqueue(datatype data,link_pqueue q);
extern bool out_linkqueue(link_pqueue q,datatype *D);
extern void show_linkqueue(link_pqueue q);

#endif

linkqueue.c ? ? ?

#include "linkqueue.h"

void init_linkqueue(link_pqueue *Q)
{
	//申请front和rear的空间
	*Q=(link_pqueue)malloc(sizeof(link_queue));
	if((*Q)==NULL)
	{
		perror("malloc");
		exit(-1);
	}
	//申请头结点空间
	(*Q)->front=(linkqueue_pnode)malloc(sizeof(linkqueue_node));
	if((*Q)->front==NULL)
	{
		perror("malloc");
		exit(-1) ;
	}

	(*Q)->front->next=NULL;
	(*Q)->rear=(*Q)->front;

	return;
}

//入队
bool in_linkqueue(datatype data,link_pqueue q)
{
	linkqueue_pnode  new;

	//申请数据结点空间
	new=(linkqueue_pnode)malloc(sizeof(linkqueue_node));
	if(new==NULL)
	{
		puts("入队失败！");
		return false;
	}
	//将数据存储在申请的空间
	new->data=data;
	
	//将new指向的结点插入到链式队列中
	new->next=q->rear->next;
	q->rear->next=new;
	
	//让rear指针指向新的队尾结点
	q->rear=q->rear->next;

	return true;
}

bool is_empty_linkqueue(link_pqueue q)
{
	if(q->rear == q->front)
		return true;
	else
		return false;
}

//出队
bool out_linkqueue(link_pqueue q,datatype *D)
{
	linkqueue_pnode t;
	//判断队列是否空
	if(is_empty_linkqueue(q)){
		printf("队列已空!\n");
		return false;
	}

	//出队
	t=q->front;
	q->front =q->front->next;
	*D=q->front->data;
	free(t);

	return true;
}

void show_linkqueue(link_pqueue q)
{
	linkqueue_pnode p;
	if(is_empty_linkqueue(q))
		return;
	//非空时，从对头打印到队尾
	for(p=q->front->next;p!=NULL;p=p->next)
	{
		printf("%d\t",p->data);
	}
	printf("\n");
}

test.c

#include "linkqueue.h"
/* 用链式队列实现如下功能：
 * 用户从键盘输入整数，程序将其入对;
 * 用户从键盘输入字母，程序将队头元素出队;
 * 并在每一次出队和入队之后打印队列元素。
 */
int main(int argc, const char *argv[])
{
	link_pqueue q;
	datatype data,t,ret;
	
	init_linkqueue(&q);

	while(1)
	{
		printf("请输入一个整数或字符:");
		ret=scanf("%d",&data);
		
		//输入整数时，入对
		if(ret == 1)
		{
			if(in_linkqueue(data,q))
				show_linkqueue(q);
		}
		else
		{
			//输入为字符时
			if(out_linkqueue(q,&t))
			{
				printf("out:%d\n",t);
				show_linkqueue(q);
			}
			//清空输入缓冲区
			while(getchar()!='\n');
		}
	}
	return 0;
}

Makefile?

CC = gcc
CFLAGS = -o0 -g -Wall

SRC=linkqueue.c test.c
OBJS=test

$(OBJS):$(SRC)
	$(CC) $(CFLAGS) -o $@ $^

.PHONY:clean
clean:
	rm -rf $(OBJS) *.o

"-o0"表示优化级别为0，即关闭优化。这将导致生成的可执行文件较大，但是可以方便地进行调试。
"-g"表示生成调试信息，以便在调试程序时可以查看变量的值、函数的调用栈等信息。
"-Wall"表示启用所有警告，编译器将会显示所有可能的警告信息，帮助开发人员发现潜在的问题。

编译结果测试:

文章来源:https://blog.csdn.net/m0_74712453/article/details/135351817
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！