Stack and Queue Data Structures: Concepts and Applications | 栈与队列数据结构：核心概念与应用实例

📚 Stack and Queue Data Structures: Concepts and Applications | 栈与队列数据结构：核心概念与应用实例

Stacks and queues are two of the most fundamental abstract data types (ADTs) in computer science. They are linear data structures that store collections of elements, but they differ in the order in which elements are added and removed. A stack follows the Last-In, First-Out (LIFO) principle, while a queue follows the First-In, First-Out (FIFO) principle. Understanding these structures is essential for algorithm design, operating system implementation, and solving many technical interview problems.

栈和队列是计算机科学中最基础的两种抽象数据类型（ADT）。它们都是线性数据结构，存储元素的集合，但添加和移除元素的顺序不同：栈遵循后进先出（LIFO）原则，队列遵循先进先出（FIFO）原则。理解这两种结构对于算法设计、操作系统实现以及解决许多技术面试题都至关重要。

1. What is a Stack? | 什么是栈？

A stack is an abstract data type that stores elements in a linear order. All insertions and deletions are performed at a single end called the top of the stack. This behaviour is known as Last-In, First-Out, or LIFO. The element added most recently is the first one to be removed. A common real-world analogy is a stack of plates: you place a plate on top and remove a plate from the top only.

栈是一种按线性顺序存储元素的抽象数据类型。所有插入和删除操作都在一个称为栈顶的一端进行。这种行为称为后进先出（LIFO）。最近添加的元素将最先被移除。一个常见的现实类比是一摞盘子：你只能把盘子放在顶部，也只能从顶部拿走盘子。

The fundamental operations are push (add an element to the top), pop (remove the top element), peek or top (return the top element without removing it), and isEmpty (check whether the stack has no elements). Because these operations work on only one end, a stack is also called a restricted list.

栈的基本操作包括：push（将元素压入栈顶）、pop（弹出栈顶元素）、peek 或 top（查看栈顶元素但不移除），以及 isEmpty（判断栈是否为空）。由于这些操作只在一个端点进行，栈也被称为受限的线性表。

2. Core Operations and Time Complexity | 核心操作与时间复杂度

Push adds a new element onto the top; Pop removes the top element; Peek returns the top value; isEmpty checks whether the stack is empty; Size returns the number of elements. If the stack is implemented with a dynamically resizable array and we keep track of the top index, all of these operations run in O(1) time.

Push（压栈）将一个新元素添加到栈顶；Pop（弹栈）移除栈顶元素；Peek（取栈顶）返回栈顶值但不删除；isEmpty（判空）检查栈是否为空；Size（大小）返回元素个数。如果栈使用动态数组实现并维护栈顶下标，则所有这些操作都在 O(1) 时间内完成。

The constant-time behaviour makes stacks very efficient for storing temporary data and for backtracking tasks. The table below summarises the main operations.

这种常数时间特性使栈非常适合存储临时数据和解决回溯类任务。下表总结了栈的主要操作。