C++ 队列（2）指针实现_c++ queue指针

本篇介绍通过链表和指针实现队列。

目录

一、逻辑结构：

二、概述：

三、相关操作：

1.复制构造函数：

2.析构函数：

3.=重载：

4.判空：

5.头节点数据：

6.入队：

7.出队:

8.打印队列数据：

---

一、逻辑结构：

我们使用如下图所示的带尾指针的循环链表结构：

使用该结构是因为我们需要对头和尾进行操作，如果是带头指针的话尾部不好找到，而如果是带尾指针的循环链表，尾的next就是头，这样对两端的操作十分方便。

二、概述：

以下是要实现的功能：

class Queue
{
private:
	class Node//存储数据的节点，由数据和指向下一个节点的指针组成
	{
	public:
		int data;
		Node* next;
        //构造函数
		Node(int newdata = 0, Node* nextptr = NULL) :data(newdata), next(nextptr) {};
	};
	Node* last;
public:
	Queue() :last(NULL) {};//默认构造函数
	Queue(const Queue& origin);//复制构造函数
	~Queue();//析构函数
	Queue& operator=(const Queue& origin);//=重载
 
	bool empty() const;//判空
	void enqueue(int newdata);//入队
	bool dequeue();//出队
	int front() const;//队头数据
	void display() const;//遍历队列
};

三、相关操作：

1.复制构造函数：

Queue::Queue(const Queue& origin)
{
	last = NULL;
	if (!origin.empty())
	{
		last = new Node(origin.last->data);//先给last开辟空间
		Node* orgptr = origin.last->next;//遍历origin的指针
		Node* curptr = last;//遍历当前队列的指针
        //遍历复制
		while (orgptr != origin.last)//遍历到最后一个就停止
		{
			curptr->next = new Node(orgptr->data);//每次开一个新节点
			orgptr = orgptr->next;
			curptr = curptr->next;
		}
		curptr->next = last;
	}
}

代码中已经给出了注释，要注意的一点是我们的循环到origin.last就停止了，这时当前链表的倒数第二个节点的next还是null，所以在while循环之后还要把倒数第二个节点的next指向last。

2.析构函数：

Queue::~Queue()
{
	if (!empty())
	{
		Node* ptr = last->next;//用于遍历的指针
		Node* nextptr = NULL;//存储next
		while (ptr != last)
		{
			nextptr = ptr->next;//把要删除节点的next先记下来,不然删完后就找不到了
			delete ptr;
			ptr = nextptr;
		}
		delete last;
		last = NULL;
	}
}

遍历的指针ptr初始化为last->next，这是为了避免和while循环的条件冲突，如果直接令ptr=last，循环就开始不了了，因此在最后我们还要把没有被放到循环中的last删除。

3.=重载：

Queue& Queue::operator=(const Queue& origin)
{
	if (this != &origin)
	{
		this->~Queue();
		if (!origin.empty())
		{
			last = new Node(origin.last->data);
			Node* orgptr = origin.last->next;
			Node* curptr = last;
			while (orgptr != origin.last)
			{
				curptr->next = new Node(orgptr->data);
				orgptr = orgptr->next;
				curptr = curptr->next;
			}
			curptr->next = last;
		}
	}
	return *this;
}

这个和复制构造函数基本一样，唯一的区别就是一开始的是不是本身的判断和析构函数的调用，如果不判断是不是本身而=右边又是自己的话，在第5行调用析构函数时本身就已经被删除了，无法进行复制，所以要判断一下。如果是本身就不用进行任何操作。

4.判空：

判空条件是尾为空。

bool Queue::empty() const
{
	return (last == NULL);
}

5.头节点数据：

int Queue::front() const
{
	if (empty()) {
		cerr << "empty";
		exit(1);
	}
	else return last->next->data;
}

6.入队：

在队尾加入新数据。

void Queue::enqueue(int newdata)
{
	if (empty())
	{
		last = new Node(newdata);
		last->next = last;
	}
	else
	{
		last->next = new Node(newdata, last->next);
		last = last->next;
	}
}

这里要分队列为空和不为空两种情况，

1、为空时就为last开辟空间存放数据，此时只有一个数据，它既是头又是尾。

2、不为空就把新的节点放在last的next，而这个新节点的next就是原来的last->next，即头指针。

最后再令这个新节点为新的last。

7.出队:

删除头节点。

bool Queue::dequeue()
{
	if (empty()) return false;
	else if (last->next == last) {
		delete last;
		last = NULL;
		return true;
	}
	else {
		Node* newfirst = last->next->next;
		delete last->next;
		last->next = newfirst;
		return true;
	}
}

三种情况：

1、队列为空直接返回false。

2、当队列只有一个数据时直接删除last。

3、当队列有多个元素时就需要调整指针，新的头节点为原来的第二个节点，因此last的next应在删除头节点后指向第二个节点。

8.打印队列数据：

void Queue::display() const
{
	if (!empty())
	{
		Node* ptr = last->next;
		while (ptr != last)
		{
			cout << ptr->data << " ";
			ptr = ptr->next;
		}
		cout << ptr->data << endl;
	}
}