目录

队列的逻辑结构

队列的顺序存储结构及实现

如何该进出队的时间性能

假溢出

如何解决假溢出

循环队列入队（伪代码）

循环队列出队（伪代码）

顺序存储代码

队列的链式存储结构及其实现

链式存储代码

循环队列与链队列的比较

队列的逻辑结构

队列：只允许在一端进行插入操作，而另一端进行删除操作的线性表。

空队列：不含任何数据元素的队列。

允许插入（也称入队、进队）的一端称为队尾，允许删除（也称出队）的一端称为队头。

队列的顺序存储结构及实现

如何该进出队的时间性能

放宽队列的所有元素必须存储在数组的前n个单元这一条件 ，只要求队列的元素存储在数组中连续的位置。

设置队头、队尾两个指针

假溢出

假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。

如何解决假溢出

设置循环队列；将存储队列的数组头尾相接。

循环队列入队（伪代码）

循环队列入队伪算法两步完成：
1.将值存入rear所代表的位置
2. rear=rear+1;   
  是否正确？
  正确的写法是：rear=(rear+1)%数组的长度maxsize
  上述写法代表rear后移了一位，即（rear+1)%数组的长度maxsize代表的是rear的下一个元素

循环队列出队（伪代码）

循环队列出队伪算法两步完成：
1.把队头元素保存起来
2.front=(front+1)%数组的长度maxsize

判断队列为空条件：
front==rear

顺序存储代码

代码如下：

#include"stdio.h"
#include"stdlib.h"
#define maxsize 5
typedef struct node
{
	int front,rear;
	int data[maxsize];
}linklist;
void push(linklist *s)
{
	printf("请输入%d个数据",maxsize-1);
	if(((s->rear+1)%maxsize)==s->front)
	exit(0); 
	else
	for(int i=0;idata[s->rear]);
	s->rear=(s->rear+1)%maxsize;
	}
}

void pop(linklist *s)
{
	if(s->rear==s->front)
	{printf("失败"); exit(0);}
	else
	for(int i=0;idata[s->front]);
	s->front=(s->front+1)%maxsize;
	}
	
}

main()
{
	linklist s;
	s.rear=0;s.front=0;
	push(&s);
	pop(&s);
	
} 

队列的链式存储结构及其实现

链式存储代码

代码如下：

#include"stdio.h"
#include"stdlib.h"
typedef struct node
{
	int data;
	struct node *next;
}linklist;
linklist *rear,*front;
int x;
linklist *push(linklist *rear)
{
	linklist *p;
	p=(linklist *)malloc(sizeof(linklist));
	scanf("%d",&p->data);
	p->next=rear->next;
	rear->next=p;
	rear=p;
	puts("成功");
}
int pop(linklist *front,linklist *rear)
{
	linklist *p;
	while(front!=rear)
	{
		p=front->next;
		x=p->data;
		front->next=p->next;
		if(p->next==NULL)
		rear=front;
		free(p);
		return x;
	}
}
main()
{
	linklist *rear,*front;
	front=(linklist *)malloc(sizeof(linklist));
	front->next=NULL;
	rear=front;
	rear=push(rear);
	int x=pop(front,rear);
	printf("%d",x);
} 

循环队列与链队列的比较

时间性能:
循环队列和链队列的基本操作都需要常数时间O (1)。

空间性能:
循环队列：必须预先确定一个固定的长度，所以有存储元素个数的限制和空间浪费的问题。
链队列：没有队列满的问题，只有当内存没有可用空间时才会出现队列满，但是每个元素都需要一个指针域，从而产生了结构性开销。