队列的理解与使用

时间：2022-03-21 17:37:16



1、概念与理解


 队列在实际生活中是经常遇到的，比如上班高峰期地铁站限流。回归到本质，队列其实也是一种运算受限制的线性表，它的特点是，只可以在对头删除元素，在队尾插入元素，所以这是一种先进先出的数据结构。它和栈不一样，栈是只有一端可以执行插入删除的操作，因此定义栈的运算的时候，只要一个标记能够标志顶点元素就可以。但是在队列中，它是有两端的，并且两端各执行不一样的操作，所以定义一个数据结构来表达队列相对比较复杂一点。


2、队列的数据结构定义
队列是一种受限制的线性表，因此也拥有线性表的特点。根据存储方式的不同，队列可以分为顺序队列和链式队列，根据不同的存储方式，定义的结构也不同。


2.1 、顺序队列的数据结构定义


 既然是顺序队列，那么必然包含一个数组成员。前面提到队列含有两端，并且各端对应的操作不相同，因此很有必要使用两个标记来标志这两端。一般我们把执行删除操作的一端称为对头，执行插入操作的一端称为队尾。下面的数据结构均用C语言语法定义，随后会使用实际例子实现基本运算。 

typedef struct queue
{
dataType data[MAXSIZE];
int front,rear;
}LQueue


对于顺序队列我们还需要考虑一个问题，假如我们现在有一个容量为5的名称是a的队列，一开始给队列中a[0]-a[4]赋值0，1，2，3，4。然后移除对头的元素0，1。此时，队列还剩2，3，4，空余两个位置。此时如果我们在队尾插入元素，会发现，队列已经满了。但是明明有两个空余的位置对吧？我们可以将队列想象成首位连接的一个圆圈，我们称为循环队列。在确定插入的元素应该处于哪个位置的时候，使用(rear+1)%5求出模，就是新插入的元素应该处于的位置。
好了，上面的一个问题解决了。现在考虑一下，队列什么时候是空？即对头等于队尾的时候，这里是front==rear表示队列为空。再考虑一下，队列什么时候为满，没错也是front==rear。好了，当front==rear的时候，究竟是空表还是满表呢。思路如下：
假如现在进行插入操作(n代表队列的容量)：rear=(rear+1)%n,front不变。
假如现在进行删除操作:front=(front+1)%n,rea不变。
发现了没有，其实如果我们执行的是插入操作遇到rear==front的情况，说明对满。执行删除操作的时候则是对空。


2.2、链式队列的数据结构定义


链式队列和顺序队列的不同之处在于，它的数组长度是动态增长，所以它并没有对满的忧虑。首先需要一个节点，表示每个队列元素的结构，其次我们还需要一个数据结构来定义指向对头和队尾的节点。如下：
typedef struct node
{
dataType data;
struct node *next;
}PNode

typedef struct queue
{
PNode *read,*front;
}PQueue

其中node是队列的节点，queue表示整个队列，含有对头和队尾元素。


3、队列的基本运算


①、初始化队列：init_queue
②、判断对空：isEmpty_queue
③、对头元素出队：delete_element
④、队尾添加元素：insert_element
⑤、读取队头元素：get_element
上述只是基于队列的基本运算，实际应用中应该根据队列的特点以及需求共同定义运算。



4、C语言实现链式队列的基本运算

 

/*
实现链式队列的基本运算
*/

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


/*
声明链式队列的节点元素
*/
typedef struct node
{
int data;//存放数据
struct node *next;//连接下一节点
}Node;


/*
由于队列需要知道队头和队尾元素，所以声明一个队列的基本结构
*/

typedef struct queue
{
Node *front;//指向对头元素
Node *rear;//指向队尾元素
}Queue;


/*
声明基本运算
*/

Queue* init_queue();//初始化队列
int isEmpty_queue(Queue *pQueue);//判断对空
void insert_element(Queue *pQueue, int data);//向队尾插入元素
void delete_element(Queue *pQueue);//移除对头元素
int get_element(Queue* pQueue);//获取对头元素

int main(void)
{
Queue *queue = init_queue();
for (int i = 1; i <= 5; i++)
{
insert_element(queue, i);
}
printf("队头元素:%d\n", get_element(queue));
delete_element(queue);
printf("删除1之后队头元素:%d\n", get_element(queue));

system("pause");
return 0;
}

/*
初始化队列
*/
Queue* init_queue()
{
Queue *pQueue = (Queue *)malloc(sizeof(Queue));
//先定义一个表头，然后让队列都指向它，这样就把队列和队列的元素连接起来了。
Node *pHeader = (Node *)malloc(sizeof(Node));
pHeader->data =-1;
pHeader->next = NULL;
//将对头和队尾都指向表头元素。
pQueue->front = pHeader;
pQueue->rear = pHeader;
return pQueue;
}

/*
判断对空
*/
int isEmpty_queue(Queue *pQueue)
{
//因为链式表是动态增长的，长度是没有限制的，所以当对头等于队尾，一定是空队列。
if (pQueue->front == pQueue->rear)
return 1;
return 0;
}

/*
在队尾插入元素
*/
void insert_element(Queue *pQueue, int data)
{
Node *pNode = (Node *)malloc(sizeof(Node));
pNode->data = data;
pNode->next = NULL;
//先获取当前的队尾元素
Node *pRear = pQueue->rear;
//此队尾元素是即将插入队尾元素的下一个元素
pRear->next = pNode;
//将当前结点设为队尾元素
pQueue->rear = pNode;
}

/*
移除队头元素
对头用于指向头节点
*/
void delete_element(Queue *pQueue)
{
if (isEmpty_queue(pQueue) == 1)
{
printf("对空/n");
}
else
{
//获取当前队列的头节点
Node *pHeader = pQueue->front;
//获取当前队列的头节点的下一节点元素，即队头
Node *pFront = pHeader->next;
//获取对头的下一节点，作为新的对头
Node *pNewFront = pFront->next;

pHeader->next=pNewFront;//将新的对头元素赋值给头节点。
free(pFront);

//如果队列只有一个元素，则删除之后，队尾指针则指向了不确定的值，所以应该重新将队尾指向头节点
if (pNewFront == NULL)//说明是空的队列
{
pQueue->rear = pHeader;
}
}
}


/*
获取队头元素的值
*/
int get_element(Queue* pQueue)
{
if (isEmpty_queue(pQueue) == 1)
{
return -1;
}
Node *pFront = pQueue->front->next;
return pFront->data;
}
注释已经说明的很清楚了。我们很容易犯得一个错误的思维定势是，总是认为next是从队尾指向队头的方向。在队列中，其实是队头指向队尾的方向。

运行效果：
队列的理解与使用



5、c++实现链式队列


 首先定义一个Node.h。 
class Node
{
public:
Node();
~Node();
int data;
Node *next;

private:

};

Node::Node()
{
}

Node::~Node()
{
}


其次是定义Queue.h 
#include "Node.h"
#include <iostream>

class Queue
{
public:
Queue();
~Queue();
Queue(Node *header);
int isEmpty_queue(Queue *pQueue);//判断对空
void insert_element(Queue *pQueue, int data);//向队尾插入元素
void delete_element(Queue *pQueue);//移除对头元素
int get_element(Queue* pQueue);//获取对头元素
Node *rear;
Node *front;

private:

};
Queue::Queue(Node *header)
{

rear = header;
front = header;
}
Queue::Queue()
{
}

Queue::~Queue()
{
}


/*
判断对空
*/
int isEmpty_queue(Queue *pQueue)
{
//因为链式表是动态增长的，长度是没有限制的，所以当对头等于队尾，一定是空队列。
if (pQueue->front == pQueue->rear)
return 1;
return 0;
}

/*
在队尾插入元素
*/
void insert_element(Queue *pQueue, int data)
{
Node *pNode = new Node;
pNode->data = data;
pNode->next = nullptr;
//先获取当前的队尾元素
Node *pRear = pQueue->rear;
//此队尾元素是即将插入队尾元素的下一个元素
pRear->next = pNode;
//将当前结点设为队尾元素
pQueue->rear = pNode;
}

/*
移除队头元素
对头用于指向头节点
*/
void delete_element(Queue *pQueue)
{
if (isEmpty_queue(pQueue) == 1)
{

std::cout<<"对空"<<std::endl;
}
else
{
//获取当前队列的头节点
Node *pHeader = pQueue->front;
//获取当前队列的头节点的下一节点元素，即队头
Node *pFront = pHeader->next;
//获取对头的下一节点，作为新的对头
Node *pNewFront = pFront->next;

pHeader->next = pNewFront;//将新的对头元素赋值给头节点。
free(pFront);

//如果队列只有一个元素，则删除之后，队尾指针则指向了不确定的值，所以应该重新将队尾指向头节点
if (pNewFront == nullptr)//说明是空的队列
{
pQueue->rear = pHeader;
}
}
}

/*
获取队头元素的值
*/
int get_element(Queue* pQueue)
{
if (isEmpty_queue(pQueue) == 1)
{
return -1;
}
Node *pFront = pQueue->front->next;
return pFront->data;
}

最后是Main.cpp 
#include <iostream>
#include "Queue.h"

int main()
{
Node *header = new Node;
header->data = -1;
header->next = nullptr;
Queue *queue = new Queue(header);
for (int i = 1; i <= 5; i++)
{
insert_element(queue, i);
}
std::cout<<"队头元素"<<get_element(queue)<<std::endl;
delete_element(queue);
std::cout << "移除1之后队头元素" << get_element(queue) << std::endl;

system("pause");
return 0;
}


运行结果：

队列的理解与使用


6、java实现顺序队列

Queue.java 
public class Queue {

private int data[]=new int[5];
private int front=-1,rear=-1,num=0;//num表示队列的元素


/*
判断对空
*/
public  boolean isEmpty_queue()
{
//因为链式表是动态增长的，长度是没有限制的，所以当对头等于队尾，一定是空队列。
if (num==0)
return true;
return false;
}


/*
在队尾插入元素
*/
public void insert_element( int param)
{

if(num==5)
{
System.out.println("队列满");
return ;
}
else
{
rear=(rear+1)%5;
data[rear]=param;
num++;
}
}

/*
移除队头元素
对头用于指向头节点
*/
public void delete_element()
{
if(isEmpty_queue())
{
System.out.println("队空");
return ;
}else
{
front=(front+1)%5;
num--;
}
}

/*
获取队头元素的值
*/
public int get_element()
{
if (isEmpty_queue() )
{
System.out.println("队空");
return -1;
}
if(front==-1)
front=0;
return data[front];
}

}


QueueMain.java 
/**
 *java实现顺序队列
 */
public class QueueMain {

public static void main(String args[])
{
Queue queue = new Queue();
for (int i = 1; i <= 5; i++)
{
 queue.insert_element(i);
}
System.out.println("队头元素:"+ queue.get_element());
queue.delete_element();
System.out.println("删除1之后队头元素:"+queue.get_element());


}

}


运行结果：
队列的理解与使用




---------文章写自：HyHarden---------

--------博客地址：http://blog.csdn.net/qq_25722767-----------



标签：

相关文章