C#数据结构：两栈实现队列，两队列实现栈

立羽

发布于 2023-08-24 15:31:12

15600

代码可运行

文章被收录于专栏：Unity3d程序开发Unity3d程序开发

运行总次数：0

代码可运行

两个栈实现队列：栈实现先进先出

栈1负责队尾，栈2负责队头
每次入队，栈2无元素且栈1无元素，入栈2；否则入栈1
每次出队，栈2有元素，出栈2顶；否则把全部栈1入栈2，再出栈2顶

bool Pop(ref int value)
    {
        if (m_stack2.Count > 0)
        {
            value =  m_stack2.Pop();
            return true;
        }

        while (m_stack1.Count > 0)
        {
            m_stack2.Push(m_stack1.Pop());
        }

        if (m_stack2.Count > 0)
        {
            value = m_stack2.Pop();
            return true;
        }

        return false;
    }

    void Push(int value)
    {
        if (m_stack2.Count == 0 && m_stack1.Count == 0)
        {
            m_stack2.Push(value);
        }
        else
        {
            m_stack1.Push(value);
        }
    }

两个队列实现栈：队列实现先进后出

队1负责插入，队2负责出栈时暂时保存空间。两者存在一个作为出队缓冲，然后1保留1个最为栈顶出去，即身份可以互调
两个队列只存在3种情况：都是空，插入队1；队1空，队2有值，即队2作为操作队列；反之队1有，队2空
出栈：有值的队列依次出队到另一个队列，留一个出栈
入栈：谁不空入谁；都空入队1

bool Pop(ref int value)
   {
       if (m_queue1.Count == 1 && m_queue2.Count == 0)
       {
           value = m_queue1.Dequeue();
           return true;
       }
       else if (m_queue1.Count == 0 && m_queue2.Count == 1)
       {
           value = m_queue2.Dequeue();
           return true;
       }
       else if (m_queue1.Count > 1 && m_queue2.Count == 0)
       {
           while (m_queue1.Count > 1)
           {
               m_queue2.Enqueue(m_queue1.Dequeue());
           }

           value = m_queue1.Dequeue();
           return true;
       }
       else if (m_queue1.Count == 0 && m_queue2.Count  > 1)
       {
           while (m_queue2.Count > 1)
           {
               m_queue1.Enqueue(m_queue2.Dequeue());
           }

           value = m_queue2.Dequeue();
           return true;
       }

       return false;
   }

   void Push(int value)
   {
       if (m_queue1.Count >= 0  && m_queue2.Count == 0)
       {
           m_queue1.Enqueue(value);
       }
       else if (m_queue1.Count == 0 && m_queue2.Count > 0)
       {
           m_queue2.Enqueue(value);
       }
   }