队列的基础操作

怼烎@ 2023-06-19 01:52 12阅读 0赞

*  **一、队列的顺序存储结构**

#define MaxSize 50
    typedef strecu{
        
    	ElemType data[MaxSize];
    	int front,rear
    }SqQueue;
    //基础描述
    循环队列--将队列臆造为一个环状的空间
    初始              Q.front==Q.rear==0;
    入队--队尾指针进1  Q.rear=(Q.rear+1)%MaxSize
    出队--队首指针进1  Q.front=(Q.front+1)%MaxSize
    队列长度          (Q.rear+MaxSize-Q.front)%MaxSize
    队满              (Q.rear+1)%MaxSize==Q.front
    队空  			  Q.front==Q.rear

*  **队列的初始化**

void InitSqQueue(SqQueue &Q){
        
    	Q.front=Q.rear=0;
    }

*  **队列的判空**

bool SqQueueEmpty(SqQueue Q){
        
    	if(Q.front==Q.rear)
    		return true;
    	else
    		return false;
    }

*  **入队**

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;
    	return true;
    }

*  **出队**

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

*  **二、队列的链式存储结构**

typedef struct{
        
    	ElemType data;
    	Struct LinkNode *next;
    }LinkNode;
    typedef struct{
        
    	LinkNode *front,*rear;
    }LinkQueue;

*  **初始化**

void InitQueue(LinkQueue &Q){
        
    	Q.front=Q.rear=(LinkNode *)malloc(SizeOf(LinkNode));//建立头结点
    	Q.front->next=NULL;
    }

*  **队判空**

bool QueueEmpty(LinkQueue Q){
        
    	if(Q.front==Q.rear) return true;
    	else return false;
    }

*  **入队**

bool EnQueue(LinkQueue &Q,ElemType x){
        
    	LinkNode *s;
    	s=(LinkNode *)malloc(SizeOf(LinkNode));
    	s->data=x;
    	s->next=NULL;
    	Q.rear->next=s;
    	Q.rear=s;
    	return true;
    }

*  **出队**

bool DeQueue(LinkQueue &Q,ElemType &x){
        
    	LinkNode *q;
    	q=Q.front->next;
    	x=q.data;
    	Q.front->next=q->next;
    	if(q==Q->rear) Q.rear=Q.front;
    	free(q);
    	return true;
    }

*  **利用两个栈s1、s2来模拟一个队列，实现队列的入队、出队、判断队列是否为空的操作**

//入队
    //若s1不满，则将元素直接入栈s1，若s1已满，s2为空，则将s1元素全部出栈到s2，再将元素入栈
    void EnQueue(SqStack &s1,SqStack &s2,ElemType x){
        
    	if(s1.top!=MaxSize-1){
        
    		pust(s1,x);
    	}
    	else if(s1.top==MaxSize-1&&s2.top==-1){
        
    		while(s1.top!=-1){
        
    			pop(s1,e);
    			push(s2,e);
    		}
    		push(s1,x);
    	}
    	else{
        
    		cout<<"入栈失败！"<<endl;
    	}
    } 
    
    //出队
    //若s2不为空，则将s2中元素出栈，若s2为空，则将s1中全部元素出栈，然后入栈s2，进行出栈
    void Dequeue(SqStack &s1,SqStack &s2,ElemType x){
        
    	if(s2.top!=-1){
        
    		pop(s2,x);
    	}
    	else if(s2.top==-1&&s1.top!=-1){
        
    		while(s1.top!=-1){
        
    			pop(s1,,e);
    			push(s2,e);
    		}
    		pop(s2,x);
    	}
    	else{
        
    		cout<<"出队失败"<<endl;
    	}
    }
    
    //判断队列是否为空
    bool QueueEmpty(SqStack s1,SqStack &s2){
        
    	if(s1.top==-1&&s2.top==-1)
    	 return true;
    	else
    		return false;
    }

*  **利用队列来模拟栈**

//栈判空
    bool StackEmpty(SqQueue q1,SqQueue q2){
        
    	if(QueueEmpty(q1)==NUll)
    		return NULL;
    }
    //入栈
    void push(SqQueue &q1,SqQueue &q2,ElemType x){
        
    	if((q1.rear+1)%MaxSize==0){
        
    		cout<<"栈满，入栈失败"<<endl;
    	}
    	EnQueue(q1,x);
    }
    //出栈
    void pop(SqQueue &q1,SqQueue &q2,ElemType x){
        
    	if(QueueEmpty(q1)==NULL)
    		return;
    	int n=q1.size(q1);
    	while(n!=1){
        //将q1中的元素出队到只剩下一个元素在q1中
    		DeQueue(q1,e);
    		EnQueue(q2,e);
    		n--;
    	}
    	DeQueue(q1,x);
    	while(QueueEmpty(q2)!=NULL){
        //将q2中的元素重新入队到q1
    		DeQueue(q2,e);
    		EnQueue(q1,e);
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，12人围观）

还没有评论，来说两句吧...

相关阅读

相关队列的基本操作

目录一、什么是队列？二、用数组实现队列代码实现：数组实现的缺点：三、用链表实现队列代码实现： -------------------- 一、什么

r囧r小猫/ 2023年09月23日 16:15/ 0 赞/ 114 阅读

相关队列的基础操作

一、队列的顺序存储结构 define MaxSize 50 typedef strecu{ ElemType data[Ma

怼烎@/ 2023年06月19日 01:52/ 0 赞/ 13 阅读

相关顺序队列的基本操作

/\顺序队的基本操作\/ \include <stdio.h> \include <malloc.h> \define MaxSize 100 typedef

逃离我推掉我的手/ 2022年09月20日 12:43/ 0 赞/ 129 阅读

相关链队列的基本操作

将队列的基本运算实现 EnQueue() DeQueue() InitQueue() GetHead() QueueEmpty() QueueLengt

比眉伴天荒/ 2022年05月27日 00:45/ 0 赞/ 208 阅读

相关循环队列的常见操作

与栈相比，队列我个人感觉简单一些，不过对于一般的队列，都是循环队列，这是为了防止内存的浪费，使为队列分配的内存可以循环使用，而且一般动态分配一个长度为n的循环队列的话，真正用

深藏阁楼爱情的钟/ 2022年05月26日 01:26/ 0 赞/ 233 阅读

相关链队列的基本操作

一、链队列的数据类型定义： include<stdio.h> include<stdlib.h> include<assert.h>

素颜马尾好姑娘i/ 2022年04月23日 04:58/ 0 赞/ 306 阅读

相关队列的基本操作！

1.链式队列 //队列结点结构体 typedef struct QNode \{ QElemType data; QNode \next; \}\Queueptr

浅浅的花香味﹌/ 2022年04月11日 08:08/ 0 赞/ 344 阅读

相关循环队列的基本操作

循环队列设置不同队空与队满条件的解决方案为了解决顺序队列假溢出的问题，我们采用的方案是少用一个元素空间，此时的指针状态是队尾指针加1才与队头指针重合，于是此时队满的判定

ゝ一世哀愁。/ 2022年03月22日 03:27/ 0 赞/ 289 阅读

相关顺序队列的基本操作

顺序队列会发生假溢出的情况，具体运行情况请看效果截图，相关代码如下：一、顺序队列的定义： include<stdio.h> include<stdlib

傷城~/ 2022年03月22日 01:55/ 0 赞/ 333 阅读

相关队列的基本操作

include "stdafx.h" include<iostream> using namespace std; typedef struct

￡神魔★判官ぃ/ 2021年06月24日 15:56/ 0 赞/ 448 阅读