C++数据结构——队列

目录
1、简介
2、基本结构
3、基本操作

简介

像栈一样，队列也是一种线性表。它允许在表的一端插入数据，在另一端删除元素。插入元素的这一端称之为队尾。删除元素的这一端我们称之为队头，它的特点是先进先出。

首先我们来思考一下队列这种数据结构使用什么表的创建方式比较好，是头插法？尾插法？之前我们有提到，队列在队头删除元素，在队尾插入元素，如果是头插法，那么在头结点这边进行插入，在另一边进行删除，尾插法恰恰相反。其实这两种方法没有本质上的区别，因为无论使用哪种方法，我们都需要有两个标志能够定位到插入点和删除点，但是，我们在进行尾插法时我们就自带了一个标志，因为每次往后增加结点时，我们需要找到当前的最后一个结点，这时的末尾结点就充当了一个标志“rear”，在头结点处删除，在rear处插入，我们就完成了队列的基本操作。

基本结构

rear标志会随着结点的插入而移动，始终指向末尾结点

而多数教科书或者文章中会是这样的结构

它这里多了一个标志"front"，它有什么作用呢，其实作者认为它的作用跟头结点没什么区别，都是为了找到队头，要说什么本质的区别的话，emmmmm，作者好像没领悟出来，可能是因为在凑结构的时候能凑一对？？
我们接下来的代码将基于这种结构实现。

基本操作

队列的基本操作有入队（push）、出队（pop）、判空（isEmpty）、读取队头元素(getFront）、返回队列大小（getSize）

队列的类型声明

        typedef struct queue* Queue;
typedef struct node* Node;
struct node{
	int element;
	Node next;
};
//队列结构
struct queue{
	Node front;
	Node rear;
    int size;
};

    

入队

        void push(Queue q,int x){
	Node temp=new node;
	temp->element=x;
	temp->next=NULL;//由于我们用的是尾插法，所以我们插入的结点的next必定是指向NULL，
				   //我们也可以换成temp->next=q->rear->next;
	q->rear->next=temp;
	q->rear=temp;  //这两步将rear移动到temp上
	q->size++;
}

    

出队

删除三步走（实际代码就①②两步，觉得不太详细的可以看我关于表的文章），在删除的时候我们还会遇到一个问题，在删除了最后一个元素后我们该怎么办

如图，在删除结点4后，我们只需要把rear标志放到front处就变成了我们初始化队列时的样子

        void pop(Queue q)
{
    if(isEmpty(q))
    	return ;
    Node temp;
    temp=q->front->next;
    q->front->next=temp->next;//删除队头
    if(q->rear==temp)//如果队尾就是我们要删除的元素，就代表已经是最后一个元素了
    	q->rear=q->front;
    delete(temp);//删除的最后记得把内存释放
    q->size--;
}

    

判空

        void isEmpty(Queue q){
	return q->front==q->rear;//队头队尾在一起说明队列为空
}

    

获取队头元素

        int getFront(Queue q){
	return q->front->next->element;
}

    

获取队列长度

        int getSize(Queue q){
	return q->size;
}

    

完整代码

        #include<iostream>
using namespace std;
typedef struct queue* Queue;
typedef struct node* Node;
struct node{
	int element;
	Node next;
};
struct queue{
	Node front;
	Node rear;
	int size;
};
void init(Queue q){
	q->front=q->rear=new node;
	q->front->next=NULL;
	q->size=0;
}
bool isEmpty(Queue q){
	return q->front==q->rear;
} 
void push(Queue q,int x){
	Node temp=new node;
	temp->element=x;
	temp->next=NULL;
	q->rear->next=temp;
	q->rear=temp;
	q->size++;
}
void pop(Queue q)
{
    if(isEmpty(q))
    	return ;
    Node temp=new node;
    temp=q->front->next;
    q->front->next=temp->next;
    if(q->rear==temp)
    	q->rear=q->front;
    delete(temp);
    q->size--;
}

void print(Node head){
	while(head->next){
		cout<<head->next->element<<" ";
		head=head->next;
	}
	cout<<endl;
}
int getFront(Queue q){
	return q->front->next->element;
}
int getSize(Queue q){
	return q->size;
}
int main(){
	Queue q=new queue;
	init(q);
	Node head=new node;
	head=q->front;
	for(int i=0;i<5;i++){	
		push(q,i+1);
	}
	print(head);
	pop(q);
	print(head);
	push(q,20);
	pop(q);
	print(head);
	cout<<getFront(q)<<endl;
	cout<<getSize(q)<<endl;
	return 0;
}

    

原文：https://www.cnblogs.com/yszcode/p/13747443.html