实现原理：
1、利用Stack的先进后出的特性，实现一个MaxStack，MaxStack中用一个Stack记录当前的值，一个Stack记录当前的最大值。
2、用2个MaxStack实现MaxQueue，其中一个MaxStack记录出栈记录，一个MaxStack记录入栈记录，取2个MaxStack中的最大值作为当前MaxQueue的最大值。
using System;
using System.Data;
using System.Collections;
using System.Collections.Generic; namespace HelloWorld
{
public class MaxStack<T>
{
private Stack<T> data;
private Stack<T> maxStack; public MaxStack()
{
data = new Stack<T>();
maxStack = new Stack<T>();
} public void Push(T element)
{
if (data.Count == )
{
data.Push(element);
maxStack.Push(element);
}
else
{
var current = maxStack.Peek();
var compare = Comparer<T>.Default;
if (compare.Compare(current, element) < )
{
maxStack.Push(element);
}
data.Push(element);
}
} public T Pop()
{
if (this.IsEmpty)
throw new Exception("Queue is empty.");
else
{
var current = data.Pop();
var compare = Comparer<T>.Default;
if (compare.Compare(current, maxStack.Peek()) == )
{
maxStack.Pop();
}
return current;
}
} public bool IsEmpty
{
get
{
return data.Count == ;
}
} public T GetMax()
{
if (maxStack.Count > )
return maxStack.Peek();
else
return default(T);
}
}
}
using System;
using System.Data;
using System.Collections;
using System.Collections.Generic; namespace HelloWorld
{
public class MaxQueue<T>
{
private MaxStack<T> popStack;
private MaxStack<T> pushStack;
public MaxQueue()
{
popStack = new MaxStack<T>();
pushStack = new MaxStack<T>();
} public void Enqueue(T element)
{
pushStack.Push(element);
} public T Dequeue()
{
if (popStack.IsEmpty && pushStack.IsEmpty)
throw new Exception("Queue is empty.");
if (popStack.IsEmpty)
{
while (!pushStack.IsEmpty)
{
var element = pushStack.Pop();
popStack.Push(element);
}
}
return popStack.Pop();
} public T GetMax()
{
Comparer comparer = Comparer.Default;
if (comparer.Compare(popStack.GetMax(), pushStack.GetMax()) > )
{
return popStack.GetMax();
}
else
{
return pushStack.GetMax();
}
}
}
}
using System;
using System.Text; namespace HelloWorld
{
class Program
{
static void Main(string[] args)
{
MaxQueueTest();
} static void MaxQueueTest()
{
MaxQueue<int> queue = new MaxQueue<int>();
SELECT:
var selected = ShowMenu();
switch (selected)
{
case "":
Console.Write("请输入入队值(int):");
var value = Console.ReadLine();
int v = ;
if (int.TryParse(value, out v))
{
queue.Enqueue(v);
Console.WriteLine("输入入队值:{0}后，,当前最大值为:{1}", value,queue.GetMax());
}
goto SELECT;
case "":
try
{
var element = queue.Dequeue();
Console.WriteLine("出队值:{0},当前最大值为:{1}",element,queue.GetMax());
}
catch(Exception ex)
{
Console.WriteLine(ex.Message);
}
goto SELECT;
case "":
break;
default:
Console.WriteLine("输入有误，请重新选择。");
goto SELECT;
}
} static string ShowMenu()
{
MaxQueue<int> queue = new MaxQueue<int>();
Console.WriteLine("*****************************************");
Console.WriteLine("1、入队");
Console.WriteLine("2、出队");
Console.WriteLine("3、退出");
Console.WriteLine("*****************************************");
Console.Write("请选择:");
var selected = Console.ReadLine();
return selected;
}
}
}