数据结构：队列

目录

 一、队列的基本概念 

1.队列的定义

二、队列的顺序存储结构 

1.顺序队列

1.1顺序队列的描述

2.循环队列

2.1循环队列的定义

2.2循环队列的分析

 2.3循环队列的实现

2.3.1循环队列的顺序存储结构

2.3.2循环队列的初始化

2.3.3循环队列判队空

2.3.4 循环队列长度

2.3.5循环队列入队

2.3.6循环队列判满

2.3.7循环队列出队

三、队列的链式存储结构

1.链队列的分析 

2.链队列的实现

2.1链队列的存储类型

2.2链队列的初始化

2.3队列的销毁

2.4队列的插入

2.5队列的删除

2.6队列头信息的获取

2.7队列末信息的获取

2.8队列节点数量的多少

2.9队列判空

3.循环队列使用循环链表实现

四、用栈实现队列

1.分析如何用栈实现队列

2.栈实现队列 

---

前言：

大家好！今天给大家带来的数据结构中的队列，希望这篇对大家能有帮助。

 一、队列的基本概念 

1.队列的定义

队列是一种只允许在一端进行插入数据操作另一端进行删除数据操作的特殊线性表。

队列是具有先进先出 FIFO(First In First Out)特性的线性表。

队头：进行删除数据的一端。

队尾：进行插入数据的一端。

因为队列是线性表的一种，所以队列有顺序存储结构和链式存储结构。

二、队列的顺序存储结构 

1.顺序队列

1.1顺序队列的描述

队列的顺序存储结构是通过数组来实现的。具体实现方式是用一个数组来存储队列中的元素，并且使用两个指针分别指向队列的头部和尾部。

#define  MAXSIZE  20
typedef struct 
{
  int data[MAXSIZE];
  int front,rear;//一个为队头指针，一个为队尾指针
}queue; 

初始状态时，对头指针与队尾指针均指向第一个元素：queue->front==queue->rear==0;

入队操作：将元素插入到队列的尾部，并将尾指针后移一位。

出队操作：将头指针指向的元素出队，并将头指针后移一位。

由上图此时该数组还未放满元素，如果在加入F元素的化却会失败，因为rear=5，尾指针已经达到了队列的最大长度，但该队列还未放满，所以这种情况被称为：假溢出。

2.循环队列

为了解决假溢出而导致的队列的空间浪费的问题，我们使用了循环队列。

2.1循环队列的定义

队列的头尾相接的顺序存储结构称为循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。这里我们用数组实现。

2.2循环队列的分析

由上图我们发现，当队列为空时和队列为满时，front=rear，这时当rear==front时，该是判满还是判空呢？

解决方案：

方案一：设置一个计数器，开始时计数器设为0，新元素入队时，计数器加1，元素出队，计数器减1。当计数器==MAXSIZE时，队满；计数器==0时，队空。

这里我们主要讲第二种方法。

方案二：保留一个元素空间，当队尾指针指的空闲单元的后继单元是队头元素所在单元时，队满。

当front指针指向最后一个时，我们如何将front=0呢？

这可以利用除法取余运算（%）来实现。

①队首指针进1：Q->front = (Q->front + 1) % MAXSIZE。

②队尾指针进1：Q->rear = (Q->rear + 1) % MAXSIZE。

③队列长度：(Q->rear - Q->front + MAXSIZE) % MAXSIZE。

 2.3循环队列的实现

2.3.1循环队列的顺序存储结构

typedef int ElemType;   //ElemType的类型根据实际情况而定，这里假定为int
#define MAXSIZE 20  //定义元素的最大个数
/*循环队列的顺序存储结构*/
typedef struct{
    ElemType data[MAXSIZE];
    int front;  //头指针
    int rear;   //尾指针,若队列不空，指向队列尾元素的下一个位置
}SqQueue;

2.3.2循环队列的初始化

int Init_SeQueue(SeQueue *Q)
{
    Q=(SeQueue *)malloc(sizeof(SeQueue));
    if(Q!=NULL)
    {
        Q->front=0;
        Q->rear=0;
    }
    return 1;
}

2.3.3循环队列判队空

int SeQueue_Empty(SeQueue *Q)
{
    return Q->rear==Q->front;
}

2.3.4 循环队列长度

int QueueLength(SeQueue *Q)
{
    return (Q->rear-Q->front+MAXSIZE)%MAXSIZE;
}

2.3.5循环队列入队

int Enter_SeQueue(SeQueue *Q,ElemType e)
{
    if(SeQueue_Full(Q))
    {
        return 0;
    }
 
    Q->data[Q->rear]=e;
    Q->rear=(Q->rear+1)%MAXSIZE;
    return 1;
}

2.3.6循环队列判满

int SeQueue_Full(SeQueue *Q)
{
    return (Q->rear+1)%MAXSIZE==Q->front;
}

2.3.7循环队列出队

int Delete_SeQueue(SeQueue *Q,ElemType e)
{
    if(SeQueue_Empty(Q))
    {
        return 0;
    }
 
    e=Q->data[Q->front];
    Q->front=(Q->front+1)%MAXSIZE;
    return 1;
}

三、队列的链式存储结构

1.链队列的分析 

链队列的分析与顺序队列的分析类似，都需要借用头指针和尾指针，但是为了方便使用我们创建另一个结构体来放置头指针和尾指针以及队列中元素个数。

2.链队列的实现

2.1链队列的存储类型

typedef int QdataType;
 链式结构：表示队列 
typedef struct queuenode
{
	struct queuenode* next;//下个元素的地址
	QdataType val;//队列的信息
}QNode;
 队列的结构 
typedef struct queue
{
	QNode* phead;
	QNode* ptail;
	int size;//对列中的元素个数
}queue;

2.2链队列的初始化

//初始化
void QueueInit(queue* pst)
{
	assert(pst);
	pst->phead = NULL;
	pst->ptail = NULL;
	pst->size = 0;
}

2.3队列的销毁

void QueueDestory(queue* pst)
{
	assert(pst);
	QNode* cur = pst->phead;
	while (cur)
	{
		QNode* Next = cur->next;
		free(cur);
		cur = Next;
	}
	pst->phead = pst->ptail = NULL;
	pst->size = 0;
}

2.4队列的插入

void QueuePush(queue* pst, QdataType x)
{
	assert(pst);
	QNode* NewQNode = (QNode*)malloc(sizeof(QNode));
	//判断申请空间是否有效
	if (NewQNode = NULL)
	{
		perror("malloc fail");
		return ;
	}
	NewQNode->next = NULL;
	NewQNode->val = x;
	//此时队列为空
	if (pst->size = 0)
	{
		pst->phead = pst->ptail = NewQNode;
	}
	else
	{
       pst->ptail->next = NewQNode;
	   pst->ptail = NewQNode;
	}
	pst->size++;
}

2.5队列的删除

void QueuePop(queue* pst)
{
	assert(pst);
	assert(pst->ptail);
	//只有一个节点时
	if (pst->phead = pst->ptail)
	{
		free(pst->phead);
		pst->phead = pst->ptail = NULL;
	}
	//多个节点时
	else
	{
			QNode* next = pst->phead->next;
			free(pst->phead);
			pst->phead = next;
	}
	pst->size--;
}

2.6队列头信息的获取

QdataType QueueFront(queue* pst)
{
	assert(pst);
	assert(pst->ptail);
	return pst->phead->val;
}

2.7队列末信息的获取

QdataType QueueBack(queue* pst)
{
	assert(pst);
	assert(pst->ptail);
	return pst->ptail->val;
}

2.8队列节点数量的多少

int QueueSize(queue* pst)
{
	assert(pst);
	return pst->size;
}

2.9队列判空

bool QueueEmpty(queue* pst)
{
	assert(pst);
	return pst->size==0;
}

3.循环队列使用循环链表实现

typedef struct {
    int *a;
    int phead;
    int tail;
    int k;
} MyCircularQueue;
 
 
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*pst=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    pst->a=(int*)malloc(sizeof(int)*(k+1));
    pst->phead=0;
    pst->tail=0;
    pst->k=k;
    return pst;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
   return obj->tail==obj->phead;
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%(obj->k+1)==obj->phead;
}
 
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
        return false;
        obj->a[obj->tail]=value;
        obj->tail++;
        obj->tail%=(obj->k+1);
        return true;
    
}
 
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else{
        ++obj->phead;
        obj->phead%=(obj->k+1);
        return true;
    }
}
 
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->a[obj->phead];
}
 
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->tail==0?obj->a[obj->k]:obj->a[obj->tail-1];
}
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

四、用栈实现队列

1.分析如何用栈实现队列

仅使用两个栈我们就可以实现先入先出队列：

实现队列最重要的是实现先进先出原则，即我们用栈实现队列最重要的是完成插入与取出，这里我们创建两个栈

一个为：puspst专门用来插入数据。

一个为：popst专门用来出数据。

当我们先后插入1 ，2， 3， 4进入pushst栈时，再将pushst栈的元素插入popst栈中，这时再出栈时的顺序就是1 ，2， 3， 4 

2.栈实现队列 

typedef int STDataType;
 
typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;
void STInit(ST* pst)
{
	assert(pst);
 
	pst->a = NULL;
	// top指向栈顶数据的下一个位置
	pst->top = 0;
 
	// top指向栈顶数据
	//pst->top = -1;
 
	pst->capacity = 0;
}
 
void STDestroy(ST* pst)
{
	assert(pst);
 
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}
 
// 入栈  出栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);
 
	// 扩容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
 
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
 
	pst->a[pst->top] = x;
	pst->top++;
}
 
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
 
	pst->top--;
}
// 取栈顶数据
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
 
	return pst->a[pst->top - 1];
}
 
// 判空
bool STEmpty(ST* pst)
{
	assert(pst);
 
	return pst->top == 0;
}
 
// 获取数据个数
int STSize(ST* pst)
{
	assert(pst);
 
	return pst->top;
}
 
 
typedef struct {
    ST pushst;
    ST popst;
} MyQueue;
 
 
MyQueue* myQueueCreate() {
     MyQueue*obj=( MyQueue*)malloc(sizeof( MyQueue));
    STInit(&(obj->pushst));
    STInit(&(obj->popst));
    return obj;
}
 
void myQueuePush(MyQueue* obj, int x) {
    STPush((&(obj->pushst)),x);
}
 
int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&(obj->popst)))
    {
        while(!(STEmpty(&(obj->pushst))))
        {
        int top=STTop(&(obj->pushst));
        STPush((&(obj->popst)),top);
        STPop(&(obj->pushst));
        }
    }
	return STTop(&(obj->popst));
}
int myQueuePop(MyQueue* obj) {
    int front=myQueuePeek(obj);
    STPop(&(obj->popst));
	return front;
}
bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&(obj->pushst))&&STEmpty(&(obj->popst));
}
 
void myQueueFree(MyQueue* obj) {
    STDestroy(&(obj->pushst));
    STDestroy(&(obj->popst));
    free(obj);
}