1、栈

栈(Stack)是操作限定在表的尾端进行的线性表。表尾由于要进行插入、删除等操作,所以,它具有特殊的含义,把表尾称为栈顶( Top),另一端是固定的,叫栈底( Bottom)。当栈中没有数据元素时叫空栈(Empty Stack)。



操作方法


2、顺序栈(用数组实现顺序栈)

接口声明:

    interface StackInterface<T>
    {
        public int Count { get;  }
        /// <summary>
        /// 获取长度
        /// </summary>
        /// <returns></returns>
        public int GetLength();
        /// <summary>
        /// 是否为空
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty();
        /// <summary>
        /// 入栈
        /// </summary>
        /// <param name="Item"></param>
        public void Push(T Item);
        /// <summary>
        /// 出栈,并返回出栈数据
        /// </summary>
        /// <returns></returns>
        public T Pop();
        /// <summary>
        /// 取得栈顶数据
        /// </summary>
        /// <returns></returns>
        public T Peek();
        /// <summary>
        /// 清空所有数据
        /// </summary>
        public void Clear();
    }

实现接口:

    public class MyStack<T> : StackInterface<T>
    {
        private T[] data;
        private int top;

        public MyStack(int size)
        {
            data = new T[size];
            top = -1;
        }
        public MyStack() :this(10) //默认10个
        {
        }
        public int Count { 
            get 
            {
                return top + 1;
            }
        }
        public void Clear()
        {
            top = -1;
        }
        public int GetLength()
        {
            return Count;
        }
        public bool IsEmpty()
        {
            if (Count==0)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        public T Peek()
        {
            return data[top];
        }
        public T Pop()
        {
            T temp = data[top];
            top--;
            return temp;
        }
        public void Push(T Item)
        {
            data[top + 1] = Item;
            top++;
        }
    }

测试:


3、链栈(Linked Stack)

概述:原本链表每次添加元素的时候会添加在结尾,由于栈是在栈顶操作的,所以实现链栈添加元素时,要把元素添加在前面,既每添加一个新节点(入栈),头指针就指向新节点。
创建节点类:

 class Node<T>
    {
        private T data; //本节点数据
        private Node<T> next; //next存放的是下一节点地址,会访问到下一节点信息
        public T Data 
        {
            get { return data; }
            set { data = value; }
        }
        public Node<T> Next
        {
            get { return next; }
            set { next = value; }
        }
        public Node()
        {
            data = default(T);
            next = null;
        }
        public Node(T Item)
        {
            data = Item;
            next = null;
        }
        public Node(T data, Node<T> next)
        {
            this.data = data;
            this.next = next;
        }
        public Node(Node<T> next)
        {
            this.next = next;
            data = default(T);
        }
    }

编写接口实现:

 public class MyLinkedStack<T> : StackInterface<T>
    {
        private Node<T> top; //栈顶节点
        private int count;//栈中元素个数
        public MyLinkedStack()
        {
            top = null;
            count = 0;
        }

        public int Count
        { 
            get  { return count; } 
        }

        public void Clear()
        {
            count = 0;
            top = null;
        }

        public int GetLength()
        {
            return Count;
        }

        public bool IsEmpty()
        {
            if (count==0)
            {
                return true;
            }
            return false;
        }

        public T Peek()
        {
            return top.Data;
        }

        public T Pop()
        {
            T  temp= top.Data;
            top = top.Next;
            count--;
            return temp;
        }

        public void Push(T Item)
        {
            //新加的元素作为头节点(栈顶)
            Node<T> newnode = new Node<T>(Item);
            newnode.Next = top;
            top = newnode;
            count++;
        }
    }

测试:


最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 数据结构是编程的起点,理解数据结构可以从三方面入手: 逻辑结构。逻辑结构是指数据元素之间的逻辑关系,可分为线性结构...
    yhthu阅读 2,320评论 0 6
  • 栈 栈的英文单词是Stack,它代表一种特殊的线性表,这种线性表只能在固定一端(通常认为是线性表的尾端)进行插入,...
    Jack921阅读 1,529评论 0 5
  • 数组 1:什么是数组?2:Java中数组的声明及数组的遍历3:数组天生的优势——索引4:动态数组5:封装自己的数组...
    憨憨二师兄阅读 439评论 0 1
  • 栈 栈是一种特殊的线性表,只能在一端进行操作,往栈中添加元素的操作,一般叫做push,入栈,从栈中移除元素的操作,...
    coder_feng阅读 204评论 0 0
  • 栈 同顺序表和链表一样,栈也是用来存储逻辑关系为 "一对一" 数据的线性存储结构,如图1 所示: 栈对数据 "存"...
    hadoop_a9bb阅读 1,340评论 0 0