兩個棧構造一個隊列 || 兩個隊列構造一個棧

這篇文章主要用於理解隊列（Queue）與棧（Stack）的區別與聯系，區別在於隊列（Queue）是先進先出（FIFO），而棧（Stack）是先進後出（FILO）；同樣的，兩則都為線性存儲結構。   一. 兩個棧構造一個隊列：Queue with two stacks（Stack 1：inbox，Stack 2： outbox）   入列操作（EnQueue） inbox壓棧。 出列操作（DeQueue） 判斷inbox為空則拋出InvalidOperationException異常； 否則，將inbox所有數據出棧，並且壓入outbox； outbox出棧一次，並且把數據存入臨時變量temp； 將outbox剩下所有數據出棧重新壓入inbox； 返回temp。 以上為思路，附上C#代碼如下：    

using System;  
using System.Collections.Generic;  
using System.Linq;  
using System.Text;  
  
namespace TestApp.QueueAndStack  
{  
    /// <summary>  
    /// Construct a queue with two stacks: FIFO  
    /// </summary>  
    /// <typeparam name="T"></typeparam>  
    public class Queue2Ss<T>  
    {  
        private Stack<T> inbox = null;  
        private Stack<T> outbox = null;  
  
        /// <summary>  
        /// Initialize the two stacks  
        /// </summary>  
        public Queue2Ss()  
        {  
            inbox = new Stack<T>();  
            outbox = new Stack<T>();  
        }  
  
        /// <summary>  
        /// EnQueue  
        /// </summary>  
        /// <param name="t"></param>  
        public void EnQueue(T t)  
        {  
            inbox.Push(t);  
        }  
  
        /// <summary>  
        /// DeQueue  
        /// </summary>  
        /// <returns></returns>  
        public T DeQueue()  
        {  
            if (inbox.Count == 0)  
            {  
                throw new InvalidOperationException("The queue is empty.");  
            }  
  
            // Pop the values of inbox to outbox  
            while (inbox.Count > 0)  
            {  
                outbox.Push(inbox.Pop());  
            }  
  
            // Get the result  
            T t = outbox.Pop();  
  
            // Push to inbox with the values of outbox   
            while (outbox.Count>0)  
            {  
                inbox.Push(outbox.Pop());  
            }  
  
            return t;  
        }  
  
        /// <summary>  
        /// Clear the whole queue's values  
        /// </summary>  
        public void Clear()  
        {  
            inbox.Clear();  
            outbox.Clear();  
        }  
  
        /// <summary>  
        /// Return the count of queue  
        /// </summary>  
        /// <returns></returns>  
        public int Count()  
        {  
            return (inbox.Count + outbox.Count);  
        }  
    }  
}  

 

  二. 兩個隊列構造一個棧：Stack with two queues（Queue 1： inbox，Queue 2： outbox）   壓棧操作（Push） inbox入列。 出棧操作（Pop） 判斷inbox為空則拋出InvalidOperationException異常； 否則，將inbox數據出列直到剩下最後一個元素為止，並且將出列數據入列到outbox中； inbox出列一次，並且將數據存入臨時變量temp； Swap（inbox，outbox）； 返回temp。 附上C#代碼如下：    

using System;  
using System.Collections.Generic;  
using System.Linq;  
using System.Text;  
  
namespace TestApp.QueueAndStack  
{  
    /// <summary>  
    /// Construct a stack with two queues: FILO  
    /// </summary>  
    public class Stack2Qs<T>  
    {  
        private Queue<T> inbox = null;  
        private Queue<T> outbox = null;  
  
        /// <summary>  
        /// Initialize the two queues  
        /// </summary>  
        public Stack2Qs()  
        {  
            inbox = new Queue<T>();  
            outbox = new Queue<T>();  
        }  
  
        /// <summary>  
        /// Push  
        /// </summary>  
        /// <param name="t"></param>  
        public void Push(T t)  
        {  
            inbox.Enqueue(t);  
        }  
  
        /// <summary>  
        /// Pop  
        /// </summary>  
        /// <returns></returns>  
        public T Pop()  
        {  
            if (inbox.Count == 0)  
            {  
                throw new InvalidOperationException("The stack is empty.");  
            }  
  
            // Dequeue the inbox's values to outbox   
            // until the inbox has only 1 element left  
            while (inbox.Count > 1)  
            {  
                outbox.Enqueue(inbox.Dequeue());  
            }  
  
            // Get the result  
            T t = inbox.Dequeue();  
  
            // Exchange the inbox and the outbox  
            Queue<T> temp = inbox;  
            inbox = outbox;  
            outbox = temp;  
  
            return t;  
        }  
  
        /// <summary>  
        /// Clear the whole stack's values  
        /// </summary>  
        public void Clear()  
        {  
            inbox.Clear();  
            outbox.Clear();  
        }  
  
        /// <summary>  
        /// Return the count of stack  
        /// </summary>  
        /// <returns></returns>  
        public int Count()  
        {  
            return (inbox.Count + outbox.Count);  
        }  
    }  
}  

 

  上面是基於對棧和隊列的理解的基礎上，分別對棧和隊列的實現，當然我們也可以利用C#裡面的線性鏈表分別對Stack和Queue進行實現，有興趣大家可以試試，so easy！媽媽再也不用擔心我不會棧和隊列了！~_~