.NET 数据结构：栈

栈是具有先入后出特征的线性数据结构。

在益智玩具汉诺塔中，为了移动圆盘，玩家总是需要先移动一个塔上最上层的圆盘。而移动到下一个塔后，那个圆盘则始终会出现在那个塔的最上方。

此时，每个塔都可以被视为一个栈。

栈的所有元素都是先进后出的：

当元素入栈（添加到栈中）后，该元素成为栈顶（最底部的元素则为栈底）
元素的出栈即是从栈中移除该元素

常用操作

在使用栈的过程中，入栈、出栈和访问栈顶元素是最常见的操作，而这些操作的时间复杂度均为O(1)。

类似列表，栈可以基于数组或链表实现。

// 初始化
Stack<int> stack = new Stack<int>();

// 入栈
stack.Push(1);
stack.Push(1);
stack.Push(4);
stack.Push(5);
stack.Push(1);
stack.Push(4);

// 出栈
int pop = stack.Pop();

// 获取栈顶元素
int peek = stack.Peek();

// 获取栈的长度
int size = stack.Count;

// 判断栈是否为空
bool isEmpty = stack.Count == 0;

实现

抛开先进后出的特性不谈，栈和列表、链表极为相似。所以，对列表和链表施加限制即可达到栈的效果。

基于列表

将列表的尾部元素定义为栈顶，在列表的尾部添加元素是入栈，移除则是出栈。在未触发扩容操作的情况下，时间复杂度均为O(1)。

class ListStack
{
	List<int> stack = [];  // 初始化

	public void Push(int num) => stack.Add(num);  // 入栈
	
    public int Size() => stack.Count;  // 获取栈的长度
	
	public bool IsEmpty() => Size() == 0;  // 判断栈是否为空

	// 访问栈顶元素
	public int Peek()
	{
		if (IsEmpty())
			throw new Exception();
		return stack[Size() - 1];
	}

	// 出栈
	public int Pop()
	{
		if (IsEmpty())
			throw new Exception();
		var peek = Peek();
		stack.RemoveAt(Size() - 1);
		return peek;
	}
}

列表诸如访问任意元素，插入等操作不属于栈的范畴。

基于链表

将链表的头节点视为栈顶，在链表的头部添加元素是入栈，移除则是出栈。

// 节点类
public class Node<T>(T item)
{
    public T Item { get; set; } = item;
    public Node<T> Next { get; set; }
}

public class LinkedStack<T>
{
    private Node<T> first = null;
    private int index = 0;
	
    // 入栈
    public void Push(T item)
    {
        Node<T> oldNode = first;
        first = new Node<T>(item);
        first.Next = oldNode;
        index++;
    }

	// 出栈
	public T Pop()
	{
		T item = first.Item;
		first = first.Next;
		index--;
		return item;
	}

	// 判断栈是否为空
	public bool IsEmpty() => this.index == 0;

	// 获取栈的长度
	public int Size() => this.index;
}

对比

基于列表的实现效率一般更高，但扩容操作会使它在添加元素时降低到O(n)的效率。由于扩容操作在后期不容易触发，所以不用太关心。

基于链表实现的效率虽然没有列表那么高且占用空间略大，但好在稳定，不会因为扩容操作而突然降低效率。

基本应用

递归算法
浏览器的网页记录（后退，前进等）

本文和右下角标有www.hello-algo.com标识的图片采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。