4、队列
队列(Queue)是只允许在一段插入另一端删除的线性表
先进先出(FIFO)
4.1、顺序队列
队列定义和初始化
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10
#define ElemType int
#define true 1
#define false 0
//定义一个队列
typedef struct{
ElemType data[MaxSize];
int front,rear;//front 对头 rear 对尾
}SqQueue;
//初始化一个队列
int InitSqQueue(SqQueue *Q){
(*Q).front = (*Q).rear = 0;
return true;
}
//判断队列是否为空
int QueueEmpty(SqQueue Q){
if(Q.rear == Q.front) return true;
else return false;
}
入队 出队 获取队头
//入队操作
int EnQueue(SqQueue *Q,ElemType e){
if((Q->rear+1)%MaxSize == Q->front) return false;//队列已经满了
Q->data[Q->rear] = e; //入队操作
Q->rear = (Q->rear+1)%MaxSize; //队尾指针后移
return true;
}
//出队操作
int DeQueue(SqQueue *Q,ElemType *e){
if(Q->rear == Q->front) return false;//如果队列为空,就出队失败
*e = Q->data[Q->front]; //出队的数据
Q->front = (Q->front+1)%MaxSize; //头头后移
return true;
}
//获取对头元素
int GetHead(SqQueue Q,ElemType *e){
if(Q.rear == Q.front) return false;//如果队头等于对尾为空,获取失败
*e = Q.data[Q.front]; //队头的数据
return true;
}
测试
int main(){
SqQueue Q;
printf("没有初始化队列是否为空:%d\n",QueueEmpty(Q));
InitSqQueue(&Q);
printf("初始化后队列是否为空:%d\n",QueueEmpty(Q));
printf("初始化队列后的队头:%d\n",Q.front);
printf("初始化队列后的队尾:%d\n",Q.rear);
EnQueue(&Q,1);
EnQueue(&Q,2);//入队
printf("入队列后的队尾:%d\n",Q.rear);
ElemType x;
DeQueue(&Q,&x);
printf("出队的元素:%d\n",x);
GetHead(Q,&x);
printf("队头元素:%d\n",x);
return 0;
}
//结果:
没有初始化队列是否为空:0
初始化后队列是否为空:1
初始化队列后的队头:0
初始化队列后的队尾:0
入队列后的队尾:2
出队的元素:1
队头元素:2
4.2、链表队列
定义和初始化
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define true 1
#define false 0
//结点
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}LinkNode;
//链队列定义
typedef struct{
LinkNode *front,*rear;//*front 队头指针, *rear 队尾指针
}LinkQueue;
//初始化带头结点的队列
int InitLinkQueue(LinkQueue *Q){
(*Q).front = (*Q).rear = (LinkNode *)malloc(sizeof(LinkNode));
if((*Q).front == NULL || (*Q).rear == NULL) return false;
(*Q).front->next = NULL;
return true;
}
//初始化不带头结点的队列
int InitLinkQueue1(LinkQueue *Q){
(*Q).front = NULL;
(*Q).rear = NULL;
return true;
}
//带头结点判断是否为空
int IsEmpty(LinkQueue Q){
if(Q.front == Q.rear) return true;
else return false;
}
//不带头结点判断是否为空
int IsEmpty1(LinkQueue Q){
if(Q.front == NULL) return true;
else return false;
}
入队 、出队
//带头结点入队操作
int EnQueue(LinkQueue *Q,ElemType e){
LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
if(p==NULL) return false;//分配内存失败
p->data = e;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
}
//不带头结点入队操作
int EnQueue1(LinkQueue *Q,ElemType e){
LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
if(p==NULL) return false;//分配内存失败
p->data = e;
p->next = NULL;
if(Q->front == NULL){
Q->front = p;
Q->rear = p;
}else{
Q->rear->next = p;
Q->rear = p;
}
}
//带头结点出队操作
int DeQueue(LinkQueue *Q,ElemType *e){
if(Q->front == Q->rear) return false;//队列为空,出队失败
LinkNode *p = Q->front->next;
*e = p->data;
Q->front->next = p->next;
if(Q->rear == p){ //如果出队的元素是对尾元素,需要特殊处理
Q->rear = Q->front;
}
free(p);//释放片
return true;
}
//不带头结点出队操作
int DeQueue1(LinkQueue *Q,ElemType *e){
if(Q->front == Q->rear) return false;//队列为空,出队失败
LinkNode *p = Q->front;
*e = p->data;
Q->front = p->next;
if(Q->rear == p){
Q->front = NULL;
Q->rear =NULL;
}
free(p);
return true;
}
//获取对头元素
int GetHead(LinkQueue Q,ElemType *e){
if(Q.front == Q.rear) return false;//队列为空,出队失败
*e = Q.front->next->data;
return true;
}
测试
int main(){
LinkQueue Q;
InitLinkQueue(&Q);
printf("链队列是否为空:%d \n",IsEmpty(Q));
EnQueue(&Q,11);
EnQueue(&Q,22);
printf("链队列是否为空:%d \n",IsEmpty(Q));
ElemType x;
DeQueue(&Q,&x);
printf("链队列出队:%d \n",x);
ElemType y;
GetHead(Q,&y);
printf("链队列的队头元素:%d \n",y);
return 0;
}
//结果
链队列是否为空:1
链队列是否为空:0
链队列出队:11
链队列的队头元素:22
4.3、双端队列
双端队列:
只允许从两端插入、两端删除的线性表
输入受限的双端队列:
只允许从一段进行插入、两端进行删除的线性表
输出受限的双端队列:
标签:return,队列,ElemType,int,front,rear From: https://www.cnblogs.com/shuisanya/p/16826299.html只允许从两端进行插入、一端进行删除的线性表