计算机专业面试常见基础什么是栈（Stack）？

什么是栈（Stack）？

栈（Stack）是一种线性数据结构，它遵循先进后出（LIFO，Last In, First Out）的原则。在栈中，所有的插入和删除操作都在栈顶进行。我们可以将栈想象成一组盘子，每个盘子代表一个数据元素，盘子只能从一端放置或移除，这一端栈顶。

栈的基本特性

1. 唯一入口/出口：栈只有一个入口和一个出口，称为栈顶（Top）和栈底（Bottom）。

2. 后进先出：入到栈中的元素最先被移除。

3. 有限容量：大多数栈有固定的最大容量，当栈满时，再尝试添加新元素将导致溢出。

栈的操作

– 压栈（Push）：将一个新元素添加到栈顶。

– 出栈（Pop）：从栈顶移除元素。

– 查看栈顶元素（Peek）：获取栈顶元素的值，但不移除它。

– 判断栈空（IsEmpty）：检查栈是否为空。

– 获取栈的大小（Size）：返回栈中元素的数量。

栈的应用

栈在计算机科学中有许多应用，是一些常见的例子：

1. 函数调用栈：在编程语言中，每次函数调用都会在栈上创建一个新的帧，包含局部变量和返回地址。当函数返回时，相应的栈帧被移除。

2. 递归：递归函数在执行过程中会不断调用自身，每个函数调用都会在栈上创建一个新的帧。

3. 表达式求值：使用栈可以有效地计算逆波兰表达式（后缀表达式）或中缀表达式。

4. 括号匹配：通过使用栈，可以检查程序中的括号是否正确匹配。

5. undo/redo 功能：在文本编辑器或其他应用程序中，可以通过栈来实现 undo 和 redo 功能。

栈的实现

栈可以通过多种实现，是一些常见的方法：

– 数组实现：使用一个数组和一个指向栈顶的指针。

– 链表实现：使用链表节点动态地表示栈中的元素。

数组实现栈的代码示例（Python）

python

class Stack:

def __init__(self, capacity=10):

self.stack = [None] * capacity

self.top = -1

self.capacity = capacity

def is_empty(self):

return self.top == -1

def is_full(self):

return self.top == self.capacity – 1

def push(self, item):

if self.is_full():

raise IndexError("Stack is full")

self.stack[self.top + 1] = item

self.top += 1

def pop(self):

if self.is_empty():

raise IndexError("Stack is empty")

item = self.stack[self.top]

self.stack[self.top] = None

self.top -= 1

return item

def peek(self):

if self.is_empty():

raise IndexError("Stack is empty")

return self.stack[self.top]

# Example usage:

stack = Stack()

stack.push(1)

stack.push(2)

print(stack.pop()) # Output: 2

print(stack.peek()) # Output: 1

栈是一种常见的基础数据结构，它在计算机科学中有着广泛的应用。理解栈的基本概念、操作和应用对于计算机专业的学生和从业者来说至关重要。在面试中，了解如何实现和应用栈是评估面试者对计算机专业基础知识的掌握程度的一个重要方面。