queue.cpp

来自「这是关于二叉树的建立」· C++ 代码 · 共 67 行

#include <iostream.h>
#include <malloc.h>
#include <stdlib.h>
#include "Queue.h"

//置空队
void InitQueue(LinkQueue *Q)
{
	Q->front = Q->rear = NULL;
}

//判队空
int QueueEmpty(LinkQueue *Q)
{
	return Q->front == NULL && Q->rear == NULL;
}

//入队
void EnQueue(LinkQueue *Q,QDataType x)
{//将元素x插入链队列尾部
//	QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申请新结点
	LinkQueue *p = new LinkQueue;
	p->data = x;
	p->rear = NULL;
	if(QueueEmpty(Q))
		Q->front = Q->rear = p;  //将x插入空队列
	else
	{ //x插入非空队列的尾
		Q->rear->rear = p;     //*p链到原队尾结点后
		Q->rear = p;           //队尾指针指向新的尾
	}
}

//出队
QDataType DeQueue (LinkQueue *Q)
{
	QDataType x;
	LinkQueue *p;
	if(QueueEmpty(Q))
	{
		cout<<"Queue underflow!";//下溢
		exit(1);
	}		
	else
	{
		p = Q->front;                   //指向对头结点
		x = p->data;                    //保存对头结点的数据
		Q->front = p->rear;             //将对头结点从链上摘下
		if(Q->rear == p)//原队中只有一个结点，删去后队列变空，此时队头指针已为空
			Q->rear = NULL;
		free(p);   //释放被删队头结点
		return x;  //返回原队头数据
	}
}

//取队头元素
QDataType QueueFront(LinkQueue *Q)
{
	if(QueueEmpty(Q))
	{
		cout<<"Queue if empty!";
		exit(1);
	}
	else
		return Q->front->data;
}