Aris

队列

2015/05/14 数据结构
队列的定义

和栈相反，队列(queue)是一种先进先出(first in first out，缩写为FIFO)的线性表，它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中允许插入一端叫做队尾，允许删除一端称为队头。

双端队列是限定插入和删除操作在表的两端进行的线性表。

链队列–队列的链式表示和实现

和线性表类似，队列也可以有两种存储表示。

用链表来表示的队列称为链队列。一个链队列显然需要两个分别指示队头和队尾的指针(分别称为头指针和尾指针)才能被唯一确定。这里，为了操作方便起见，给链队列添加一个头结点，并令头指针指向头结点。由此，空的链队列的判决条件作为头指针和尾指针均指向头结点。

链式队列完整代码（C语言）：

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

//函数结果状态代码
#define OK           1
#define ERROR        0

using namespace std;

typedef int QElemType;     //定义数据类型
typedef int Status;  

//单链表存储结构
typedef struct QNode{
	QElemType data;
	struct QNode *next;
}QNode,*QueuePtr;

typedef struct{
	QueuePtr front;       //队头指针
	QueuePtr rear;        //队尾指针
}LinkQueue;

//初始化队列
Status InitQueue(LinkQueue &Q){
	Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));  //指向队头结点
	if(!Q.front) exit(OVERFLOW);
	Q.front->next=NULL;
	return OK;
}

//插入元素队列
Status EnQueue(LinkQueue &Q,QElemType e){
	QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
	if(!p) exit(OVERFLOW);
	p->data=e;
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
	return OK;
}

//出队列
Status DeQueue(LinkQueue &Q,QElemType &e){
	if(Q.front==Q.rear) return ERROR;
	QueuePtr p=Q.front->next;
	e=p->data;
	Q.front->next=p->next;
	if(Q.rear==p) Q.rear=Q.front;
	free(p);
	return OK;
}

//打印队列
void printQueue(LinkQueue &Q){
	QueuePtr p=Q.front->next;
	while(p!=Q.rear){
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<p->data<<endl;
}

int main(){
	LinkQueue Q;
	InitQueue(Q);
	EnQueue(Q,1);
	EnQueue(Q,2);
	EnQueue(Q,3);
	EnQueue(Q,4);
	EnQueue(Q,5);
	printQueue(Q);
	int e;
	DeQueue(Q,e);
	DeQueue(Q,e);
	printQueue(Q);
	system("pause");
}

链式队列完整代码（C++语言）：

#include <iostream>
using namespace std;

struct ListNode{
	int val;
	struct ListNode *next;
	ListNode(int n):val(n){
		next=NULL;
	}
};

struct Queue{
	ListNode *front;
	ListNode *rear;
	Queue(){
		front=new ListNode(0);
		rear=front;
	}
	void EnterQueue(int n){
		ListNode *temp=new ListNode(n);
		if(front==rear){
			front->next=temp;
			rear=temp;
		}else{
			rear->next=temp;
			rear=temp;
		}
	}
	int DeleQueue(){
		if(front==rear) return -1;
		ListNode *p=front->next;
		int n=p->val;
		if(p==rear)
			rear=front;
		else
			front->next=p->next;
		delete p;
		return n;
	}
	bool empty(){
		return (front==rear);
	}
};

int main(){
	Queue q;
	q.EnterQueue(1);
	q.EnterQueue(2);
	q.EnterQueue(3);
	cout<<q.DeleQueue()<<endl;

	system("pause");
}
循环队列–队列的顺序表示和实现

和顺序栈类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，还需要附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。约定：初始化建空队列时，令front=rear=0，每当插入新的队列尾元素时，”尾指针增1”；每当删除队列头元素时，”头指针增1”，因此非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。

假设当前队列分配的最大空间为6，则当队列处于图3.12 (d) 的状态时，不可再继续插入新的队尾元素，否则会因为数组越界而遭致程序代码被破坏，此时又不宜进行存储分配扩大数组空间，因为队列的实际可用空间并未占满，一个较巧妙的办法是将顺序队列臆造成一个环状的空间，称之为循环队列。

指针和队列元素之间关闭不变，如图3.14（a）所示循环队列中，队列头元素是J3，队列尾元素是J5，之后J6，J7，J8相继插入，则队列空间均被占满。如图3.14（b）所示，此时Q.front=Q.rear；反之，若J2，J4，J5相继从图3.14（a）中队列中删除，是队列呈空状态，如图3.14（c）所示，也存在关系Q.front=Q.rear,因此无法判断队列空间是空还是满。解决办法：少用一个元素空间，约定以”队列头指针在队列尾指针的下一位置上”作为队列呈满状态标志。

如下图所示：

假设数组的存数空间为7，此时已经存放1，a，5,7,22,90六个元素了，如果在往数组中添加一个元素，则rear=front；此时，队列满与队列空的判断条件front=rear相同，这样的话我们就不能判断队列到底是空还是满了；解决这个问题有两个办法：一是增加一个参数，用来记录数组中当前元素的个数；第二个办法是，少用一个存储空间，也就是数组的最后一个存数空间不用，当（rear+1）%maxsiz=front时，队列满；

循环队列完整代码（C语言）：

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

//函数结果状态代码
#define OK           1
#define ERROR        0

#define MAXQSIZE 6       //最大队列长度

using namespace std;

typedef int QElemType;     //定义数据类型
typedef int Status;  

//循环队列的存储结构
typedef struct{
	QElemType *base;       //初始化的动态分配的存储空间
	int front;             //头指针 若队列不空 指向队列头元素
	int rear;              //尾指针 若队列不空 指向队列尾元素的下一个位置
}SqQueue;

//初始化循环队列
Status InitQueue(SqQueue &Q){
	Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
	if(!Q.base) exit(OVERFLOW);
	Q.front=Q.rear=0;
	return OK;
}

//求队列长度
int QueueLength(SqQueue Q){
	return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

//插入元素
Status EnQueue(SqQueue &Q,QElemType e){
	if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;
	Q.base[Q.rear]=e;
	Q.rear=(Q.rear+1)%MAXQSIZE;   //前进方式
	return OK;
}

//出队列
Status DeQueue(SqQueue &Q,QElemType &e){
	if(Q.front==Q.rear) return ERROR;
	e=Q.base[Q.front];
	Q.front=(Q.front+1)%MAXQSIZE; //前进方式
	return OK;
}

//打印队列
void printQueue(SqQueue Q){
	int q;
	q=Q.front;
	int i=1;
	while(q!=Q.rear){
		cout<<Q.base[q]<<" ";
		q=(Q.front+i)%MAXQSIZE;
		i++;
	}
	cout<<endl;
}

int main(){
	SqQueue Q;
	InitQueue(Q);
	EnQueue(Q,1);
	EnQueue(Q,2);
	EnQueue(Q,3);
	EnQueue(Q,4);
	EnQueue(Q,5);
	printQueue(Q);
	int e;
	DeQueue(Q,e);
	printQueue(Q);
	EnQueue(Q,7);
	printQueue(Q);
	system("pause");
}

循环队列完整代码（C++语言）：

#include <iostream>
using namespace std;

struct SqQueue{
	int *vec;
	int front;
	int rear;
	int maxsize;
	SqQueue(){
		maxsize=10;
		vec=new int[maxsize];
		front=rear=0;
	}
	void EnterQueue(int n){
		if((rear+1)%maxsize!=front){     //循环队列已满
			vec[rear]=n;
			rear=(rear+1)%maxsize;
		}
	}
	int DeleQueue(){
		if(rear==front) return -1;       //循环队列空
		int n=vec[front];
		front=(front+1)%maxsize;
		return n;
	}
	bool empty(){
		return (rear==front);
	}
	int getSize(){
		return (rear-front+maxsize)%maxsize;
	}
};

int main(){
	SqQueue sq;
	sq.EnterQueue(1);
	sq.EnterQueue(2);
	sq.EnterQueue(3);
	sq.EnterQueue(4);
	cout<<sq.DeleQueue()<<endl;
	cout<<sq.getSize()<<endl;
	system("pause");
}

Search

    Post Directory