算法系列15天速成第十天棧

2024-09-08 23:18:40

字體：大中小

來源：轉載

供稿：網友

一：概念

棧，同樣是一種特殊的線性表，是一種Last In First Out（LIFO)的形式，現實中有很多這樣的例子，

比如：食堂中的一疊盤子，我們只能從頂端一個一個的取。

二：存儲結構

”棧“不像”隊列“，需要兩個指針來維護，棧只需要一個指針就夠了，這得益于棧是一種一端受限的線性表。

這里同樣用”順序結構“來存儲這個”棧“，top指針指向棧頂，所有的操作只能在top處。

代碼段：

復制代碼代碼如下:

#region 棧的數據結構
    /// <summary>
/// 棧的數據結構
/// </summary>
    public class SeqStack<T>
    {
        public T[] data;

/// <summary>
/// 棧頂指針
/// </summary>
public int top = -1;

        public SeqStack(int lenth)
        {
            data = new T[lenth];
        }
    }
    #endregion

三：常用操作

棧的操作有：①初始化棧，②入棧，③出棧，④獲取棧頂。

1: 初始化棧

這個還是比較簡單的，初始化棧時，設置默認top指針為-1，這個就不用圖來展示了。

代碼段：

復制代碼代碼如下:

#region 棧的初始化操作
        /// <summary>
/// 棧的初始化操作
/// </summary>
/// <typeparam name="T"></typeparam>
/// <returns></returns>
        public SeqStack<T> SeqStackInit<T>(int length)
        {
            SeqStack<T> seqStack = new SeqStack<T>(length);

seqStack.top = -1;

            return seqStack;
        }
        #endregion

2：入棧

這個操作主要就是做兩件事情：① 將元素從棧頂壓入，② top指針自增。

代碼段：

復制代碼代碼如下:

#region 入棧
        /// <summary>
/// 入棧
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqStack"></param>
/// <param name="data"></param>
        public void SeqStackPush<T>(SeqStack<T> seqStack, T data)
        {
            if (SeqStackIsFull(seqStack))
                throw new Exception("不好意思，棧溢出");

            seqStack.data[++seqStack.top] = data;
        }
        #endregion

3：出棧

同樣跟“入棧”類似，需要做兩件事情，①干掉top處的元素，②top指針自減。

代碼段

復制代碼代碼如下:

#region 出棧
        /// <summary>
/// 出棧
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqStack"></param>
/// <returns></returns>
        public T SeqStackPop<T>(SeqStack<T> seqStack)
        {
            if (SeqStackIsEmpty(seqStack))
                throw new Exception("嗚嗚，棧已空");

seqStack.data[seqStack.top] = default(T);

            return seqStack.data[--seqStack.top];
        }
        #endregion

4：獲取棧頂元素

這個很簡單，跟“出棧”唯一不同的是不破壞棧頂元素，只是翻出來看看而已。

代碼段

復制代碼代碼如下:

#region 獲取棧頂
        /// <summary>
/// 獲取棧頂
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqStack"></param>
/// <returns></returns>
        public T SeqStackPeek<T>(SeqStack<T> seqStack)
        {
            if (SeqStackIsEmpty(seqStack))
                throw new Exception("棧已空");

            return seqStack.data[seqStack.top];
        }
        #endregion

總的運行代碼如下

復制代碼代碼如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SeqStack
{
    class Program
    {
        static void Main(string[] args)
        {
            SeqStackClass stackManager = new SeqStackClass();

SeqStack<Student> seqStack = stackManager.SeqStackInit<Student>(10);

            Console.WriteLine("******************** 壓入ID=1,ID=2,ID=3的元素 ***********************/n");
            //壓入ID=1,ID=2,ID=3的元素
            stackManager.SeqStackPush(seqStack, new Student() { ID = 1, Name = "一線碼農", Age = 23 });
            stackManager.SeqStackPush(seqStack, new Student() { ID = 2, Name = "huangxincheng520", Age = 23 });
            stackManager.SeqStackPush(seqStack, new Student() { ID = 3, Name = "51cto", Age = 23 });

Console.WriteLine(".... 壓入成功，當前棧中元素有：" + stackManager.SeqStackLen(seqStack) + "個");

Console.WriteLine("/n****************** 查看棧頂元素 ********************");

var result = stackManager.SeqStackPeek(seqStack);

Console.WriteLine("棧頂元素為：ID=" + result.ID + ",Name=" + result.Name + ",Age=" + result.Age);

Console.WriteLine("/n******************** 彈出棧頂元素 ***********************");

stackManager.SeqStackPop(seqStack);

Console.WriteLine("/n****************** 查看棧中的元素 ********************");

            for (int i = 0; i < stackManager.SeqStackLen(seqStack); i++)
            {
                Console.WriteLine("棧頂元素為：ID=" + seqStack.data[i].ID + ",Name=" + seqStack.data[i].Name + ",Age=" + seqStack.data[i].Age);
            }

            Console.Read();
        }
    }

    #region 學生數據實體
    /// <summary>
/// 學生數據實體
/// </summary>
    public class Student
    {
        public int ID { get; set; }

public string Name { get; set; }

        public int Age { get; set; }
    }
    #endregion

    #region 棧的數據結構
    /// <summary>
/// 棧的數據結構
/// </summary>
    public class SeqStack<T>
    {
        public T[] data;

/// <summary>
/// 棧頂指針
/// </summary>
public int top = -1;

        public SeqStack(int lenth)
        {
            data = new T[lenth];
        }
    }
    #endregion

    public class SeqStackClass
    {
        #region 棧的初始化操作
        /// <summary>
/// 棧的初始化操作
/// </summary>
/// <typeparam name="T"></typeparam>
/// <returns></returns>
        public SeqStack<T> SeqStackInit<T>(int length)
        {
            SeqStack<T> seqStack = new SeqStack<T>(length);

seqStack.top = -1;

            return seqStack;
        }
        #endregion

        #region 判斷棧是否為空
        /// <summary>
/// 判斷棧是否為空
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqStack"></param>
/// <returns></returns>
        public bool SeqStackIsEmpty<T>(SeqStack<T> seqStack)
        {
            return seqStack.top == -1;
        }
        #endregion

        #region 清空棧
        /// <summary>
/// 清空棧
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqStack"></param>
        public void SeqStackClear<T>(SeqStack<T> seqStack)
        {
            seqStack.top = -1;
        }
        #endregion

        #region 棧是否已滿
        /// <summary>
/// 棧是否已滿
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqStack"></param>
        public bool SeqStackIsFull<T>(SeqStack<T> seqStack)
        {
            return seqStack.top == seqStack.data.Length;
        }
        #endregion

            seqStack.data[++seqStack.top] = data;
        }
        #endregion

seqStack.data[seqStack.top] = default(T);

            return seqStack.data[--seqStack.top];
        }
        #endregion

            return seqStack.data[seqStack.top];
        }
        #endregion

        #region 獲取棧中元素個數
        /// <summary>
/// 獲取棧中元素個數
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="seqStack"></param>
/// <returns></returns>
        public int SeqStackLen<T>(SeqStack<T> seqStack)
        {
            return seqStack.top + 1;
        }
        #endregion
    }
}