两个栈构成一个队列算法

梦里梦外; 2022-04-03 16:39 115阅读 0赞

在《剑指Offer》中看到了一个算法：用两个栈实现一个队列。然后我就在思考这个要怎么实现，队列的特点是先进先出，而栈的特点是先进后出，与队列恰好相反。  
  但是如果是两个栈的话就可以实现，用一个栈进行入栈操作，另一个栈进行出栈操作。当要入队列时，便进入S1；当要出队列时，检查S2是否为空，如果为空，则将S1栈中的所有数据出栈并依次存入S2中，然后从S2中出一个元素，如果S2不空，则直接从S2中Pop元素即可。  
代码如下：

#include <stdio.h>
    #define INITSTACK 5//栈空间大小
    
    typedef struct SqStack
    {
        
        char data[INITSTACK];//顺序栈
        int top;//栈顶“指针”
        int base;//栈底“指针”
        int size;//栈的空间大小
    }SqStack;//栈结构体
    
    typedef struct SqQueue
    {
        
        SqStack S1;//构成队列的第一个栈，用于插入数据
        SqStack S2;//构成队列的第二个栈，用于删除数据
    }SqQueue;//队列结构
    
    //初始化栈
    void InitStack(SqStack *S)
    {
        
        S->top = 0;
        S->base = 0;
        S->size = INITSTACK;
    }
    
    //栈实际存放的元素个数
    int RealSizeStack(SqStack S)
    {
        
        return S.top - S.base;
    }
    
    //判断栈是否为空，栈为空，返回1；栈不空，返回0
    int EmptyStack(SqStack S)
    {
        
        if(S.base == S.top)
        {
        
            return 1;
        }
        else
        {
        
            return 0;
        }
    }
    
    //判断栈是否满，栈满返回1；栈不满，返回0
    int FullStack(SqStack S)
    {
        
        if(S.top - S.base == S.size)
        {
        
            return 1;
        }
        else
        {
        
            return 0;
        }
    }
    
    //入栈操作
    int Push(SqStack *S,char ch)
    {
        
        if(S->top - S->base == S->size)
        {
        
            return 0;
        }
        S->data[S->top] = ch;
        S->top++;
        return 1;
    }
    
    //出栈操作
    int Pop(SqStack *S,char *ch)
    {
        
        if(S->base == S->top)
        {
        
            return 0;
        }
        S->top--;
        *ch = S->data[S->top];
        return 1;
    }
    
    //初始化一个队列
    void InitQueue(SqQueue *Q)
    {
        
        InitStack(&Q->S1);
        InitStack(&Q->S2);
    }
    
    //入队列
    void EnQueue(SqQueue *Q,char ch)
    {
        
        int signal = 0;//标志元素是否成功入队列
        int s1_size = 0;//栈S1的实际元素个数
        int s2_size = 0;//栈S2的实际元素个数
        int q_size = 0;//队列的实际元素个数
        if(1 == FullStack(Q->S1))
        {
        
            signal = 0;
        }
        else
        {
        
            s1_size = RealSizeStack(Q->S1);
            s2_size = RealSizeStack(Q->S2);
            q_size = s1_size + s2_size;
            if(INITSTACK > q_size)
            {
        
                Push(&Q->S1,ch);
                signal = 1;
            }
            else
            {
        
                signal = 0;
            }
        }
        if(1 == signal)
        {
        
            printf("elem '%c' enqueue!\n",ch);
        }
        else
        {
        
            printf("elem '%c' enqueue failed!\n",ch);
        }
    }
    
    //出队列
    void DeQueue(SqQueue *Q,char *pch)
    {
        
        int signal = 0;//标志是否成功出队列
        if(0 == EmptyStack(Q->S2))
        {
        
            Pop(&Q->S2,pch);
            signal = 1;
        }
        else
        {
        
            if(0 == EmptyStack(Q->S1))
            {
        
                while(!EmptyStack(Q->S1))
                {
        
                    Pop(&Q->S1,pch);
                    Push(&Q->S2,*pch);
                }
                Pop(&Q->S2,pch);
                signal = 1;
            }
        }
        if(1 == signal)
        {
        
            printf("elem '%c' dequeue!\n",*pch);
        }
        else
        {
        
            printf("DeQueue failed!\n");
        }
    }
    
    int main()
    {
        
        char ch;
        SqQueue Q;
        InitQueue(&Q);
        EnQueue(&Q,'a');
        EnQueue(&Q,'b');
        EnQueue(&Q,'c');
        DeQueue(&Q,&ch);
        EnQueue(&Q,'d');
        EnQueue(&Q,'e');
        EnQueue(&Q,'f');
        EnQueue(&Q,'g');
        EnQueue(&Q,'h');
        EnQueue(&Q,'i');
        DeQueue(&Q,&ch);
        DeQueue(&Q,&ch);
        DeQueue(&Q,&ch);
        DeQueue(&Q,&ch);
        DeQueue(&Q,&ch);
        DeQueue(&Q,&ch);
        return 0;
    }

这个代码写的不具有普适性，但是基本功能都实现了。后续有时间再进行代码的完善！加油！