当前位置:编程学习 > C#/ASP.NET >>

两个栈构造一个队列 || 两个队列构造一个栈

这篇文章主要用于理解队列(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!妈妈再也不用担心我不会栈和队列了!~_~
 
补充:软件开发 , C# ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,