队列应用题

队列应用题

1.队列的顺序存储结构

图像描述

特别提醒:注意头尾指针初始位置,以及队列满时的位置!

image-20220730143027917

队列的顺序储存类型描述

1
2
3
4
5
#define MaxSize 100								//定义队列中元素的最大个数
typedef struct{
int data[MaxSize]; //存放队列指针
int rear,front; //对头元素和队尾指针
}SqQueue;

2.循环队列

1.图像描述

特别提醒:方案一的本质就是牺牲掉一个储存单位来区分是队空还是队满!

image-20220730143502062

2.初始化

1
2
3
4
void InitQueue(SqQueue &Q)
{
Q.front=Q.rear=0; //初始化队首、队尾指针
}

3.判断空

1
2
3
4
5
bool isEmpty(SqQueue &Q)
{
if(Q.front == Q.rear) return true; //队空条件
else return false;
}

4.入队

1
2
3
4
5
6
bool EnQueue(SqQueue &Q,Elemtype x){
if((Q.rear+1)%MaxSize == Q.front ) return false; //队满则报错
Q.data=[Q.rear]=x;
Q.rear=(Q.rear+1)%Maxsize; //队尾指针加1取模
return true;
}

5.出队

1
2
3
4
5
6
bool DeQueue(Squeue &Q,Elemtype &x){
if(Q.rear == Q.front ) return false; //队空则报错
x=Q.data[Q.front];
Q.front=(Q.front+1)%MaxSize; //对头指针加1取模
return true;
}

3.队列的链式储存结构

1.图像描述

不带头节点:

image-20220730144635084

带头节点:

image-20220730144714656

2.队列的链式储存类型描述为

特别提醒:这里需要强加掌握!

1
2
3
4
5
6
7
typedef struct LinkNode{									//链式队列结点
int data;
struct Linknode *next;
}LinkNode;
typedef struct{ //链式队列
linkNode *front,*rear; //队列的队头和队尾指针
}LinkQueue;

3.初始化

1
2
3
4
void InitQueue(LinkQueue &Q){
Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); //建立头结点
Q.front->next =NULL; //初始为空
}

4.判队空

1
2
3
4
bool IsEmpty(LinkQueue &Q){
if(Q.front == Q.rear) return true;
else return false;
}

5.入队

1
2
3
4
5
6
7
void Enqueue(LinkQueue &Q,Elentype x){
LinkNode *s =(LinkNode*)malloc(sizeof(LinkNode));
s>data = x; //创建新结点,插入到表尾
s->next =NULL;
Q.rear->next = s;
Q.rear = s;
}

6.出队

特别提醒:这里需要注意如果删除后变为空队列需要怎么处理!

1
2
3
4
5
6
7
8
9
10
bool DeQueue(LinkQueue &Q,Elentype &x){
if(Q.front == Q.rear) return false;
LinkNode *p=Q.front->next;
x=p->data;
Q.front->next = p->next;
if(Q.rear = p)
Q.rear = Q.front; //若原队列中只有一个结点,删除后变空
free(p);
return true
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!