数据结构之队列

一、队列的定义

队列是一种操作受限的线性表，队列只允许在表的一端进行插入，在表的另一端进行删除。可进行插入的一段称为队尾，可进行删除的一端称为队头。

队列的主要特点就是先进先出。依照存储结构可分为：顺序队和链式队。

二、顺序队列

一开始front(队头)和rear(队尾)都在数组的0号位置，入队时rear往后挪动一位

因为是用数组实现的环形队列，front不能单纯的++，否则越界，出队时，将front后挪动一位

入队时需要先考虑队中是否已满，出队时要考虑队中是否为空

代码实现

成员变量

T* pQue_; //维护指针
int cap_; //空间容量
int front_; //队头
int rear_; //队尾
int size_; //队列元素个数

这里的T是模板

构造函数与析构函数

MyQueue(int size = 20)
	: pQue_(new T[size])
	, front_(0)
	, rear_(0)
	, cap_(size)
	, size_(0)
{}
~MyQueue() {
	delete[] pQue_;
	pQue_ = nullptr;
}

扩容

void expand(int size) {
	int* p = new T[size];
	//这里不能用memcpy(),需要遍历队列，将元素重新赋值到新内存中
	int i = 0;//遍历新数组
	int j = front_;//遍历老数组
	for (; j != rear_; i++, j = (j + 1) % cap_) {
		p[i] = pQue_[j];
	}
	delete pQue_;
	pQue_ = p;
	cap_ = size;
	front_ = 0;
	rear_ = i;
}

这里不能直接用memcpy，因为队头可能不在数组索引为0的位置，需要从front遍历到rear，同样不能单纯的递增，要考虑到数组会越界

入队

void push(T val) {
	if (isFull()) {
		//队满扩容
		expand(cap_ + 10);
	}
	pQue_[rear_] = val;
	rear_ = (rear_ + 1) % cap_;
	size_++;
}
//判断队列是否已经满了
bool isFull() {
	//保证队列中一直空着一个元素来区分队列是否满了
	if ((rear_ + 1) % cap_ == front_) {
		return true;
	}
	return false;
}

先判断队列是否满了，满了的话扩容十个元素的容量

未满直接在队头的索引放元素即可，别忘了将容纳元素数量++

出队

void pop() {
	//队列为空抛异常
	if (empty()) {
		throw "queue is empty";
	}
	front_ = (front_ + 1) % cap_;
	size_--;
}
bool empty() const {
	if (front_ == rear_) {
		return true;
	}
	return false;
}

队列为空抛异常，否则将队头往后挪一位就可以

链式队列

采用双向循环链表实现

结点结构体

struct Node
{
	Node(int data = 0)
		: data_(data)
		, next_(nullptr)
		, pre_(nullptr)
	{}
	int data_;
	Node* next_;
	Node* pre_;
};

成员变量

Node* head_;
int size_;

构造函数与析构函数

LinkQueue():size_(0) {
	head_ = new Node;
	head_->next_ = head_;
	head_->pre_ = head_;
}
~LinkQueue() {
	Node* p = head_->next_;
	while (p != head_) {
		head_->next_ = p->next_;
		p->next_->pre_ = head_;
		delete p;
		p = head_->next_;
	}
	delete head_;
}

构造函数需要将头结点的next指向头，pre指向头(双向循环列表)

析构函数删除结点是每次删除链表的第一个结点，将头结点的next指向被删结点的下一结点，被删结点的下一结点的pre指向被删结点，循环结束条件为 != 头结点，循环结束后只剩头结点了，直接删除

入队

void push(int val) {
	Node* tem = new Node(val);
	tem->next_ = head_;
	tem->pre_ = head_->pre_;
	head_->pre_->next_ = tem;
	head_->pre_ = tem;
	size_++;
}

尾插在链表中，改变指向顺序要记得先变新结点，再变老结点

出队

void pop() {
	Node* p = head_->next_;
	head_->next_ = p->next_;
	p->next_->pre_ = head_;
	delete p;
	size_--;
}

出队和析构原理是一样的，删除第一个结点

获取队头&队尾元素

//获取队头元素
int front() const {
	if (head_->next_ == head_) {
		throw "queue is empty!";
	}
	return head_->next_->data_;
}
//获取队尾元素
int rear() const {
	if (head_->next_ = head_) {
		throw "queue is empty!";
	}
	return head_->pre_->data_;
}

判断队列为空的依据都是head->next = head，双向循环链表因为可以从头结点直接访问到尾结点

访问队头元素和队尾元素时间复杂度都是O(1)

两个栈实现一个队列

实现原理：s1用来入队的，s2用来出队的，出队时先把s1出栈的元素入栈到s2，再由s2出栈，这样就实现了先进先出，后进后出的进出顺序了

代码：

class TwoStack2Queue 
{
public:
	//入队
	void push(int x) {
		s1.push(x);
	}
	//出队
	int pop() {
		if (s2.empty()) {
			while (!s1.empty()) {
				s2.push(s1.top());
				s1.pop();
			}
		}
		int val = s2.top();
		s2.pop();
		return val;
	}
	//获取队头元素
	int peek() {
		if (s2.empty()) {
			while (!s1.empty()) {
				s2.push(s1.top());
				s1.pop();
			}
		}
		return s2.top();
	}
	//判断队列是否为空
	bool empty() {
		return s1.empty() && s2.empty();
	}
private:
	stack<int>s1;
	stack<int>s2;
};

如果两个栈都为空，队列才为空