队列

2023-11-22 12:15:22

队列

队列的顺序存储结构

队列的顺序实现

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize]; //用静态数组存放队列元素
    int front,rear;//队头指针和队尾指针
}SqQueue;

//初始化队列
void InitQueue(SqQueue &Q){
    //初始时，队头和队尾指针指向0
    Q.rear = Q.front = 0;
}

//判断队列是否为空
bool QueueEmpty(SqQueue Q){
    if(Q.rear == Q.front)//队空条件
        return true;
    else
        return false;
}

void testQueue(){
    //声明一个队列（顺序存储）
    SqQueue Q;
    InitQueue(Q);
    //.....
}

入队操作

bool EnQueue(SqQueue &Q, ElemType x){
	if((Q.rear + 1) % MaxSize == Q.front)//判断队满
        return false;//队满报错
    Q.data[Q.rear] = x;//将x插入队尾
    Q.rear = Q.rear+1;//队尾指针后移
    return true;
}

就算rear==MaxSize，队列也不一定是满的，因为前面还有出队的

循环队列的入队操作

bool EnQueue(SqQueue &Q, ElemType x){
	if((Q.rear + 1) % MaxSize == Q.front)
        return false;//队满报错
    Q.data[Q.rear] = x;//将x插入队尾
    Q.rear = (Q.rear+1)%MaxSize;//队尾指针后移
    return true;
}

出队操作

bool DeQueue(SqQueue &Q, ElemType &x){
    if(Q.rear==Q.front)//判断队空
        return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1)%MaxSize;
    return true;
}

//获得队头元素的值，用x返回
bool GetHead(SqQueue Q, ElemType &x){
    if(Q.rear == Q.front)
        return false;
    x = Q.data[Q.front];
    return true;
}

队列元素个数
```
(rear+MaxSize-front)%MaxSize
```

方案二

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize]; //用静态数组存放队列元素
    int front,rear;//队头指针和队尾指针
    int size;//队列当前的长度
}SqQueue;
//插入成功
size++;
//删除成功
size--;
//此时，判断队满的条件为
size == MaxSize;
//判断队空的条件为
size == 0;

方案三

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize]; //用静态数组存放队列元素
    int front,rear;//队头指针和队尾指针
    int tag;//最近进行的是删除为0，插入1
}SqQueue;//

//每次删除操作成功时，都令tag=0；
//每次插入操作成功时，都令tag=1；
//此时的队满条件
front == rear && tag = 1;
//此时的队空条件
front == reat && tag = 0;

其他出题方法

如果队尾指针指向的是队尾元素

那么在入队操作时
```
Q.rear = (Q.rear + 1)%MaxSize;
Q.data[Q.rear] = x;
```
在初始化的时候，可以让front指向0，让rear指向n-1

判空：(Q.rear+1)%MaxSize == Q.front

判满：1.牺牲一个存储单元 2.增加辅助变量tag或者size

队列的链式实现

typedef struct LinkNode{//链式队列结点    ElemType data;    struct LinkNode *next;}LinkNode;typedef struct{//链式队列    LinkNode *front,*rear;//队列的队头和队尾指针}LinkQueue;//初始化（带头结点）void InitQueue(LinkQueue &Q){    //初始时，front，rear都指向头结点    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));    Q.front ->next = NULL;}//判断队列是否为空（带头结点）bool IsEmpty(LinkQueue Q){	if(Q.front == Q.rear)        return true;    else        return false;}//初始化（不带头结点）void InitQueue(LinkQueue &Q){    //初始时，front，rear都指向NULL    Q.front = NULL;    Q.rear = NULL;}//判空（不带头结点）bool IsEmpty(LinkQueue Q){	if(Q.front == NULL)        return true;    else        return false;}

入队

//带头结点
void EnQueue(LinkQueue &Q, ElemType x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;//新结点插入到rear之后
    Q.rear = s;//修改表尾指针
}

//不带头结点
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *S = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    if(Q.front == NULL){//在空列队中插入第一个元素
        Q.front = s;//修改队头队尾指针
        Q.rear = s;
    }else{
		Q.rear->next = s;//新节点插入到rear结点之后
        Q.reat = s;//修改rear指针
    }
}

出队

//带头结点
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front == Q.rear){
		return false;//空队
    }
    LinkNode *p = Q.front->next;
    x = p->data;//用变量x返回队头元素
    Q.front->next = p->next;//修改头结点的next指针
    if(Q.rear = p)//若此次是最后一个结点出队
        Q.rear = Q.front;//修改rear指针
    free(p);//释放结点空间
    return true;
}

//不带头结点
bool DeQueue(LinkQueue &Q,ElemType &x){
	if(Q.front == NULL)
        return false;//空队
    LinkNode *p = Q.front;//p指向此次出队的结点
    x = p->data;//用变量x返回队头元素
    Q.front->next = p->next;//修改front指针
    if(Q.rear == p){//此次是最后一个结点出队
        Q.front = NULL;//front指向NULL
        Q.rear = NULL;//rear指向NULL
    }
    free(p);//释放结点空间
    return true;
}

队满的条件：链式存储一般不会队满，除非内存不足
队列长度：从front遍历到rear，length++

码农公寓

队列

队列的顺序存储结构

队列的链式实现

相关文章