数据结构（C#语言版）——栈和队列

现在的位置: 首页 > 综合 > 正文

数据结构（C#语言版）——栈和队列

2011年10月12日 ⁄ 综合 ⁄ 共 2019字 ⁄ 字号小中大 ⁄ 评论关闭

文章目录

栈和队列是计算机中常用的两种数据结构，是操作受限的线性表。栈的插入和删除等操作都在栈顶进行，它是先进后出的线性表。队列的删除、查找等操作在队头进行，而插入操作在队尾进行，它是先进先出的线性表。与线性表一样，栈和队列也有顺序存储与链式存储两种方式。

栈

public interface IStack<T> {
    /// <summary>
    /// 获取栈的长度
    /// </summary>
    int Count { get; }
  
    /// <summary>
    /// 清空栈
    /// </summary>
    void Clear();
  
    /// <summary>
    /// 将一个数据压入栈
    /// </summary>
    /// <param name="value"></param>
    void Push(T value);
  
    /// <summary>
    /// 将一个数据弹出栈
    /// </summary>
    /// <returns></returns>
    T Pop();
  
    /// <summary>
    /// 获取栈顶部的数据，但不弹出
    /// </summary>
    /// <returns></returns>
    T Peek();
}

顺序栈

public class SequenceStack<T> : IStack<T> {
    private const int Step = 16;
    private int _capacity;
    private int _top = -1;
    private T[] _datas;
  
    public SequenceStack() : this(Step) {}
  
    public SequenceStack(int capacity) {
        this._capacity = capacity;
        this._datas = new T[this._capacity];
    }
  
    public int Count {
        get { return this._top + 1; }
    }
  
    public void Clear() {
        this._top = -1;
    }
  
    public void Push(T value) {
        if(this._top+1>=this._datas.Length) {
            this._capacity += Step;
            T[] temps = new T[this._capacity];
            for(int i = 0; i < this._datas.Length; i++) {
                temps[i] = this._datas[i];
            }
            this._datas = temps;
        }
        this._datas[++this._top] = value;
    }
  
    public T Pop() {
        return this._datas[this._top--];
    }
  
    public T Peek() {
        return this._datas[this._top];
    }
}

链栈

public class StackNode<T> {
    private StackNode<T> _next;
    private T _value;
  
    public StackNode() : this(default(T), null) {
    }
  
    public StackNode(T value) : this(value, null) {
    }
  
    public StackNode(T value, StackNode<T> next) {
        this._value = value;
        this._next = next;
    }
  
    public StackNode<T> Next {
        get { return this._next; }
        set { this._next = value; }
    }
  
    public T Value {
        get { return this._value; }
        set { this._value = value; }
    }
}

public class LinkStack<T> : IStack<T> {
    private int _count = 0;
    StackNode<T> _top;
  
    public int Count {
        get { return this._count; }
    }
  
    public void Clear() {
        this._top = null;
        this._count = 0;
    }
  
    public void Push(T value) {
        this._top=new StackNode<T>(value, this._top);
        this._count++;
    }
  
    public T Pop() {