重生之数据结构与算法----队列&栈
简介上文说到，数据结构只有两种。其它的数据结构都是它的整花活。
[*]栈
栈只能在表的一端（称为栈顶）进行插入和删除操作，遵循 “后进先出”（Last In First Out，LIFO）的原则。就像生活中的一摞盘子，最后放上去的盘子会最先被拿走
[*]队列
它只允许在表的一端进行插入操作（队尾），在另一端进行删除操作（队头），遵循 “先进先出”（First In First Out，FIFO）的原则。类似于生活中排队买票，先排队的人先买到票离开队列。
用链表实现stack
public class MyLinkedStack<T>()
{
public static void Run()
{
var stack = new MyLinkedStack<string>();
stack.Push("aaaa");
stack.Push("bbbb");
stack.Push("cccc");
stack.Push("dddd");
while (stack.Count > 0)
{
Console.WriteLine(stack.Pop());
}
}
private LinkedList<T> _linked = new LinkedList<T>();
/// <summary>
/// 入栈
/// O(1)
/// </summary>
/// <param name="item"></param>
public void Push(T item)
{
_linked.AddFirst(item);
}
/// <summary>
/// 出栈
/// O(1)
/// </summary>
/// <returns></returns>
public T Pop()
{
var first = _linked.First;
_linked.RemoveFirst();
return first.Value;
}
/// <summary>
/// 查看栈顶
/// </summary>
/// O(1)
/// <returns></returns>
public T Peek()
{
return _linked.First.Value;
}
public int Count { get { return _linked.Count; } }
}用链表实现queue
public class MyLinkedQueue<T>
{
public static void Run()
{
var queue = new MyLinkedQueue<string>();
queue.Enqueue("aaa");
queue.Enqueue("bbb");
queue.Enqueue("ccc");
queue.Enqueue("ddd");
while (queue.Count > 0)
{
Console.WriteLine(queue.Dequeue());
}
}
private LinkedList<T> _linked = new LinkedList<T>();
/// <summary>
/// 入列
/// </summary>
/// <param name="item"></param>
public void Enqueue(T item)
{
_linked.AddFirst(item);
}
/// <summary>
/// 出列
/// </summary>
/// <returns></returns>
public T Dequeue()
{
var last= _linked.Last;
_linked.RemoveLast();
return last.Value;
}
/// <summary>
/// 查看队列顶
/// </summary>
/// <returns></returns>
public T Peek()
{
return _linked.First.Value;
}
public int Count { get { return _linked.Count; } }
}用数组实现stack
public class MyArrayStack<T>()
{
public static void Run()
{
var stack = new MyLinkedStack<string>();
stack.Push("aaaa");
stack.Push("bbbb");
stack.Push("cccc");
stack.Push("dddd");
while (stack.Count > 0)
{
Console.WriteLine(stack.Pop());
}
}
private List<T> _list=new List<T>();
/// <summary>
/// 入栈
/// O(1)
/// </summary>
/// <param name="item"></param>
public void Push(T item)
{
_list.Add(item);
}
/// <summary>
/// 出栈
/// O(1)
/// </summary>
/// <returns></returns>
public T Pop()
{
var v = _list;
_list.RemoveAt(_list.Count - 1);
return v;
}
/// <summary>
/// 查看栈顶
/// </summary>
/// O(1)
/// <returns></returns>
public T Peek()
{
return _list;
}
public int Count { get { return _list.Count; } }
}用数组实现queue
由于queue先进先出的特性，list头部增删元素的复杂度是O(N),不符合性能要求，我们可以使用前文介绍的环形数组，来实现list头部增删的O(1)
public class MyArrayQueue<T>
{
public static void Run()
{
var queue = new MyArrayQueue<string>();
queue.Push("aaaa");
queue.Push("bbbb");
queue.Push("cccc");
queue.Push("dddd");
while (queue.Count > 0)
{
Console.WriteLine(queue.Pop());
}
}
private CircularArray<T> _list = new CircularArray<T>();
/// <summary>
/// 入栈
/// O(1)
/// </summary>
/// <param name="item"></param>
public void Push(T item)
{
_list.AddFirst(item);
}
/// <summary>
/// 出栈
/// O(1)
/// </summary>
/// <returns></returns>
public T Pop()
{
var v = _list.GetLast();
_list.RemoveLast();
return v;
}
/// <summary>
/// 查看栈顶
/// </summary>
/// O(1)
/// <returns></returns>
public T Peek()
{
return _list.GetFirst();
}
public int Count { get { return _list.Count; } }
}队列的变种：双端队列
所谓双端队列，主要是比普通队列，多一个出入口,可以从队列的两头进行插入，删除。但也破坏了先进先出的原则。
日常场景使用不多。只有 Python用得多一些，因为Python标准库没有提供内置的栈和队列，一般会用双端队列来模拟标准队列。
public interface IMyQueue<T>
{
/// <summary>
/// 从头入列
/// </summary>
/// <param name="item"></param>
void EnqueueFirst(T item);
/// <summary>
/// 从头出列
/// </summary>
/// <param name="item"></param>
/// <returns></returns>
T DequeueFirst(T item);
/// <summary>
/// 从尾入列
/// </summary>
void EnqueueLast();
/// <summary>
/// 从头出列
/// </summary>
/// <returns></returns>
T DequeueLast();
}实现比较简单，不再重复，参考普通队列思路即可。链表/环形数组均可实现。
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]