队列
2016-12-15 本文已影响13人
c与php
1、队列的定义
队列（Queue）是一种先进先出的线性表（First In Frist Out，简称FIFO）。只允许在表的一端（front）进行删除，另一端（rear）进行插入。
队首（front）：只允许进行删除的一端
队尾（rear）：只允许进行插入的一端
队列中没有元素的时候成为空队列。在空队列中依次加入元素a1,a2,...,an之后，a1是队首元素，an是队尾元素。所以退出队列的次序是a1,a2,...,an，按照先进先出的原则进行。
队列.jpg
2.队列的主要操作
（1）清空队列
（2）判断是否为空
（3）元素的个数
（4）入队列
（5）出队列
（6）取队头元素
3.顺序实现队列
队列数组实现.png
存在问题
设数组长度为M,则：
当front=0，rear=M，再有元素入队时发生溢出----真溢出
当front!=0，rear=M，再有元素入队时发生溢出----假溢出
解决方案
循环队列：把队列设想成环形，让sq[0]接在sq[m-1]之后，若rear+1==M，则令rear=0。
循环队列.png
顺序实现队列
（1）
struct DATA{
string name;
int age;
};
struct SQType
{
DATA data[QUEUELEN];//队列数组
int head;//队头
int tail;//队尾
};
定义了队列结构的最大长度是QUEUELEN，队列结构的数据元素类型DATA，队列结构的数据结构类型SQType。在数据结构SQType中，data为数据元素，head是队首序号，tail是队尾序号。当head=0时，队列为空，当tail=QUEUELEN时表示队列满。
（2）初始化队列数据
<1>按符号常量QUEUELEN指定的大小申请一段内存空间，用来保存队列中的数据。
<2>设置head=0和tail=0，表示一个空栈。
SQType *SQTypeInit()
{
SQType *q;
if(q = new SQType)//申请队列的内存空间
{
q -> head = 0;//队首
q -> tail = 0;//队尾
return q;
}
else
{
return NULL;//返回空
}
}
（3）判断空队列
判断空队列是判断一个队列结构是否为空。如果是空，此时队列可以进行入队操作，不可以进行出队操作。
int SQTypeIsEmpty(SQType *q)
{
return(q -> head == q -> tail);
}
（4）判断满队列
判断满队列就是判断一个队列结构是否为满。满队列不可以进行入队操作，可以进行出队操作
int SQTypeIsFull(SQType *q)
{
return(q -> tail == QUEUELEN);
}
（5）清空队列
void SQTypeClear(SQType *q)
{
q -> head =0;
q -> tail =0;
}
（6）释放空间
释放空间是释放队列结构所占用的内存空间，前面用new关键字分配的内存单元，可以用delete释放。
void SQTypeFree(SQType *q)
{
if(q != NULL) delete q;
}
（7）入队列
<1>判断队尾，如果tail等于QUEUELEN，队列满不能插入数据。
<2>设置tail=tail+1
<3>将入队元素保存到tail指向的位置
int InSQType(SQType *q,DATA data)
{
if(q -> tail == QUEUELEN)
{
cout<<"队列已满，操作失败！！"<<endl;
}
else
{
q -> data[q -> tail++] = data;
return 1;
}
}
（8）出队列
<1>判断队首head，如果head等于tail，则表示队列为空
<2>从队列首部取出队头元素（实际返回队头元素的指针）
<3>修改队首head的序号，指向后一个元素
DATA *OutSQType(SQType *q)
{
if(q -> tail == q -> head)
{
cout<<"队列已空！操作失败！"<<endl;
exit(0);
}
else
{
return &(q -> data[q -> head++]);
}
}
（9）读节点数据
读节点数据就是读队头的数据
DATA *PeekSQType(SQType *q)
{
if(SQTypeIsEmpty(q))
{
cout<<"空对列"<<endl;
return NULL;
}
else
{
return &(q -> data[q -> head]);
}
}
（10）计算队列长度
计算队列长度就是计算该队列中数据节点的个数。用队尾序号减去队首序号。
int SQTypeLen(SQType *q)
{
return(q -> tail - q -> head);
}
源代码：http://pan.baidu.com/s/1qYKZG76
截图：
结果.png
4.链表实现队列
#include <stdio.h>
#include <stdlib.h>
#define Error(str) FatalError(str)
#define FatalError(str) fprintf(stderr, "%s\n", str),exit(1)
typedef int ElementType;
#define MAXQUEUE 10
typedef struct node
{
ElementType data;
struct node* nextNode;
}Node;
typedef struct queue
{
Node* front; //队首指针
Node* rear;//队尾指针
int items;//队列中项目个数
}*ptrQueue;
typedef ptrQueue Queue;
int IsEmpty(Queue q);
int IsFull(Queue q);
Queue CreateQueue(void);
void DisposeQueue(Queue q);
void MakeEmpty(Queue q);
void Enqueue(ElementType x, Queue q);
ElementType Front(Queue q);
void Dequeue(Queue q);
ElementType FrontAndDequeue(Queue q);
int main(void)
{
Queue sqQueue;
sqQueue = CreateQueue();
if(IsEmpty(sqQueue))
printf("创建一个空队列");
int value = 0;
printf("队列中的数据为（front -> rear）: \n");
while(!IsFull(sqQueue))
{
Enqueue(value*value, sqQueue);//入队
printf("%d", value*value);
value++;
}
printf("队列已满\n");
ElementType frontQueue;
frontQueue = Front(sqQueue);
printf("对头元素为： %d\n",frontQueue);
Dequeue(sqQueue);
frontQueue = Front(sqQueue);
printf("执行出队操作Dequeue之后，对头元素是： %d\n",frontQueue);
DisposeQueue(sqQueue);
return 0;
}
/***是否为空***/
int IsEmpty(Queue q)
{
return q -> items == 0;
}
/***是否已满***/
int IsFull(Queue q)
{
return q -> items == MAXQUEUE;
}
/***创建队列***/
Queue CreateQueue(void)
{
Queue q;
q = (Queue)malloc(sizeof(struct queue));
if(NULL == q)
Error("空间不足，队列分配内存失败！");
q -> front = (Node*)malloc(sizeof(Node));
if(NULL == q -> front)
Error("空间不足，队列首节点内存分配失败！");
q -> rear = (Node*)malloc(sizeof(Node));
if(NULL == q -> rear)
Error("空间不足，队列尾节点内存分配失败！");
q -> items = 0;
return q;
}
/***释放队列***/
void DisposeQueue(Queue q)
{
MakeEmpty(q);
free(q);
}
/***使队列为空***/
void MakeEmpty(Queue q)
{
if(q == NULL)
Error("必须先使用CreateQueue创建队列！");
while(IsEmpty(q))
Dequeue(q);
}
/***入队***/
void Enqueue(ElementType x, Queue q)
{
if(IsFull(q))
Error("队列已满");
Node* pnode;
pnode = (Node*)malloc(sizeof(Node));
if(NULL == pnode)
Error("新节点分配内存失败！");
pnode -> data = x;
pnode -> nextNode = NULL;
if(IsEmpty(q))
q -> front = pnode;//队列为空数据插入队首位置
else
q -> rear -> next = pnode;//队列不为空，元素放在队尾指针的下一个位置
q -> rear = pnode;//队列尾指针指向pnode节点
q -> items++;//队列项目数加1
return;
}
/***出队***/
void Dequeue(Queue q)
{
if(IsEmpty(q))
Error("队列本身为空");
Node* pnode;
pnode = q -> rear;
q -> front = q -> front -> nextNode;
free(pnode);
q -> items--;
if(q -> items == 0)
q -> rear = NULL;
return;
}
/***返回队列头元素***/
ElementType Front(Queue q)
{
if(!IsEmpty(q))
return q -> front -> data;
Error("队列为空\n");
return 0;
}
/***返回对头元素并使对头元素出队***/
ElementType FrontAndDequeue(Queue q)
{
ElementType x;
if(IsEmpty(q))
Error("队列为空\n");
else
{
q -> items--;
x =q -> front -> data;
q -> front = q -> front -> nextNode;
}
return x;
}
源代码：http://pan.baidu.com/s/1o8jkZcI
截图：
单链表实现队列.png
3.不使用动态创建内存（malloc）而是申请固定地址来实现队列
typedef struct qq_link_struct
{
struct qq_link_struct *ptr;//相当于nextNode下一个节点
}qq_link_type;
typedef struct qq_struct
{
qq_link_type head;//队列头指针
qq_link_type tail;//队列尾指针
int cnt;//记录队列数据个数
}qq_type;
（1）初始化队列
qq_type* qq_init(qq_type *q_ptr)
{
q_ptr -> head.ptr = &q_ptr -> head;//
q_ptr -> tail.ptr = &q_ptr -> head;//初始时队列为空，q_ptr的头指针。尾指针都指向head
q_ptr -> cnt = 0;
return q_ptr;
}
（2）插入数据
/***队列尾部只能进行插入**/
void qq_put(qq_type *q_ptr,qq_link_type * link_ptr)
{
link_ptr -> ptr = &q_ptr -> head;//link指向插入数据
q_ptr -> tail.ptr -> ptr = link_ptr;//队列尾部插入数据
q_ptr -> tail.ptr = link_ptr;//改变队列尾指针
q_ptr -> cnt++;
}
（3）取出数据
/***队列头部只能取数据***/
void* qq_get(qq_type * q_ptr)
{
qq_link_type *ret_ptr = 0;
if(q_ptr -> cnt > 0 )//cnt大于0队列才有数据可以取出来
{
ret_ptr = q_ptr -> head.ptr;//存放取出的数据
q_ptr -> head.ptr = ret_ptr -> ptr;//改变队列头指针
q_ptr -> cnt--;
if(q_ptr -> cnt ==0)
{
q_ptr -> tail.ptr = &q_ptr -> head;//当队列中没有数据尾指针指向队列头
}
}
}
