栈

什么是栈？

栈和顺序表、链表一样，也是存储逻辑关系为“一对一”的数据。
和顺序表、链表不一样的是，栈的存和取有限制：

• 一端封闭，一端开口，只能从开口处存取数据
• 存取遵循“先进后出”的原则，即最先进栈的元素最后出栈

因此，栈是只能从一端存取数据的先进后出的数据结构。
开口的一端叫栈顶，封闭的一端叫栈底。向栈中添加数据叫进栈，从栈中取数据叫出栈。

栈的实现

栈主要有两种实现方式：

• 顺序栈：采用顺序存储结构
• 链栈：采用链式存储结构

通用接口

因为栈有不同的实现，所以定义一个接口，可以根据接口实现不同的栈

public interface IStack<T>
{ 
    /// <summary>
    /// 栈内元素数量
    /// </summary>
    int Count { get; }
    /// <summary>
    /// 栈是否为空
    /// </summary>
    bool IsEmpty { get; }
    /// <summary>
    /// 向栈中添加数据
    /// </summary>
    /// <param name="elem"></param>
    void Push(T elem);
    /// <summary>
    /// 从栈顶取出数据
    /// </summary>
    /// <returns></returns>
    T Pop();
    /// <summary>
    /// 查询栈顶数据，不取出
    /// </summary>
    /// <returns></returns>
    T Peek();
}

顺序栈

顺序栈采用动态顺序表实现。
我们知道，从动态顺序表的末尾添加和移除元素是最快的，为O(1)。因此，入栈操作就是向顺序表末尾添加元素，出栈操作就是从顺序表末尾移除元素。

using System.Text;

public class SeqStack<T>: IStack<T>
{
    private DynamicSeqList<T> list;
    public int Count { get { return list.Count; } }

    public bool IsEmpty { get { return list.Count <= 0; } }

    public SeqStack(int capacity)
    {
        list = new DynamicSeqList<T>(capacity);
    }

    public SeqStack()
    {
        list = new DynamicSeqList<T>();
    }

    public void Push(T elem)
    {
        list.Add(elem);
    }

    public T Pop()
    {
        return list.RemoveAt(list.Count - 1);
    }

    public T Peek()
    {
        return list[list.Count - 1];
    }

    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();
        sb.Append("[");
        for (int i = 0; i < list.Count; i++)
        {
            sb.Append(list[i].ToString());
            if (i < list.Count - 1)
            {
                sb.Append(",");
            }
        }
        sb.Append("]Top");
        return sb.ToString();
    }
}

链栈

链栈采用单链表实现。
我们知道，从单链表的表头添加和移除元素是最快的，为O(1)。因此，入栈操作就是从表头添加元素，出栈操作就是从表头移除元素。

using System.Text;

public class LinkStack<T> : IStack<T>
{
    private SingleLinkList<T> list;
    public int Count { get { return list.Count; } }

    public bool IsEmpty { get { return list.Count <= 0; } }

    public LinkStack()
    {
        list = new SingleLinkList<T>();
    }

    public void Push(T elem)
    {
        list.AddFirst(elem);
    }

    public T Pop()
    {
        return list.RemoveFirst();
    }

    public T Peek()
    {
        return list.GetFirst();
    }

    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();
        sb.Append("Top:");
        for (int i = 0; i < list.Count; i++)
        {
            var elem = list.Get(i);
            sb.Append(elem.ToString());
            sb.Append("->");
        }
        sb.Append("Null");
        return sb.ToString();
    }
}