C#数据结构之堆栈(Stack)实例详解

namespace 栈与队列{  public interface IStack<T>  {    /// <summary>    /// 返回堆栈的实际元素个数    /// </summary>    /// <returns></returns>    int Count();    /// <summary>    /// 判断堆栈是否为空    /// </summary>    /// <returns></returns>    bool IsEmpty();    /// <summary>    /// 清空堆栈里的元素    /// </summary>    void Clear();    /// <summary>    /// 入栈：将元素压入堆栈中    /// </summary>    /// <param name="item"></param>    void Push(T item);    /// <summary>    /// 出栈：从堆栈顶取一个元素，并从堆栈中删除    /// </summary>    /// <returns></returns>    T Pop();    /// <summary>    /// 取堆栈顶部的元素(但不删除)    /// </summary>    /// <returns></returns>    T Peek();  }}

using System;using System.Text;namespace 栈与队列{  public class SeqStack<T>:IStack<T>  {    private int maxsize;    private T[] data;    private int top;        public SeqStack(int size)     {      data = new T[size];      maxsize = size;      top = -1;    }    #region //接口实现部分    public int Count()     {      return top + 1;    }    public void Clear()     {      top = -1;    }    public bool IsEmpty()     {      return top == -1;    }    public void Push(T item)    {      if (IsFull())      {        Console.WriteLine("Stack is full");        return;      }      data[++top] = item;    }    public T Pop()    {      T tmp = default(T);      if (IsEmpty())      {        Console.WriteLine("Stack is empty");        return tmp;      }      tmp = data[top];      top--;      return tmp;    }    public T Peek()    {      if (IsEmpty())      {        Console.WriteLine("Stack is empty!");        return default(T);      }      return data[top];    }    #endregion    public bool IsFull()     {      return top == maxsize - 1;    }    public override string ToString()    {      StringBuilder sb = new StringBuilder();      for (int i = top;i>=0;i--)      {        sb.Append(data[i] + ",");      }      return sb.ToString().Trim(',');    }      }}

namespace 栈与队列{  public class Node<T>  {    private T data;    private Node<T> next;    public Node(T data, Node<T> next)     {      this.data = data;      this.next = next;    }    public Node(Node<T> next)     {      this.next = next;      this.data = default(T);    }    public Node(T data)     {      this.data = data;      this.next = null;    }    public Node()     {      this.data = default(T);      this.next = null;    }    public T Data {      get { return this.data; }      set { this.data = value; }    }    public Node<T> Next     {      get { return next; }      set { next = value; }    }  }}

using System;using System.Text;namespace 栈与队列{  public class LinkStack<T>:IStack<T>  {    private Node<T> top;    private int num;//节点个数    /// <summary>    /// 顶部节点    /// </summary>    public Node<T> Top     {      get { return top; }      set { top = value; }    }    public LinkStack()     {      top = null;      num = 0;    }    public int Count()     {      return num;    }    public void Clear()     {      top = null;      num = 0;    }    public bool IsEmpty()     {      if (top == null && num == 0)      {        return true;      }      else      {        return false;      }    }    public void Push(T item)     {      Node<T> q = new Node<T>(item);      if (top == null)      {        top = q;      }      else      {        q.Next = top;        top = q;      }      num++;    }    public T Pop()     {      if (IsEmpty())       {        Console.WriteLine("Stack is empty!");        return default(T);      }      Node<T> p = top;      top = top.Next;      num--;      return p.Data;    }    public T Peek()     {      if (IsEmpty())       {        Console.WriteLine("Stack is empty!");        return default(T);      }      return top.Data;    }    public override string ToString()    {      StringBuilder sb = new StringBuilder();      if (top != null)       {        sb.Append(top.Data.ToString() + ",");        Node<T> p = top;        while (p.Next != null)        {                    sb.Append(p.Next.Data.ToString()+ ",");          p = p.Next;        }      }      return sb.ToString();    }  }}

Console.WriteLine("顺序堆栈测试开始...");SeqStack<int> seqStack = new SeqStack<int>(10);seqStack.Push(1);seqStack.Push(2);seqStack.Push(3);Console.WriteLine(seqStack);Console.WriteLine(seqStack.Peek());Console.WriteLine(seqStack);Console.WriteLine(seqStack.Pop());Console.WriteLine(seqStack);Console.WriteLine("链堆栈测试开始...");LinkStack<int> linkStack = new LinkStack<int>();linkStack.Push(1);linkStack.Push(2);linkStack.Push(3);Console.WriteLine(linkStack);Console.WriteLine(linkStack.Peek());Console.WriteLine(linkStack);Console.WriteLine(linkStack.Pop());Console.WriteLine(linkStack);Console.ReadLine();