数据结构栈篇

概念

• 定义：栈是操作跟定在表的尾端进行的线性表。表尾要进行插入，删除等操作。表的尾端叫做栈顶，另一段叫做栈底。
• 特点：先进后出
• 入栈：将数据压至栈顶的过程叫做入栈
• 出栈：将数据从栈顶移出栈外叫做出栈

栈的常用操作

• Push():入栈，添加数据
• Pop():出栈，移除数据
• Peek():返回栈顶的元素但不删除
• Count:栈中元素个数
• IsEmpty():是否为空栈
• Clear():将栈中的所有数据移出栈外

栈的两种存储方式

• 顺序栈：用一片连续的存储空间来存储栈中的数据元素（使用数组）称为顺序栈，逻辑相邻的两个结点在物理存储上也是相邻
• 链栈：逻辑相邻的两个数据结点在物理存储上并不相邻，链栈的逻辑与单链表的逻辑一样

栈的实现

1 定义栈的接口

public interface MyStackDS<T>
    {
        int Count{ get;}//获取栈中数据个数
        int GetLength();//获取栈中数据个数
        bool IsEmpty();//是否为空栈
        void Clear();//清除栈中的数据
        void Push(T item);//将数据压入栈顶
        T Pop();//将栈顶数据弹出栈并返回
        T Peek();//返回栈顶的数据但是不删除
    }

2 顺序栈

• 实现栈的接口

        //使用数组来存储栈中的数据
        private T[] data;
        //指向栈顶的下标
        private int top;
        //构造并且初始化
        public SeqStack (int size)
        {
            data = new T[size];
            top = -1;
        }
        //栈中元素个数
        public int Count{ 
            get{ 
                return top + 1;
            }
        }
        public int GetLength(){
            return Count;
        }
        //判断栈中元素个数来判断栈是否为空栈
        public bool IsEmpty(){
            return Count == 0;
        }
        //将指向栈顶的下标设置成默认值即清除了栈内的元素
        public void Clear(){
            top = -1;
        }
        //将数据压入栈中
        public void Push(T item){
            data[top+1] = item;
            top++;
            Console.WriteLine ("添加top = {0}", top);

        }
        //出栈：将栈顶数据取出，指向栈顶的下标指向下一个元素，最后将栈顶数据返回
        public T Pop(){
            T temp = data[top];
            top--;
            Console.WriteLine ("移除top = {0}", top);
            return temp;
        }
        //返回栈顶的数据
        public T Peek(){
            return data[top];
        }

3 链栈

(1) 定义链栈结点类StackNode

• 链栈结点设计与单链表结点设计一致，保存存储的实际数据后还需要有指向下一个结点的指针

        private T data;//存储的实际数据
        private StackNode<T> nextNode;//指向下一结点的坐标
        // 属性
        public T Data{
            set{ 
                data = value;
            }
            get{ 
                return data;
            }
        }

        public StackNode<T> NextNode{
            set{ 
                nextNode = value;
            }
            get{ 
                return nextNode;
            }
        }
        //提供不同的构造方法
        public StackNode (T data,StackNode<T> nextNode)
        {
            this.Data = data;
            this.NextNode = nextNode;
        }

        public StackNode(){
            this.Data = default(T);
            NextNode = null;
        }

        public StackNode(T data){
            this.Data = data;
            NextNode = null;
        }

(2) 定义链栈类LinkStack

        //栈顶结点
        private StackNode<T> top;
        //栈中元素个数
        private int count = 0;
        public LinkStack ()
        {
        }

        //取得栈中元素个数
        public int Count{ get{ return count;} }
        public int GetLength(){
            return count;
        }
        /// 判断栈中是否有数据
        public bool IsEmpty(){
            return count == 0;
        }
        //将栈顶结点置空即清除了栈中的数据
        public void Clear(){
            count = 0;
            top = null;
        }
        //入栈，将新添加的元素做为栈顶节点
        public void Push(T item){
            StackNode<T> newNode = new StackNode<T>(item);
            newNode.NextNode = top;
            top = newNode;
            count++;
        }
        //取得栈顶元素后删除
        public T Pop(){
            T data = top.Data;
            top = top.NextNode;
            count--;
            return data;
        }
        //取得栈顶的元素但是不删除
        public T Peek(){
            return top.Data;
        }