亲自教你实现栈及C#中Stack源码分析

栈的定义

栈是一种具有特殊行为的线性数据结构，栈中的元素遵循 LIFO(Last In First Out) 原则：

• 入栈（Push）：在栈的顶部添加一个元素；
• 出栈（Pop）：从栈的顶部移除一个元素；
• 取顶（Peek）：获取栈顶元素，但不对栈进行操作；
• 判空（IsEmpty）：判断栈中是否有元素。

栈的实现方式有两种：数组和链表。

数组实现栈

数组实现栈思路比较简单，基本原理就是使用数组来存储栈中的元素。具体实现方式请参考以下代码：

class ArrayStack<T>
{
    private T[] stack;
    private int top = -1;

    public ArrayStack(int capacity)
    {
        stack = new T[capacity];
    }

    public void Push(T item)
    {
        if (top == stack.Length - 1)
        {
            throw new StackOverflowException("stack overflow");
        }
        stack[++top] = item;
    }

    public T Pop()
    {
        if (top == -1)
        {
            throw new InvalidOperationException("stack is empty");
        }
        return stack[top--];
    }

    public T Peek()
    {
        if (top == -1)
        {
            throw new InvalidOperationException("stack is empty");
        }
        return stack[top];
    }

    public bool IsEmpty()
    {
        return top == -1;
    }
}

以上代码展示了如何使用数组实现栈类，其支持Push、Pop、Peek和IsEmpty操作。在创建ArrayStack对象时，需要传入一个整数参数capacity，表示栈的最大容量。在Push操作中，如果栈已满，则会抛出StackOverflowException异常，在Pop和Peek操作中，如果栈为空，则会抛出InvalidOperationException异常。示例代码：

static void Main(string[] args)
{
    var stack = new ArrayStack<int>(10);
    stack.Push(1);
    int item = stack.Pop(); // item = 1
    Console.WriteLine(item);
}

链表实现栈

链表实现栈的原理比数组方式更加简单，正是由于链表的“可增长性”，其可以实现 really dynamic stack，而数组实现的最大容量（capacity）是一开始就定好了的。

链表实现栈的具体实现方式请参考以下代码：

class LinkedListStack<T>
{
    private class Node
    {
        public T item;
        public Node next;
    }

    private Node top;

    public void Push(T item)
    {
        Node oldTop = top;
        top = new Node();
        top.item = item;
        top.next = oldTop;
    }

    public T Pop()
    {
        if (top == null)
        {
            throw new InvalidOperationException("stack is empty");
        }
        T item = top.item;
        top = top.next;
        return item;
    }

    public T Peek()
    {
        if (top == null)
        {
            throw new InvalidOperationException("stack is empty");
        }
        return top.item;
    }

    public bool IsEmpty()
    {
        return top == null;
    }
}

在链表实现栈代码中，我们在Push操作中，首先创建一个新的Node实例，并将其设置为top节点，然后将旧的top节点设置为新的top节点的next属性。示例代码：

static void Main(string[] args)
{
    var stack = new LinkedListStack<int>();
    stack.Push(1);
    int item = stack.Pop(); // item = 1
    Console.WriteLine(item);
}

C#中Stack源码分析

Stack是C#内置的一种数据结构，具有Push、Pop、Peek和Count等方法，以支持类似于数组的行为。但是，与数组不同的是，它是一种动态数据结构。以下是Stack的最简示例代码：

Stack<int> stack = new Stack<int>();
stack.Push(1);
int item = stack.Pop(); // item = 1
Console.WriteLine(item);

在源代码中，Stack类是使用动态数组实现的。这意味着，在执行Push操作时，如果已经达到了动态数组的最大容量，则新的容量将是原始容量的两倍。同时，在Pop操作中，如果容量减小到堆栈元素数的四分之一，则Stack将减小其容量到原始容量的一半。

自C#2.0以来，Stack类实现了IEnumerable接口，以支持枚举。如果您希望对Stack中的元素进行枚举，则可以使用foreach循环，如以下示例代码所示：

foreach (int i in stack)
{
    Console.Write(i + " ");
}

示例说明

以下是两个示例程序，在例子1中我们使用的是链表实现，而在例子2中我们使用的是C#内置的Stack数据结构。

示例1

class Program
{
    static void Main(string[] args)
    {
        LinkedListStack<int> stack = new LinkedListStack<int>();
        stack.Push(1);
        stack.Push(2);
        stack.Push(3);

        Console.WriteLine(stack.Pop()); // 输出3
        Console.WriteLine(stack.Pop()); // 输出2
        Console.WriteLine(stack.Pop()); // 输出1
    }
}

以上示例演示了如何使用LinkedListStack实现栈。

示例2

class Program
{
    static void Main(string[] args)
    {
        Stack<int> stack = new Stack<int>();
        stack.Push(1);
        stack.Push(2);
        stack.Push(3);

        Console.WriteLine(stack.Pop()); // 输出3
        Console.WriteLine(stack.Pop()); // 输出2
        Console.WriteLine(stack.Pop()); // 输出1
    }
}

以上示例演示了如何使用C#内置的Stack类实现栈。