栈(Stack)

栈中元素是从上到下加入的，即“后进先出”

栈的应用

十进制转二进制

Console.WriteLine("请输入一个十进制数字");
        int num = int.Parse(Console.ReadLine());
        Stack<int> Remainder = new Stack<int>();
        while (num != 0)
        {
            Remainder.Push(num % 2);
            num /= 2;
        }
        foreach (var item in Remainder)
        {
            Console.ForegroundColor = ConsoleColor.DarkBlue;
            Console.Write(item);
        }
        Console.ReadKey();

打印结果:

数组实现栈

栈的相关操作

Stack

void Push(t) 添加元素

T Pop() 删除栈顶

T Peek() 查询栈顶

int Count 栈中多少元素

bool IsEmpty 是否为空

数组在尾端添加删除最合适

新建接口

新建一个**接口Stack**实现以上方法

namespace AlgorithmTest09_实现栈Stack
{
    interface IStack<T>
    {
        int Count { get; }
        bool IsEmpty { get; }
        void Push(T t);
        T Pop();
        T Peek();
    }
}

实现接口

新建Array1Stack类实现接口功能

using AlgorithmTest06_List;

namespace AlgorithmTest09_实现栈Stack
{
    class Array1Stack<T> : IStack<T>
    {
        private SeqList<T> arr;

        /// <summary>
        /// 构造函数
        /// 参数:容量
        /// </summary>
        /// <param name="capacity"></param>
        public Array1Stack(int capacity)
        {
            arr = new SeqList<T>(capacity);
        }
        /// <summary>
        /// 构造函数,默认10容量
        /// </summary>
        public Array1Stack()
        {
            arr = new SeqList<T>();
        }

        public int Count { get { return arr.GetCount(); } }//个数

        public bool IsEmpty { get { return arr.IsEmpty(); } }//是否为空

        /// <summary>
        /// 数组底部入栈,为栈顶
        /// </summary>
        /// <param name="t"></param>
        public void Push(T t)
        {
            arr.AddLast(t);
        }
        /// <summary>
        /// 查询栈顶元素
        /// </summary>
        /// <returns></returns>
        public T Peek()
        {
            return arr[arr.count - 1];//获取数组末尾索引
        }
        /// <summary>
        /// 删除数组末尾,出栈
        /// </summary>
        /// <returns></returns>
        public T Pop()
        {
            return arr.RemoveLast();
        }

        public override string ToString()
        {
            return "Stack:" + arr.ToString() + "--Top";
        }
    }
}

实现效果

using System;

namespace AlgorithmTest09_实现栈Stack
{
    class Program
    {
        static void Main(string[] args)
        {
            Array1Stack<int> stack = new Array1Stack<int>();

            Console.WriteLine("-----栈顶添加元素-----");
            for (int i = 0; i < 5; i++)
            {
                stack.Push(i);
                Console.WriteLine(stack);
            }
            Console.WriteLine("-----栈顶删除元素-----");
            Console.WriteLine("删除:" + stack.Pop());
            Console.WriteLine(stack);
            Console.WriteLine("查询栈顶:" + stack.Peek());
            Console.WriteLine("元素个数:" + stack.Count);
            Console.WriteLine("是否为空:" + stack.IsEmpty);
            Console.ReadKey();
        }
    }
}

演示结果

链表实现栈

栈的相关操作

Stack

void Push(t) 添加元素

T Pop() 删除栈顶

T Peek() 查询栈顶

int Count 栈中多少元素

bool IsEmpty 是否为空

链表最方便的是在头部进行添加或删除操作

实现接口

新建LinkedList1Stack类实现IStack接口的方法

using AlgorithmTest08_链表;
namespace AlgorithmTest09_实现栈Stack
{
    /// <summary>
    /// 链表栈
    /// </summary>
    class LinkedList1Stack<T> : IStack<T>
    {
        private LinkedList1<T> list;//链表

        public LinkedList1Stack()
        {
            list = new LinkedList1<T>();
        }

        /// <summary>
        /// 节点个数
        /// </summary>
        public int Count { get { return list.Count; } }

        /// <summary>
        /// 是否有节点
        /// </summary>
        public bool IsEmpty { get { return list.IsEmpty; } }

        /// <summary>
        /// 头部添加节点-入栈
        /// </summary>
        /// <param name="t"></param>
        public void Push(T t)
        {
            list.AddFirst(t);
        }
        /// <summary>
        /// 查询头部节点--查询栈顶
        /// </summary>
        /// <returns></returns>
        public T Peek()
        {
            return list.GetFirst();
        }
        /// <summary>
        /// 删除头节点-栈顶出栈
        /// </summary>
        /// <returns></returns>
        public T Pop()
        {
            return list.RemoveFirst();
        }

        public override string ToString()
        {
            return "Stack:Top--" + list.ToString();
        }
    }
}

实现效果

using System;

namespace AlgorithmTest09_实现栈Stack
{
    class Program
    {
        static void Main(string[] args)
        {
            Array1Stack<int> stack = new Array1Stack<int>();

            Console.WriteLine("-----栈顶添加元素-----");
            for (int i = 0; i < 5; i++)
            {
                stack.Push(i);
                Console.WriteLine(stack);
            }
            Console.WriteLine("-----栈顶删除元素-----");
            Console.WriteLine("删除:" + stack.Pop());
            Console.WriteLine(stack);
            Console.WriteLine("查询栈顶:" + stack.Peek());
            Console.WriteLine("元素个数:" + stack.Count);
            Console.WriteLine("是否为空:" + stack.IsEmpty);

            Console.WriteLine("-----链表栈演示-----");
            LinkedList1Stack<int> listStack = new LinkedList1Stack<int>();

            Console.WriteLine("-----链表栈顶添加元素-----");
            for (int i = 0; i < 5; i++)
            {
                listStack.Push(i);
                Console.WriteLine(listStack);
            }
            Console.WriteLine("-----链表栈顶删除元素-----");
            Console.WriteLine("删除:" + listStack.Pop());
            Console.WriteLine(listStack);
            Console.WriteLine("查询栈顶:" + listStack.Peek());
            Console.WriteLine("元素个数:" + listStack.Count);
            Console.WriteLine("是否为空:" + listStack.IsEmpty);
            Console.ReadKey();
        }
    }
}

数据结构-栈

栈(Stack)

栈的应用

数组实现栈

栈的相关操作

新建接口

实现接口

实现效果

演示结果

链表实现栈

栈的相关操作

实现接口

实现效果

演示结果