用链栈解决堆栈的编程问题

女爷i 2021-09-18 03:40 213阅读 0赞

用链栈解决堆栈的编程问题：

用链式存储结构存储的栈称为链栈（Linked Stack）。链栈通常用单链表来表示，它的实现是单链表的简化。

由于链栈的操作只是在一端进行，为了操作方便，把栈顶设在链表的头部，并且不需要头结点。

<table style="width:500px;">  链栈的结点结构  
 <tbody> 
  <tr> 
   <td>data</td> 
   <td>next</td> 
  </tr> 
 </tbody> 
</table>

下面是链栈的结构示意图：

![20190225123850692.png][]

代码实现：

using System;
    
    namespace 用链栈解决堆栈的编程问题
    {
        class Program
        {
            static void Main(string[] args)
            {
            }
        }
    
        interface IStack<T>
        {
            void Push(T elem);//入栈
            T Pop();//出栈
            T GetTop();//取栈顶
            int GetLength();//求栈长
            bool IsEmpty();//判断栈是否为空
            void Clear();//清空操作
        }
    
        class StackNode<T>
        {
            private T data;//数据域
            private StackNode<T> next;//引用域
    
            //数据域属性
            public T Data
            {
                get { return data; }
                set { data = value; }
            }
    
            //引用域属性
            public StackNode <T> Next
            {
                get { return next; }
                set { next = value; }
            }
    
            //构造函数
            public StackNode()
            {
                data = default(T);
                next = null;
            }
            public StackNode (T val)
            {
                data = val;
                next = null;
            }
            public StackNode(StackNode<T> p)
            {
                data = default(T);
                next = p;
            }
            public StackNode (T val,StackNode <T> p)
            {
                data = val;
                next = p;
            }
        }
    
        class LinkStack<T> : IStack<T>
        {
            private int size;//栈中元素的个数
            private StackNode<T> top;//栈顶指示器
    
            //元素个数属性
            public int Size
            {
                get { return size; }
                set { size = value; }
            }
    
            //栈顶指示器属性
            public StackNode<T> Top //注意：LinkStack<T>的访问类型不能声明为 public ，否则，这里就会报错
            {
                get { return top; }
                set { top = value; }
            }
    
            /// <summary>
            /// 初始化链栈
            /// </summary>
            public LinkStack ()
            {
                size = 0;
                top = null;
            }
    
            /// <summary>
            /// 清空链栈
            /// </summary>
            public void Clear()
            {
                size = 0;
                top = null;
            }
    
            /// <summary>
            /// 求链栈长度
            /// </summary>
            /// <returns></returns>
            public int GetLength()
            {
                return size;
            }
    
            /// <summary>
            /// 判断链栈是否为空
            /// </summary>
            /// <returns></returns>
            public bool IsEmpty()
            {
                if((size ==0)&&(top ==null))
                {
                    return true;
                }else
                {
                    return false;
                }
            }
    
            /// <summary>
            /// 获取栈顶结点的值
            /// </summary>
            /// <returns></returns>
            public T GetTop()
            {
                if(IsEmpty())
                {
                    Console.WriteLine("Stack is empty");
                    return default(T);
                }
                else
                {
                    return top.Data;
                }
            }
    
            /// <summary>
            /// 入栈操作
            /// </summary>
            /// <param name="elem"></param>
            public void Push(T elem)
            {
                StackNode<T> q = new StackNode<T>(elem);
                if(top ==null)
                {
                    top = q;
                }else
                {
                    q.Next = top;
                    top = q;
                }
            }
    
            /// <summary>
            /// 出栈操作
            /// </summary>
            /// <returns></returns>
            public T Pop()
            {
                if(IsEmpty())
                {
                    Console.WriteLine("Stack is empty");
                    return default(T);
                }
                StackNode<T> p = top;
                top = top.Next; //重点！
                size--;
                return p.Data ;
            }
        }
    }

[20190225123850692.png]: /images/20210725/dcea3f300036441d987074d85f3f2669.png