数据结构与算法_线性表_队列_循环队列和链式队列的接口实现

队列可以用链表和数组实现，数组必须为环形，否则造成浪费。

环形队列

判断空：first == rear

判断满：first == (rear + 1) % length

入队：Arr[rear] = 100; rear = (rear + 1) % length

出队：first = (first + 1) % length

#include <iostream>
#include <string>
#include <stack>

using namespace std;
// 环形队列

class CircleQueue
{
public:
	CircleQueue(int size = 8)
	:first(0)
	,rear(0)
	, size_(0)
	,length(size)
	{
		Arr = new int[size];
	}
	~CircleQueue()
	{
		delete[] Arr;
	}
	// 入队 
	void push(int val)
	{
		if (first == (rear + 1) % length)
			expand(length * 2);
		Arr[rear] = val;
		rear = (rear + 1) % length;
		size_++;
	}
	// 出队 
	void pop()
	{
		if (first == rear)
			throw "队空";
		first = (first + 1) % length;
		size_--;
	}

	// 队头 
	int front() const
	{
		if (rear == first)
			throw "queue is empty~!";
		return Arr[first];
	}
	
	// 队尾
	int back() const
	{
		if (first == rear)
			throw "queue is empty~!";
		return Arr[(rear - 1 + length) % length];
	}
	// 队满 
	bool full()
	{
		return first == (rear + 1) % length;
	}

	// 队空 
	bool empty()
	{
		return rear == first;
	}

	// 
	void show() const
	{
		for (int i = first; i != rear ; i = (i + 1)%length)
		{
			cout << Arr[i] << " ";
		}
		cout << endl;
	}

	int size() const
	{
		return size_;
	}
private:
	int *Arr;
	int first;
	int rear;
	int length;
	int size_;
	void expand(int size)
	{
		int *p = new int[size];
		// 不能直接这样拷贝了memcpy(p, Arr, sizeof(int)*length);
		int i = 0;
		int j = first;
		for (; i != rear; i++,j = (j +1 ) % length)
		{
			p[i] = Arr[j];
		}
		delete[] Arr;
		Arr = p;
		length = size;
		rear = i;
		first = 0;
	}
};

int main()
{
	CircleQueue  c1;
	for (size_t i = 0; i < 7; i++)
	{
		c1.push(i);
	}
	c1.show();

	cout << "队尾元素" << c1.back() << endl;
	cout << "队首元素" << c1.front() << endl;

	c1.pop();
	c1.show();
	c1.push(11);
	c1.show();
	system("pause");
	return 0;
}

扩容错误

队列的链表实现

用双向循环链表实现队列比较简单

using namespace std;
class LinkQueue
{
public:
	LinkQueue()
	{
		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_;
		head_ = nullptr;
	}

	void push(int val)
	{
		Node *node = new Node(val);
		node->next_ = head_;
		node->pre_ = head_->pre_;
		head_->pre_->next_ = node;
		head_->pre_ = node;
	}
	// 出队操作 
	void pop()
	{
		Node *p = head_->next_;
		head_->next_ = p->next_;
		p->next_->pre_ = head_;
		delete p;

	}

	// 获取出队元素 
	int front() const
	{
		if (head_->next_ == nullptr)
			throw "queue is empty";
	
		return head_->next_->data_;
	}

	bool empty() const
	{
		return head_->next_ == head_;
	}

	void show() const
	{
		Node *p = head_->next_;
		while (p != head_)
		{
			cout << p->data_ << " ";
			p = p->next_;
		}
		cout << endl;
	}
private:
	struct Node
	{
		Node(int data = 0)
			:data_(data)
			,next_(nullptr)
			,pre_(nullptr)
		{}
		int data_;

		Node *next_;
		Node *pre_;
	};
	Node *head_;
};