1.3.32 #
解答 #
在队列的基础上增加一个在队首插入元素的方法即可。
代码 #
Steque.cs #
/// <summary>
/// Steque。
/// </summary>
/// <typeparam name="TItem">Steque 中要存放的元素。</typeparam>
public class Steque<TItem> : IEnumerable<TItem>
{
private Node<TItem> _first;
private Node<TItem> _last;
private int _count;
private class Node<T>
{
public T Item;
public Node<T> Next;
}
/// <summary>
/// 默认构造函数。
/// </summary>
public Steque()
{
_first = null;
_count = 0;
}
/// <summary>
/// 检查栈是否为空。
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
return _count == 0;
}
/// <summary>
/// 返回栈内元素的数量。
/// </summary>
/// <returns></returns>
public int Size()
{
return _count;
}
/// <summary>
/// 将一个元素压入栈中。
/// </summary>
/// <param name="item">要压入栈中的元素。</param>
public void Push(TItem item)
{
var oldFirst = _first;
_first = new Node<TItem>();
_first.Item = item;
_first.Next = oldFirst;
if (oldFirst == null)
{
_last = _first;
}
_count++;
}
/// <summary>
/// 将一个元素从栈中弹出,返回弹出的元素。
/// </summary>
/// <returns></returns>
public TItem Pop()
{
if (IsEmpty())
throw new InvalidOperationException("Stack Underflow");
var item = _first.Item;
_first = _first.Next;
_count--;
if (_count == 0)
{
_last = null;
}
return item;
}
/// <summary>
/// 将一个元素加入队列中。
/// </summary>
/// <param name="item">要入队的元素。</param>
public void Enqueue(TItem item)
{
var oldLast = _last;
_last = new Node<TItem>();
_last.Item = item;
_last.Next = null;
if (IsEmpty())
_first = _last;
else
oldLast.Next = _last;
_count++;
}
/// <summary>
/// 返回栈顶元素(但不弹出它)。
/// </summary>
/// <returns></returns>
public TItem Peek()
{
if (IsEmpty())
throw new InvalidOperationException("Stack Underflow");
return _first.Item;
}
public override string ToString()
{
var s = new StringBuilder();
foreach (var n in this)
{
s.Append(n);
s.Append(' ');
}
return s.ToString();
}
public IEnumerator<TItem> GetEnumerator()
{
return new StackEnumerator(_first);
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
private class StackEnumerator : IEnumerator<TItem>
{
private Node<TItem> _current;
private Node<TItem> _first;
public StackEnumerator(Node<TItem> first)
{
_current = new Node<TItem>();
_current.Next = first;
_first = _current;
}
TItem IEnumerator<TItem>.Current => _current.Item;
object IEnumerator.Current => _current.Item;
void IDisposable.Dispose()
{
_current = null;
_first = null;
}
bool IEnumerator.MoveNext()
{
if (_current.Next == null)
return false;
_current = _current.Next;
return true;
}
void IEnumerator.Reset()
{
_current = _first;
}
}
}
program.cs #
// 见 Steque.cs
var steque = new Steque<string>();
steque.Push("first");
steque.Push("second");
steque.Push("third");
steque.Enqueue("fourth");
Console.WriteLine(steque.ToString());
steque.Pop();
steque.Pop();
steque.Pop();
steque.Pop();
Console.WriteLine(steque.ToString());
steque.Enqueue("first");
steque.Push("zero");
Console.WriteLine(steque.ToString());