数据结构笔记四

队列
- 一、队列的逻辑结构
- - 1. 队列的概念
  - 2. 队列的基本操作
  - 3. 队列类的抽象类
- 二、队列的物理结构
- - 1. 队列的顺序结构
  - - （1）顺序存储的三种方式介绍
    - （2）循环队列类的声明
  - 2. 队列的链式结构
  - - （1）队列的链式存储
    - （2）链式队列的声明
- 三、队列的实现
- - 1. 顺序循环队列实现
  - 2.链式队列的实现
  - 3. 顺序实现和链式实现的比较
- 四、队列的应用
- - 代码总结和测试

队列一、队列的逻辑结构 1. 队列的概念

越早到达越早离开，先进先出。
例如：银行储蓄柜前排队，计算机打印管理器中对打印队列的管理。

2. 队列的基本操作

结合生活实际，队列的基本操作如下：

构造类

创建队列create（）：创建一个空的队列

属性类

判断队空isEmpty（）: 空，返回true

读队首元素getHead（）：返回队首元素的值

操纵类

入队enQueue（x）：将x插入队尾，使之成为队尾元素

出队deQueue()：删除队首元素并返回队首元素值

3. 队列类的抽象类

template
class queue {
public:
	virtual bool isEmpty() = 0;
	virtual elemType getHead() = 0;
	virtual void enQueue(cosnt elemType& x) = 0;
	virtual elemType  deQueue() = 0;
	virtual ~queue() {};
};

二、队列的物理结构 1. 队列的顺序结构（1）顺序存储的三种方式介绍

对头位置固定
a. 对头固定在下标0
b. 用一个变量指向队尾位置
c. 队列为空时，队尾位置为-1

缺点：出队时会引起大量数据的向前移动，时间复杂度较高

队头位置不固定
即出队时，队首指针front（指示队首节点的前一位置下标）向后移动
a. 队列初始化时，设front=rear=-1,即队空的标志：front=rear
b. 队满的标志：rear=Maxsize-1

缺点：时间复杂度为 O ( 1 ) O(1) O(1),但出队时会空出前面的位置，造成空间的浪费

循环队列
如何将上一种情况浪费的空间利用起来，即是循环队列所考虑并解决的问题。
我们可以从逻辑上认为单元0就是Maxsize，但rear已经指向最后但是前面还有位置时，便可以“从头入队”。

如何实现这个“转弯”操作呢？
r e a r = ( r e a r + 1 ) % M a x s i z e rear=(rear+1)%Maxsize rear=(rear+1)%Maxsize利用上面的公式便可以实现从数组尾跳到数组头的操作
下面考虑具体操作：
a. 入队操作： r e a r = ( r e a r + 1 ) % M a x s i z e rear=(rear+1)%Maxsize rear=(rear+1)%Maxsize
b. 出队操作： f r o n t = ( f r o n t + 1 ) % M a x s i z e front=(front+1)%Maxsize front=(front+1)%Maxsize
c. 判断队满和队空：
队空： 当队列中只有一个元素时，此时rear和front相邻，rear在front后面。执行出队操作后，front与rear相同，因此队列为空的标志为： f r o n t = = r e a r front==rear front==rear
队满： 当数组中只剩下一个空单元，就是front所指向的单元，执行入队操作后，front与rear相同，！！！和队空时情况相同。
解决方案： “牺牲”一个单元的空间，规定front所指向的单元不能存储元素，只起到标志作用，表示后面一个是队头元素，当还剩一个空单元时表示队列已满。即队满的标志为： ( r e a r + 1 ) % M a x s i z e = = f r o n t (rear+1)%Maxsize==front (rear+1)%Maxsize==front

（2）循环队列类的声明

根据上述说明，给出循环队列类的声明如下

template
class seqQueue :public queue {
private:
	elemType* elem;
	int maxSize;
	int front, rear;
	void doublespace();
public:
	seqQueue(int size = 10) {
		elem = new elemType[size];
		maxSize = size;
		front = rear = 0;
	}
	~seqQueue() { delete[]elem; };
	bool isEmpty() {
		return front == rear;
	}
	elemType getHead() {
		return elem[(front + 1) % maxSize];
	}
	void enQueue(const elemType& x);
	elemType deQueue();
};

2. 队列的链式结构（1）队列的链式存储

由于队列的操作是在队列的两端进行的，不会对队列中的其他元素进行操作，用不带头结点的单链表即可。
其中front指向队首，rear指向队尾。

存储特性分析：

链式存储并不会出现队满的情况，但需考虑队空的情况
队列为空时，单链表中没有节点存在，即收尾均为空指针
出入队均为 O ( 1 ) O(1) O(1)的时间复杂度

（2）链式队列的声明

template
class linkQueue :public queue {
private:
	struct node {
		elemType data;
		node* next;
		node(const elemType& x, node* N = NULL) {
			data = x;
			next = N;
		}
		node() :next(NULL) {}
		~node(){}
	};
	node* front, *rear;
public:
	linkQueue() {
		front = rear = NULL;
	}
	~linkQueue();
	bool isEmpty() {
		return front == NULL;
	}
	elemType getHead() {
		return front->data;
	}
	void enQueue(const elemType& x);
	elemType deQueue();
};

三、队列的实现 1. 顺序循环队列实现

doublespace（）
和线性表的doublespace不同，新建扩大后的数组后将front后的首个元素“搬移”到新数组的1下标位置

template
void seqQueue::doublespace() {
	elemType* tmp = elem;
	elem = new elemType[2 * maxSize];
	for (int i = 1; i < maxSize; ++i) {
		elem[i] = tmp[(front + i) % maxSize];
	}
	front = 0;
	rear = maxSize - 1;
	maxSize *= 2;
	delete tmp;
}

enQueue() 进队操作

template
void seqQueue::enQueue(const elemType& x) {
	//如果数组已经满了，则空间加倍
	if ((rear + 1) % maxSize == front) doublespace();
	rear = (rear + 1) % maxSize;
	elem[rear] = x;
}

deQueue() 出队操作

template
elemType seqQueue::deQueue() {
	front = (front + 1) % maxSize;
	return elem[front];
}

2.链式队列的实现

enQueue（）进队操作

template
void linkQueue::enQueue(const elemType& x) {
	if (front == NULL) {
		front = rear = new node(x);
	}
	else {
		rear->next = new node(x);
		rear = rear->next;
	}
}

deQueue（）出队操作

template
elemType linkQueue::deQueue() {
	node* tmp = front;
	elemType value = tmp->data;
	front = front->next;
	if (front == NULL) rear = NULL;
	delete tmp;
	return value;
}

~linkQueue（）析构操作
一定要注意链式结构的析构(利用兄弟协同法一直删首节点）

template
linkQueue::~linkQueue() {
	node* tmp;
	while (front != NULL) {
		tmp = front;
		front = front->next;
		delete tmp;
	}
}

3. 顺序实现和链式实现的比较

时间：两者都能在常量的时间内完成基本操作，但顺序队列由于采用回绕，使出队和入队处理较为麻烦
空间：链接队列中，每个节点多一个指针字段，但在顺序队列中有大量尚未使用的空间

四、队列的应用代码总结和测试

顺序实现

seqQueue.h

# include
using namespace std;

template
class queue {
public:
	virtual bool isEmpty() = 0;
	virtual elemType getHead() = 0;
	virtual void enQueue(const elemType& x) = 0;
	virtual elemType  deQueue() = 0;
	virtual ~queue() {};
};

template
class seqQueue :public queue {
private:
	elemType* elem;
	int maxSize;
	int front, rear;
	void doublespace();
public:
	seqQueue(int size = 10) {
		elem = new elemType[size];
		maxSize = size;
		front = rear = 0;
	}
	~seqQueue() { delete[]elem; }
	bool isEmpty() {
		return front == rear;
	}
	elemType getHead() {
		return elem[(front + 1) % maxSize];
	}
	void enQueue(const elemType& x);
	elemType deQueue();
};

template
void seqQueue::doublespace() {
	elemType* tmp = elem;
	elem = new elemType[2 * maxSize];
	for (int i = 1; i < maxSize; ++i) {
		elem[i] = tmp[(front + i) % maxSize];
	}
	front = 0;
	rear = maxSize - 1;
	maxSize *= 2;
	delete tmp;
}

template
void seqQueue::enQueue(const elemType& x) {
	//如果数组已经满了，则空间加倍
	if ((rear + 1) % maxSize == front) doublespace();
	rear = (rear + 1) % maxSize;
	elem[rear] = x;
}

template
elemType seqQueue::deQueue() {
	front = (front + 1) % maxSize;
	return elem[front];
}

seqQueue.cpp（测试代码）

#include
#include"seqQueue.h"
using namespace std;

int main() {
	seqQueue s(10);
	for (int i = 0; i < 15; ++i)
		s.enQueue(i);
	while (!s.isEmpty())
		cout << s.deQueue() << " ";
	cout << endl;
	return 0;
}

链式实现
linkQueue.h

#include
using namespace std;

template
class queue {
public:
	virtual bool isEmpty() = 0;
	virtual elemType getHead() = 0;
	virtual void enQueue(const elemType& x) = 0;
	virtual elemType  deQueue() = 0;
	virtual ~queue() {};
};

template
class linkQueue :public queue {
private:
	struct node {
		elemType data;
		node* next;
		node(const elemType& x, node* N = NULL) {
			data = x;
			next = N;
		}
		node() :next(NULL) {}
		~node(){}
	};
	node* front, *rear;
public:
	linkQueue() {
		front = rear = NULL;
	}
	~linkQueue();
	bool isEmpty() {
		return front == NULL;
	}
	elemType getHead() {
		return front->data;
	}
	void enQueue(const elemType& x);
	elemType deQueue();
};

template
void linkQueue::enQueue(const elemType& x) {
	if (front == NULL) {
		front = rear = new node(x);
	}
	else {
		rear->next = new node(x);
		rear = rear->next;
	}
}

template
elemType linkQueue::deQueue() {
	node* tmp = front;
	elemType value = tmp->data;
	front = front->next;
	if (front == NULL) rear = NULL;
	delete tmp;
	return value;
}

template
linkQueue::~linkQueue() {
	node* tmp;
	while (front != NULL) {
		tmp = front;
		front = front->next;
		delete tmp;
	}
}

linkQueue.cpp(测试程序）

#include
#include"linkQueue.h"
using namespace std;

int main() {
	linkQueue s;
	for (int i = 0; i < 15; ++i)
		s.enQueue(i);
	while (!s.isEmpty())
		cout << s.deQueue() << " ";
	cout << endl;
	return 0;
}

运行结果

数据结构笔记四

C/C++/C#相关栏目本月热门文章