[数据结构与算法] 数据结构（五）-队列（Java、C语言）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构（五）-队列（Java、C语言） -> 正文阅读

[数据结构与算法]数据结构（五）-队列（Java、C语言）

今天内容比较简单~

文章目录

一、队列的定义

队列：队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

二、队列的抽象数据类型

ADT Queue{

数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0}

数据关系：R1={<ai-1,ai>|ai-1,ai∈D, i=1,2, …,n }

           约定a1为队列头，an为队列尾。
基本操作：
   InitQueue( &Q )
     操作结果：构造一个空队列Q。
   DestroyQueue ( &Q )
     初始条件：队列Q已存在。
     操作结果：销毁队列Q。
   ClearQueue ( &Q )
     初始条件：队列Q已存在。
     操作结果：将Q清为空队列。
   QueueEmpty( Q )
     初始条件：队列Q已存在。
     操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。
   QueueLength( Q )
     初始条件：队列Q已存在。
     操作结果：返回Q的数据元素个数，即队列的长度。
   GetHead( Q, &e )
     初始条件：队列Q已存在且非空。
     操作结果：用e返回Q的队头元素。
   EnQueue( &Q, e )
     初始条件：队列Q已存在。
     操作结果：插入元素e为Q的新的队尾元素。
   DeQueue( &Q, &e )
     初始条件：队列Q已存在且非空。
     操作结果：删除Q的队头元素，并用e返回其值。
QueueTraverse( Q, visit() )
     初始条件：队列Q已存在且非空。
     操作结果：从队头到队尾依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。
}ADT Queue

三、循环队列（C语言）

如果使用队列的顺序存储结构，我们来想想有什么不足？

由于这是一个线性表，我们在队尾进行添加并没有什么问题，但是当我们在队首出队一个元素之后，后面的元素都需要向前挪动一个位置，此时的时间复杂度是n，因此，我们需要寻找一种方法来弥补这种不足。

队首元素不一定存储在0下标的位置可以解决上述问题吗？会不会产生新的问题？

我们如果让出队的元素出队后，后面的元素不移动，可以解决上述问题，但是，这会产生一个新的问题，当最后一个元素的位置已经位于数组的最后，再插入一个新的元素，那么这个新的元素将无法插入进去，会报数组越界的错误。

循环队列：
上述问题，都可以用循环队列来进行解决，让存储的时候，存储到末尾的时候又从头开始添加
在这里插入图片描述
由上面的图我们可以知道，循环队列需要一个头指针和尾指针进行标识，front为头指针，rear为尾指针。下面来讨论几种方法的实现

如何判断队列为空：
若头指针和尾指针相同，则判断为空，即front==rear

如何判断队列为满：
若队列为满，也会出现front=rear的情况，为了与队列为空的时候区别开来，我们可以保留一个空位，这个空位不存放元素，如果队列内除了这个元素其他元素都满了，则说明队列已经满了。可以看上面那个图。
队列满的条件：
(rear+2)%QueueSize==front

如何计算队列长度：
（rear-front+QueueSize）%QueueSize

#include "stdio.h"    
#include "stdlib.h"   

#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */

/* 循环队列的顺序存储结构 */
typedef struct
{
	QElemType data[MAXSIZE];
	int front;    	/* 头指针 */
	int rear;		/* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}SqQueue;

Status visit(QElemType c)
{
	printf("%d ",c);
	return OK;
}

/* 初始化一个空队列Q */
Status InitQueue(SqQueue *Q)
{
	Q->front=0;
	Q->rear=0;
	return  OK;
}

/* 将Q清为空队列 */
Status ClearQueue(SqQueue *Q)
{
	Q->front=Q->rear=0;
	return OK;
}

/* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
Status QueueEmpty(SqQueue Q)
{ 
	if(Q.front==Q.rear) /* 队列空的标志 */
		return TRUE;
	else
		return FALSE;
}

/* 返回Q的元素个数，也就是队列的当前长度 */
int QueueLength(SqQueue Q)
{
	return  (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

/* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
Status GetHead(SqQueue Q,QElemType *e)
{
	if(Q.front==Q.rear) /* 队列空 */
		return ERROR;
	*e=Q.data[Q.front];
	return OK;
}

/* 若队列未满，则插入元素e为Q新的队尾元素 */
Status EnQueue(SqQueue *Q,QElemType e)
{
	if ((Q->rear+1)%MAXSIZE == Q->front)	/* 队列满的判断 */
		return ERROR;
	Q->data[Q->rear]=e;			/* 将元素e赋值给队尾 */
	Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置， */
								/* 若到最后则转到数组头部 */
	return  OK;
}

/* 若队列不空，则删除Q中队头元素，用e返回其值 */
Status DeQueue(SqQueue *Q,QElemType *e)
{
	if (Q->front == Q->rear)			/* 队列空的判断 */
		return ERROR;
	*e=Q->data[Q->front];				/* 将队头元素赋值给e */
	Q->front=(Q->front+1)%MAXSIZE;	/* front指针向后移一位置， */
									/* 若到最后则转到数组头部 */
	return  OK;
}

/* 从队头到队尾依次对队列Q中每个元素输出 */
Status QueueTraverse(SqQueue Q)
{ 
	int i;
	i=Q.front;
	while((i+Q.front)!=Q.rear)
	{
		visit(Q.data[i]);
		i=(i+1)%MAXSIZE;
	}
	printf("\n");
	return OK;
}

int main()
{
	Status j;
	int i=0,l;
	QElemType d;
	SqQueue Q;
	InitQueue(&Q);
	printf("初始化队列后，队列空否？%u(1:空 0:否)\n",QueueEmpty(Q));

	printf("请输入整型队列元素(不超过%d个),-1为提前结束符: ",MAXSIZE-1);
	do
	{
		/* scanf("%d",&d); */
		d=i+100;
		if(d==-1)
			break;
		i++;
		EnQueue(&Q,d);
	}while(i<MAXSIZE-1);

	printf("队列长度为: %d\n",QueueLength(Q));
	printf("现在队列空否？%u(1:空 0:否)\n",QueueEmpty(Q));
	printf("连续%d次由队头删除元素,队尾插入元素:\n",MAXSIZE);
	for(l=1;l<=MAXSIZE;l++)
	{
		DeQueue(&Q,&d);
		printf("删除的元素是%d,插入的元素:%d \n",d,l+1000);
		/* scanf("%d",&d); */
		d=l+1000;
		EnQueue(&Q,d);
	}
	l=QueueLength(Q);

	printf("现在队列中的元素为: \n");
	QueueTraverse(Q);
	printf("共向队尾插入了%d个元素\n",i+MAXSIZE);
	if(l-2>0)
		printf("现在由队头删除%d个元素:\n",l-2);
	while(QueueLength(Q)>2)
	{
		DeQueue(&Q,&d);
		printf("删除的元素值为%d\n",d);
	}

	j=GetHead(Q,&d);
	if(j)
		printf("现在队头元素为: %d\n",d);
	ClearQueue(&Q);
	printf("清空队列后, 队列空否？%u(1:空 0:否)\n",QueueEmpty(Q));
	return 0;
}

四、循环队列（Java）

Java中其实封装好了很多数据结构，但是我们为什么要自己再写一遍呢？如果我们遇到Java中的数据额结构无法满足生产需求的时候，我们这种时候就可以自己根据需求写一个数据结构来使用，但是这种情况下，往往容易出现一些未知的错误，因此，一般非特殊情况并不推荐使用自己写的数据结构。下面是自己写的一个代码。也可以进行泛型化，这样更接近源码。

package Text;

// 栈的链式存储：优点是不存在栈满的情况
public class LinkStack {
    private Node header = new Node();   // 创建头节点
    class Node {
        String value;
        Node next;      
    }
    public boolean push(String value) {
        Node n = new Node();
        n.value = value;
        if(header.next == null) {
            header.next = n;
            return true;
        }
        n.next = header.next;
        header.next = n;
        return true;

    }
    public boolean pop() {
        if(header.next == null) {
            return false;
        }
        header.next = header.next.next;
        return true;
    }
    public String getTop() {
        if(header.next != null) {
            return header.next.value;
        }
        return null;
    }
    public boolean isEmpty() {
        return header.next == null ? true : false;
    }
}

五、队列的链式存储结构的实现（C语言、Java）

相比于循环队列，其实队列的链式存储结构更加简单，它没有存储空间限制，并且也没有元素移动问题，操作与实现上与线性表是一模一样的。

上代码：

#include "stdio.h"    
#include "stdlib.h"   

#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 

typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */

typedef struct QNode	/* 结点结构 */
{
   QElemType data;
   struct QNode *next;
}QNode,*QueuePtr;

typedef struct			/* 队列的链表结构 */
{
   QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;

Status visit(QElemType c)
{
	printf("%d ",c);
	return OK;
}

/* 构造一个空队列Q */
Status InitQueue(LinkQueue *Q)
{ 
	Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
	if(!Q->front)
		exit(OVERFLOW);
	Q->front->next=NULL;
	return OK;
}

/* 销毁队列Q */
Status DestroyQueue(LinkQueue *Q)
{
	while(Q->front)
	{
		 Q->rear=Q->front->next;
		 free(Q->front);
		 Q->front=Q->rear;
	}
	return OK;
}

/* 将Q清为空队列 */
Status ClearQueue(LinkQueue *Q)
{
	QueuePtr p,q;
	Q->rear=Q->front;
	p=Q->front->next;
	Q->front->next=NULL;
	while(p)
	{
		 q=p;
		 p=p->next;
		 free(q);
	}
	return OK;
}

/* 若Q为空队列,则返回TRUE,否则返回FALSE */
Status QueueEmpty(LinkQueue Q)
{ 
	if(Q.front==Q.rear)
		return TRUE;
	else
		return FALSE;
}

/* 求队列的长度 */
int QueueLength(LinkQueue Q)
{ 
	int i=0;
	QueuePtr p;
	p=Q.front;
	while(Q.rear!=p)
	{
		 i++;
		 p=p->next;
	}
	return i;
}

/* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
Status GetHead(LinkQueue Q,QElemType *e)
{ 
	QueuePtr p;
	if(Q.front==Q.rear)
		return ERROR;
	p=Q.front->next;
	*e=p->data;
	return OK;
}


/* 插入元素e为Q的新的队尾元素 */
Status EnQueue(LinkQueue *Q,QElemType e)
{ 
	QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
	if(!s) /* 存储分配失败 */
		exit(OVERFLOW);
	s->data=e;
	s->next=NULL;
	Q->rear->next=s;	/* 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中① */
	Q->rear=s;		/* 把当前的s设置为队尾结点，rear指向s，见图中② */
	return OK;
}

/* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
Status DeQueue(LinkQueue *Q,QElemType *e)
{
	QueuePtr p;
	if(Q->front==Q->rear)
		return ERROR;
	p=Q->front->next;		/* 将欲删除的队头结点暂存给p，见图中① */
	*e=p->data;				/* 将欲删除的队头结点的值赋值给e */
	Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继，见图中② */
	if(Q->rear==p)		/* 若队头就是队尾，则删除后将rear指向头结点，见图中③ */
		Q->rear=Q->front;
	free(p);
	return OK;
}

/* 从队头到队尾依次对队列Q中每个元素输出 */
Status QueueTraverse(LinkQueue Q)
{
	QueuePtr p;
	p=Q.front->next;
	while(p)
	{
		 visit(p->data);
		 p=p->next;
	}
	printf("\n");
	return OK;
}

int main()
{
	int i;
	QElemType d;
	LinkQueue q;
	i=InitQueue(&q);
	if(i)
		printf("成功地构造了一个空队列!\n");
	printf("是否空队列？%d(1:空 0:否)  ",QueueEmpty(q));
	printf("队列的长度为%d\n",QueueLength(q));
	EnQueue(&q,-5);
	EnQueue(&q,5);
	EnQueue(&q,10);
	printf("插入3个元素(-5,5,10)后,队列的长度为%d\n",QueueLength(q));
	printf("是否空队列？%d(1:空 0:否)  ",QueueEmpty(q));
	printf("队列的元素依次为：");
	QueueTraverse(q);
	i=GetHead(q,&d);
	if(i==OK)
	 printf("队头元素是：%d\n",d);
	DeQueue(&q,&d);
	printf("删除了队头元素%d\n",d);
	i=GetHead(q,&d);
	if(i==OK)
		printf("新的队头元素是：%d\n",d);
	ClearQueue(&q);
	printf("清空队列后,q.front=%u q.rear=%u q.front->next=%u\n",q.front,q.rear,q.front->next);
	DestroyQueue(&q);
	printf("销毁队列后,q.front=%u q.rear=%u\n",q.front, q.rear);
	
	return 0;
}

下面是Java的代码

public class MyQueue {
    private Node front;// 指向队列头元素的引用
    private Node rear;// 指向队列尾元素的引用
 
    private MyQueue() {
        front = null;
        rear = null;
    }
    public boolean isEmpty() {
        // 指向队头元素的引用为空即队列为空
        return front == null;
    }
    public void addQueue(Object item) {
        // 创建一个要插入的新结点
        Node newNode = new Node();
        newNode.setData(item);
        newNode.setNext(null);
        if (isEmpty()) {
            front = newNode;
            rear = front;
        } else {
            rear.setNext(newNode);
            rear = newNode;
        }
    }
 
    public Object deleteQueue() throws Exception {
        if (isEmpty()) {
            throw new Exception("队列为空！");
        } else {
            Node delNode = front;
            if (front == rear) {
                front = rear = null;
            } else {
                front = front.getNext();
            }
            return delNode.getData();
        }
    }
}