数据结构-----------栈和队列后续

1 队列

1.1概念与结构

概念：只允许在一端进行插入数据操作，在另一端进行删除元素特殊的线性表，队列具有先进先出的性质

入队列：进行插入操作的的一端叫做队尾

出队列：进行删除操作的一端叫做队头

下面我们来看一下队列的实现队列其实跟单链表是差不多的只不过队列只允许在队尾插入数据哎对头进行删除等操作

typedef int SlDatatype;

typedef struct Quenenode {
	SlDatatype data;
	struct Quenenode* next;
	
}quenen;

typedef struct quene {
	quenen* phead;
	quenen* tail;
	int size;
}que;

首先要声明一个结构体结点里面有数据和指向下一个结点的指针，后面要创建队列里面要包含一个头指向队头，然后让尾指向队尾，size是队伍里面的有效数据。

初始化：

void qinit(que* pq)
{
	assert(pq);
	pq->phead = pq->tail = NULL;
	pq->size = 0;
}

首先让tou和尾都指向空然后size的数据为0；

队列的销毁

void destoryque(que* pq)
{
	assert(pq);
	assert(!quemptu(pq));
	quenen *head = pq->phead;
	while (head)
	{
		quenen* next = head->next;
		free(head);
		head = next;
	}
	pq->phead = pq->tail = NULL;
	pq->size = 0;
}

我们像操作系统申请的空间最后都需要释放掉首先定义一个指针接受头然后去遍历去销毁最后让头和尾都指向空把size的大小变成0；

入队

void inserque(que* pq, SlDatatype x)
{
	assert(pq);
	quenen* newcode = (quenen*)malloc(sizeof(quenen));
	if(newcode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newcode->data = x;
	newcode->next = NULL;
	if (pq->phead == NULL)
	{
		pq->phead = pq->tail = newcode;
	}
	else
	{
		pq->tail->next = newcode;
		pq->tail = pq->tail->next;
	}
	pq->size++;
}

首先我们要去malloc一个空间然后判断队列是否为空如果为空的话对头和队尾指向的都是同一个地方如果不是的话就让队尾的下next指向我们申请的一个结点，然后让tail往后走，然后插入一个让size++这样就可以拿到队伍的有效数据；

判断队列是否为空

bool quemptu(que* pq)
{
	assert(pq); 
	return pq->phead == NULL;
}

如果对头为空的话那么这个队列就为空；

查找队列有效个数

int quenesize(que* pq)
{ 
	return pq->size;
}

因为我们在插入数据的时候就对size进行了操作所以这里面直接return size的大小就是队列的个数

出队列

void popqueue(que* pq)
{
	assert(pq);
	assert(!quemptu(pq));
	if (pq->phead == pq->tail)
	{
		free(pq->phead);
		pq->phead = pq->tail = NULL;
	}
	else
	{
		quenen* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

首先要判断队列是否为空，然后如果头和尾指向一个地方直接free对头然后让对头和队尾指向空

如果不是指向同一个地方就定义一个指针让他接受头结点的下一个位置然后去释放头结点在让头结点走到下一个节点的位置然后又size有效数据减减；

取对头

SlDatatype  datafront(que* pq)
{
	assert(pq);
	assert(!quemptu(pq));
	return pq->phead->data;
}

因为队列的性质所以取对头直接取头结点里面的数据就行了

取队尾数据

SlDatatype databack(que* pq)
{
	assert(pq);
	assert(!quemptu(pq));
	return pq->tail->data;
}