数据结构——队列

た入场券 2022-12-26 13:27 110阅读 0赞

[真香！20张图揭开「队列」的迷雾，一目了然][20]

#### 循环队列 ####

#### 链队列 ####

#### 队列的应用 ####

循环队列代码

#include<stdio.h>
    typedef int ElemType;
    typedef int QElemType;
    typedef int Status;
    #define TRUE  1
    #define FALSE 0
    #define  ERROR 0
    #define  OK 1
    #include<malloc.h> 
    #include<stdlib.h>
    
    //----------循环队列 --顺序存储结构-----------------------
    #define  MAXQSIZE  100    // 最大队列长度+1
    typedef  struct {
        
        ElemType   *base;   // 初始化的动态分配存储空间
        int   front;    // 头指针，若队列不空，指向队列头元素
        int   rear;   // 尾指针，若队列不空，指向队列尾元素的下一个位置
    }  SqQueue;
    void InitQueue(SqQueue &Q)
    {
            // 构造一个空队列Q
        Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
        if(!Q.base) // 存储分配失败
            exit(0);
        Q.front = Q.rear = 0;
    }
    void DestroyQueue(SqQueue &Q)
    {
           // 销毁队列Q，Q不再存在
        if(Q.base)
            free(Q.base);
        Q.base = NULL;
        Q.front = Q.rear = 0;
    }
    int QueueLength(SqQueue &Q)
    {
        
    	return ((Q.rear-Q.front+MAXQSIZE)%MAXQSIZE);
    }
    Status EnQueue(SqQueue &Q, QElemType e)
    {
           // 插入元素e为Q的新的队尾元素
        if((Q.rear + 1) % MAXQSIZE == Q.front) // 队列满
            return ERROR;
        Q.base[Q.rear] = e;
        Q.rear = (Q.rear + 1) % MAXQSIZE;
        return OK;
    }
    Status DeQueue(SqQueue &Q, QElemType &e)
    {
          // 若队列不空，则删除Q的队头元素，用e返回其值，
       // 并返回OK；否则返回ERROR
        if(Q.front == Q.rear) // 队列空
            return ERROR;
        e = Q.base[Q.front];
        Q.front = (Q.front + 1) % MAXQSIZE;
        return OK;
    }
    Status GetHead(SqQueue Q, QElemType &e)
    {
           // 若队列不空，则用e返回Q的队头元素，并返回OK；
        // 否则返回ERROR
        if(Q.front == Q.rear) // 队列空
            return ERROR;
        e = Q.base[Q.front];
        return OK;
    }
    Status QueueEmpty(SqQueue Q)
    {
        
        // 若队列Q为空队列，则返回TRUE；否则返回FALSE
        if(Q.front == Q.rear) // 队列空的标志
            return TRUE;
        else
            return FALSE;
    }
    void traverse(SqQueue &Q)
    {
        
    	int x;
    	x=Q.front;
    	int num=QueueLength(Q);
    	for(int i=0;i<num;i++)
    	{
        
    		printf("%d--",Q.base[(x++)%MAXQSIZE]);
    	}
    }
    
    int main ()
    {
        
    	int n=1,e,q;
    	int temp;
    	int a;
    	SqQueue P;
    	InitQueue(P);
    	printf("队列-----菜单\n"); 
    printf("[ 1]：入队输入 \n[ 2]：出队输入 \n[ 3]：得到队首元素输入\n[ 4]：判断队是否为空 \n");
    	printf("[ 5]： 销毁队 \n[ 6]:求循环队列的长度\n[ 7]:遍历循环队列\n");
    	
    	while(n)
    	{
        
    		printf("输入操作："); 
    		scanf("%d",&a); 
    		switch(a)
    		{
        
    			case 1: printf("入队操作,输入要入队的元素："); 
    					scanf("%d",&e);
    					EnQueue(P, e);
    					break;
    			case 2: printf("出队操作\n"); 
    				   DeQueue(P, q);
    				    printf("当前出队的元素的值为：%d\n",q);
    					break;
    			case 3: GetHead(P, temp);
    				 	printf("输出队首元素为 %d \n",temp);
    				 	break;
    			case 4: if(QueueEmpty(P)) printf("当前队列为空\n");
    			 			else printf("当前队列不空\n"); 
    			 		break;
    			case 5: printf("---正在销毁队列---\n");
    			 		DestroyQueue(P);
    			 		break;
    			case 6:
    						printf("队列的长度为%d \n",QueueLength(P));
    					break;
    			case 7:traverse(P);
    					break;
    			 		
    		}
    			
    	}
    	
     }

链队列：

#include<stdio.h>
    typedef int ElemType;
    typedef int QElemType;
    typedef int Status;
    #define TRUE  1
    #define FALSE 0
    #define  ERROR 0
    #define  OK 1
    #include<malloc.h> 
    #include<stdlib.h>
    typedef struct QNode
    {
          ElemType data;	  //存放队中元素
       struct QNode *next;  //指向下一个结点
    } QNode, *QueuePtr;
    typedef struct
    {
          QNode *front;	  //队头指针
       QNode *rear;	  //队尾指针
    } LinkQueue;
    void InitQueue(LinkQueue &Q)
    {
        
        // 构造一个空队列Q
        if(!(Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode))))
            exit(0);
        Q.front->next = NULL;
    }
    void DestroyQueue(LinkQueue &Q)
    {
            // 销毁队列Q(无论空否均可)
        while(Q.front) {
        
            Q.rear = Q.front->next;
            free(Q.front);
            Q.front = Q.rear;
        }
    }
    void EnQueue(LinkQueue &Q, QElemType e)
    {
          // 插入元素e为Q的新的队尾元素
        QueuePtr p;
        if(!(p = (QueuePtr)malloc(sizeof(QNode)))) //存储分配失败
            exit(0);
        p->data = e;
        p->next = NULL;
        Q.rear->next = p;
        Q.rear = p;
    }
    Status DeQueue(LinkQueue &Q, QElemType &e)
    {
          // 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，
       // 否则返回ERROR
        QueuePtr p;
        if(Q.front == Q.rear)
            return ERROR;
        p = Q.front->next;
        e = p->data;
        Q.front->next = p->next;
        if(Q.rear == p)
            Q.rear = Q.front;
        free(p);
        return OK;
    }
    Status GetHead(LinkQueue Q, QElemType &e)
    {
          // 若队列不空，则用e返回Q的队头元素，并返回OK，
       // 否则返回ERROR
        QueuePtr p;
        if(Q.front == Q.rear)
            return ERROR;
        p = Q.front->next;
        e = p->data;
        return OK;
    }
    
    Status QueueEmpty(LinkQueue Q)
    {
          // 若Q为空队列，则返回TRUE，否则返回FALSE
        if(Q.front->next == NULL)
            return TRUE;
        else
            return FALSE;
    }
    
    int main ()
    {
        
    	int n=1,e,q;
    	int temp;
    	int a;
    	LinkQueue P;
    	InitQueue(P);
    	printf("队列-----菜单\n"); 
    	printf("1：入队输入 \n2：出队输入 \n3：得到队首元素输入\n4：判断队是否为空 \n5： 销毁队 \n");
    	while(n)
    	{
        
    		printf("输入操作："); 
    		scanf("%d",&a); 
    		switch(a)
    		{
        
    			case 1: printf("入队操作,输入要入队的元素："); 
    					scanf("%d",&e);
    					EnQueue(P, e);
    					break;
    			case 2: printf("出队操作\n"); 
    				   DeQueue(P, q);
    				    printf("当前出队的元素的值为：%d\n",q);
    					break;
    			case 3: GetHead(P, temp);
    				 	printf("输出队首元素为 %d \n",temp);
    				 	break;
    			case 4: if(QueueEmpty(P)) printf("当前队列为空\n");
    			 			else printf("当前队列不空\n"); 
    			 		break;
    			case 5: printf("---正在销毁队列---\n");
    			 		DestroyQueue(P);
    			 		break;
    			 		
    		}
    			
    	}
    	
     }

翻转前k个元素算法

#include<stdio.h>
    typedef int ElemType;
    typedef int QElemType;
    typedef int Status;
    #define TRUE  1
    #define FALSE 0
    #define  ERROR 0
    #define  OK 1
    #include<malloc.h> 
    #include<stdlib.h>
    
    
    
    
    
    
    // ------栈的顺序存储结构表示----------
    #define STACK_INIT_SIZE 100 	// 存储空间初始分配量
    #define STACK_INCREMENT 10 	// 存储空间分配增量
    typedef int  ElemType;
    typedef struct {
        
      ElemType *base; 	// 栈底指针
      ElemType *top; 	// 栈顶指针
      int stacksize; 	// 栈空间大小
    } SqStack;
    
    
    void InitStack(SqStack &S)
    {
        
        // 构造一个空栈S
        if(!(S.base = (ElemType *)malloc(STACK_INIT_SIZE 
                                      * sizeof(ElemType))))
            exit(0);     // 存储分配失败
        S.top = S.base;
        S.stacksize = STACK_INIT_SIZE;
    }
    
    void DestroyStack(SqStack &S)
    {
        
        // 销毁栈S，S不再存在
        free(S.base);
        S.base = NULL;
        S.top = NULL;
        S.stacksize = 0;
    }
    
    void Push(SqStack &S, ElemType e)
    {
        
        if(S.top - S.base >= S.stacksize) {
         // 栈满，追加存储空间
            S.base = (ElemType *)realloc(S.base, (S.stacksize 
                  + STACK_INCREMENT) * sizeof(ElemType));
            if(!S.base)
                exit(0);           // 存储分配失败
            S.top = S.base + S.stacksize;
            S.stacksize += STACK_INCREMENT;
        }
        *(S.top)++ = e;
    }
    
    Status Pop(SqStack &S, ElemType &e)
    {
        
        // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；
        // 否则返回ERROR
        if(S.top == S.base)
            {
        
            	printf("此时栈为空，不可以再出栈\n");
    			return ERROR;
    		}
        e = *--S.top;
        
        
        return OK;
    }
    
    Status GetTop(SqStack S, ElemType &e)
    {
        
        // 若栈不空，则用e返回S的栈顶元素，并返回OK；
        // 否则返回ERROR
        if(S.top > S.base) {
        
            e = *(S.top - 1);
            printf("输出栈顶元素为 %d \n",e);
            return OK;
        }
        else
        {
        
        	printf("此时栈为空，得不到栈顶元素\n");
    		return ERROR;
    	}
            
    }
    
    Status StackEmpty(SqStack S)
    {
        
        // 若栈S为空栈，则返回TRUE，否则返回FALSE
        if(S.top == S.base)
            return TRUE;
        else
            return FALSE;
    }
    
    
    
    
    
    
    //----------循环队列 --顺序存储结构-----------------------
    #define  MAXQSIZE  100    // 最大队列长度+1
    typedef  struct {
        
        ElemType   *base;   // 初始化的动态分配存储空间
        int   front;    // 头指针，若队列不空，指向队列头元素
        int   rear;   // 尾指针，若队列不空，指向队列尾元素的下一个位置
    }  SqQueue ;
    void InitQueue(SqQueue &Q)
    {
            // 构造一个空队列Q
        Q.base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
        if(!Q.base) // 存储分配失败
            exit(0);
        Q.front = Q.rear = 0;
    }
    void DestroyQueue(SqQueue &Q)
    {
           // 销毁队列Q，Q不再存在
        if(Q.base)
            free(Q.base);
        Q.base = NULL;
        Q.front = Q.rear = 0;
    }
    Status EnQueue(SqQueue &Q, QElemType e)
    {
           // 插入元素e为Q的新的队尾元素
        if((Q.rear + 1) % MAXQSIZE == Q.front) // 队列满
            return ERROR;
        Q.base[Q.rear] = e;
        Q.rear = (Q.rear + 1) % MAXQSIZE;
        return OK;
    }
    Status DeQueue(SqQueue &Q, QElemType &e)
    {
          // 若队列不空，则删除Q的队头元素，用e返回其值，
       // 并返回OK；否则返回ERROR
        if(Q.front == Q.rear) // 队列空
            return ERROR;
        e = Q.base[Q.front];
        Q.front = (Q.front + 1) % MAXQSIZE;
        return OK;
    }
    Status GetHead(SqQueue Q, QElemType &e)
    {
           // 若队列不空，则用e返回Q的队头元素，并返回OK；
        // 否则返回ERROR
        if(Q.front == Q.rear) // 队列空
            return ERROR;
        e = Q.base[Q.front];
        return OK;
    }
    Status QueueEmpty(SqQueue Q)
    {
        
        // 若队列Q为空队列，则返回TRUE；否则返回FALSE
        if(Q.front == Q.rear) // 队列空的标志
            return TRUE;
        else
            return FALSE;
    }
    
    void Queue_traverse(SqQueue Q)
    {
        
    	int e; 
    	while(QueueEmpty(Q)!=1)
    	{
        e = Q.base[(Q.front++) % MAXQSIZE];
    	printf("-%d",e);
    	}
    	printf("\n");
    	
    }
    int main ()
    {
        
    	int n=1,e,q;
    	int temp;
    	int a;
    	SqQueue P;
    	InitQueue(P);
    	printf("队列-----菜单\n"); 
    	printf("[ 1]：入队输入 \n[ 2]：出队输入 \n[ 3]：得到队首元素输入\n[ 4]：判断队是否为空 \n[ 5]： 销毁队 \n");
    	printf("[ 6]翻转队列的前k个元素\n[ 7]:遍历队列\n");
    	while(n)
    	{
        
    		printf("输入操作："); 
    		scanf("%d",&a); 
    		switch(a)
    		{
        
    			case 1: printf("入队操作,输入要入队的元素："); 
    					scanf("%d",&e);
    					EnQueue(P, e);
    					break;
    			case 2: printf("出队操作\n"); 
    				   DeQueue(P, q);
    				    printf("当前出队的元素的值为：%d\n",q);
    					break;
    			case 3: GetHead(P, temp);
    				 	printf("输出队首元素为 %d \n",temp);
    				 	break;
    			case 4: if(QueueEmpty(P)) printf("当前队列为空\n");
    			 			else printf("当前队列不空\n"); 
    			 		break;
    			case 5: printf("---正在销毁队列---\n");
    			 		DestroyQueue(P);
    			 		break;
    			case 6: printf("---翻转队列前k个元素---\n");
    					printf("初始化队列入队元素个数n：");
    					int x;
    					scanf("%d",&x);
    					 for(int i=0;i<x;i++)
    					 {
        
    					 	printf("输入入队列的元素值：");
    						 scanf("%d",&e);
    					 	EnQueue(P, e);
    					 }
    					
    					printf("输入K:");
    					int k;
    					scanf("%d",&k);
    					
    					SqStack W;
    					InitStack(W);
    			 		for(int j=0;j<k;j++)
    			 		{
        	DeQueue(P, q);
    			 			Push(W, q);
    					 }//将前k个压入栈中 
    					 for(int j=0;j<k;j++)
    			 		{
        	Pop(W, q);
    					 	EnQueue(P, q);
    			 			
    					 }//将栈中的元素进入队列p中 
    					 for(int j=0;j<x-k;j++)
    			 		{
        	DeQueue(P, q);
    					 	EnQueue(P, q);
    			 			
    					 }
    					 Queue_traverse(P);
    			 		break;
    			case 7:Queue_traverse(P);
    					break;
    			 		
    		}
    			
    	}
    	
     }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]

[20]: https://mp.weixin.qq.com/s/oY3MZdJClpKh0Spa0YbxfQ
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70]: /images/20221120/387030609c4043b3ac922026409c6e00.png