90-用两个栈实现一个队列

缺乏、安全感 2022-12-28 12:32 176阅读 0赞

## 如何使用两个栈实现一个队列? ##

首先先书写栈的一些功能

#include<string.h>
    #include<stdlib.h>
    #include<stdio.h>
    #define INITSZIE 10
    typedef int ElemType;
    typedef struct stack
    {
        
    	ElemType *data;//指向存储空间的首地址 栈底指针
    	int       top;//栈顶指针
    	int      size;//栈存储空间的大小，为了扩容准备 
    }Stack;
    
    void InitStack(Stack *st)//初始化栈 
    {
        
    	if(st==NULL) exit(0);
    	st->data=(ElemType *)malloc(sizeof(ElemType)*INITSZIE);
    	if(st->data==NULL) exit(0);
    	st->top=0;//有两种设置 0 -1
    	st->size=INITSZIE; 
    }
    static bool AppendSpace(Stack *st)//申请新空间 扩容 
    {
        
    	ElemType *new_space=(ElemType *)malloc(sizeof(ElemType)*st->size*2);
    	if(new_space==NULL) return false;
    	for(int i=0;i<st->top;++i)
    	{
        
    		new_space[i]=st->data[i]; 
    	}
    	free(st->data);
    	st->data=new_space;
    	st->size*=2;
    	return true;
    }
    
    bool IsFull(Stack *st)//判满 
    {
        
    	return st->top==st->size;	 
    }
    
    bool Push(Stack *st,ElemType val)//增加数据 
    {
        
    	if(st==NULL) exit(0);
    	if(IsFull(st))
    	{
        
    		if(!AppendSpace(st))
    		{
        
    			return false;
    		}
    	}
    	st->data[st->top++]=val;
    	return true;
    }
    bool IsEmpty(Stack *st)//判空 
    {
         
    	return st->top==0; 
    }
    
    bool Pop(Stack *st)//取出数据 
    {
        
    	if(st==NULL) exit(0);
        if(IsEmpty(st))
        {
        
        	return false;
    	}
    	st->top--;
    	return true;
    }
    
    
    //没有通过top返回值返回栈顶元素，而是通过一个参数将栈顶元素返回 
    bool Top(Stack *st,ElemType *val)
    {
        
        if(st==NULL) exit(0);
        if(IsEmpty(st)) return false;
        *val=st->data[st->top-1];
        return true;
    }
    
    void DestroyStack(Stack *st)//销毁 
    {
        
    	if(st==NULL) exit(0);
    	free(st->data);
    	st->data=NULL;
    	st->size=st->top=0;
    }

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

![在这里插入图片描述][20201216225836222.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]  
**接下来实现 两个栈实现的队列**

typedef struct StackQue//定义两个栈实现的队的结构体 
    {
        
    	Stack st1;
    	Stack st2;
    }StackQue;
    
    void InitQue(StackQue *que)//初始化队 
    {
        
    	if(que==NULL) exit(0);
    	InitStack(&que->st1);
    	InitStack(&que->st2);
    		
    }
    
    static void St1ToSt2(StackQue *que)//实现St1ToSt2
    {
        
    	if(que==NULL) exit(0);
    	while(!IsEmpty(&que->st1))
    		{
        
    			ElemType val;
    			Top(&que->st1,&val);
    			Pop(&que->st1);
    			Push(&que->st2,val);
    		}		 
    }
    
    bool PushStackQue(StackQue *que,ElemType data)//入队(从尾入) 
    {
        
    	if(que==NULL) exit(0);
    	if(que->st1.size==que->st1.top&&!IsEmpty(&que->st2))
    	{
        
    		return false;
    	}
    	if(que->st1.size==que->st1.top)
    	{
        
    		St1ToSt2(que);
    	}
    	Push(&que->st1,data);
    	return true;
    }
    
    bool PopStackQue(StackQue *que)//出队(从头出) 
    {
        
    	if(que==NULL) exit(0);
    	if(IsEmpty(&que->st1)&&IsEmpty(&que->st2))
    	{
        
    		return false;
    	}
    	if(IsEmpty(&que->st2))
    	{
        
    		St1ToSt2(que);
    	}
    	Pop(&que->st2);
    	return true;
    }
    
    void DestroyStackQue(StackQue *que)//销毁队列 
    {
        
    	if(que==NULL) exit(0);
        DestroyStack(&que->st1);
        DestroyStack(&que->st1);
    		
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/aa737f5e32c541e09e6749b020e4ac17.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201216230529529.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center
[20201216225836222.png_pic_center]: https://img-blog.csdnimg.cn/20201216225836222.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201216225845820.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY=,size_16,color_FFFFFF,t_70#pic_center