正文

计算Stack长度只需掌握这几种主流方法代码示例与常见坑点分析

/0 浏览量
0923

前言：一个被忽视的基础问题

“栈有多长？”

听起来简单对吧？但在实际开发中，这个看似 trivial 的问题却坑死了不少开发者。我见过因为栈长度计算错误导致内存溢出、性能暴跌、甚至安全漏洞的案例。今天我们就来彻底讲清楚各种栈长度计算的方法、代码示例和常见陷阱。

一、Java Stack 的长度计算

1.1 使用 Stack 类

Java 中经典的 Stack 类继承自 Vector，提供了几种获取长度的方式：

import java.util.Stack;

public class JavaStackExample {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        
        stack.push("Apple");
        stack.push("Banana");
        stack.push("Cherry");
        
        // 方法1: size() - 最常用
        int size = stack.size();
        System.out.println("栈的大小: " + size); // 输出: 3
        
        // 方法2: isEmpty() - 检查是否为空
        boolean isEmpty = stack.isEmpty();
        System.out.println("栈是否为空: " + isEmpty); // 输出: false
        
        // 方法3: empty() - 已过时，不推荐使用
        boolean isOldEmpty = stack.empty();
        System.out.println("旧方法判断是否为空: " + isOldEmpty);
    }
}

关键点：

  • size() 返回栈中元素的数量
  • isEmpty() 比 empty() 更推荐使用
  • Stack 是线程安全的，但性能较差

1.2 使用 ArrayDeque 替代 Stack

现代 Java 开发中，推荐使用 ArrayDeque 代替 Stack：

import java.util.ArrayDeque;

public class ArrayDequeExample {
    public static void main(String[] args) {
        ArrayDeque<String> deque = new ArrayDeque<>();
        
        deque.push("Apple");
        deque.push("Banana");
        deque.push("Cherry");
        
        // ArrayDeque 没有 size() 方法，需要通过其他方式
        int size = deque.size();
        System.out.println("ArrayDeque 的大小: " + size); // 输出: 3
        
        // 遍历栈
        while (!deque.isEmpty()) {
            System.out.println("弹出: " + deque.pop());
        }
    }
}

1.3 常见坑点分析

坑点1：误用 empty() 方法

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);

// 错误：empty() 返回的是 boolean，不是长度
int length = stack.empty(); // 编译错误！

// 正确：使用 size()
int correctLength = stack.size(); // 返回 2

坑点2：混淆 size() 和容量

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);

// size() 返回的是实际元素数量
int size = stack.size(); // 返回 2

// 栈的容量（内部数组大小）可能是更大的值
// Stack 没有直接获取容量的方法，但可以通过反射获取
try {
    java.lang.reflect.Field field = stack.getClass().getDeclaredField("elementData");
    field.setAccessible(true);
    Vector<?> elementData = (Vector<?>) field.get(stack);
    System.out.println("内部数组容量: " + elementData.size());
} catch (Exception e) {
    e.printStackTrace();
}

二、Python Stack 的长度计算

2.1 使用列表作为栈

Python 中最常见的方式是使用列表（list）作为栈：

# 方法1: 使用 len() 函数
stack = []
stack.append('Apple')
stack.append('Banana')
stack.append('Cherry')

length = len(stack)
print(f"栈的长度: {length}")  # 输出: 3

# 方法2: 检查是否为空
is_empty = len(stack) == 0
print(f"栈是否为空: {is_empty}")  # 输出: False

# 方法3: 使用 bool() 转换
is_empty_bool = not bool(stack)
print(f"使用 bool 判断是否为空: {is_empty_bool}")  # 输出: False

2.2 使用 collections.deque

Python 官方推荐的方式是使用 deque：

from collections import deque

# 方法1: 使用 deque
stack = deque()
stack.append('Apple')
stack.append('Banana')
stack.append('Cherry')

length = len(stack)
print(f"deque 的长度: {length}")  # 输出: 3

# 弹出元素
while stack:
    print(f"弹出: {stack.pop()}")

# 方法2: 性能对比
import time

# 测试 list 作为栈的性能
list_stack = []
start = time.time()
for i in range(100000):
    list_stack.append(i)
    if len(list_stack) > 1000:
        list_stack.pop()
end = time.time()
print(f"List 栈耗时: {end - start:.6f} 秒")

# 测试 deque 作为栈的性能
deque_stack = deque()
start = time.time()
for i in range(100000):
    deque_stack.append(i)
    if len(deque_stack) > 1000:
        deque_stack.pop()
end = time.time()
print(f"Deque 栈耗时: {end - start:.6f} 秒")

2.3 常见坑点分析

坑点1：混淆 len() 和 容量

# Python 的 list 和 deque 没有"容量"概念
# len() 返回的是实际元素数量

stack = [1, 2, 3]
print(len(stack))  # 输出: 3

# 如果你想查看底层数组的大小，需要用到 ctypes
import ctypes

class ListWithCapacity:
    def __init__(self):
        self._list = []
    
    def append(self, item):
        self._list.append(item)
    
    def len(self):
        return len(self._list)
    
    def capacity(self):
        # 获取底层数组的容量
        return ctypes.c_long.from_address(id(self._list) + 28).value

my_list = ListWithCapacity()
my_list.append(1)
my_list.append(2)
print(f"长度: {my_list.len()}")  # 输出: 2
# print(f"容量: {my_list.capacity()}")  # 输出: 4 (可能不同)

坑点2：在循环中错误计算长度

# 错误示例：在循环中修改栈并计算长度
stack = [1, 2, 3, 4, 5]

# 错误做法
for i in range(len(stack)):
    print(f"弹出: {stack.pop()}")

# 正确做法
while stack:
    print(f"弹出: {stack.pop()}")

# 或者使用 reversed()
for item in reversed(stack):
    print(f"弹出: {item}")
stack.clear()

三、JavaScript Stack 的长度计算

3.1 使用数组作为栈

// 方法1: 使用数组的 length 属性
const stack = [];
stack.push('Apple');
stack.push('Banana');
stack.push('Cherry');

const length = stack.length;
console.log(`栈的长度: ${length}`);  // 输出: 3

// 方法2: 检查是否为空
const isEmpty = stack.length === 0;
console.log(`栈是否为空: ${isEmpty}`);  // 输出: false

// 方法3: 弹出元素
while (stack.length > 0) {
    console.log(`弹出: ${stack.pop()}`);
}

3.2 使用类封装栈

class Stack {
    constructor() {
        this.items = [];
    }
    
    // 压栈
    push(element) {
        this.items.push(element);
    }
    
    // 弹栈
    pop() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items.pop();
    }
    
    // 查看栈顶元素
    peek() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.items.length - 1];
    }
    
    // 检查是否为空
    isEmpty() {
        return this.items.length === 0;
    }
    
    // 获取栈的长度
    size() {
        return this.items.length;
    }
    
    // 清空栈
    clear() {
        this.items = [];
    }
}

// 使用示例
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);

console.log(`栈的大小: ${stack.size()}`);  // 输出: 3
console.log(`栈顶元素: ${stack.peek()}`);   // 输出: 3
console.log(`栈是否为空: ${stack.isEmpty()}`); // 输出: false

3.3 常见坑点分析

坑点1：使用 unshift/shift 代替 push/pop

// 错误：使用 unshift/shift 会降低性能
const badStack = [];
badStack.unshift(1);  // O(n) 操作
badStack.unshift(2);
badStack.unshift(3);

// 正确：使用 push/pop
const goodStack = [];
goodStack.push(1);   // O(1) 操作
goodStack.push(2);
goodStack.push(3);

console.log(`badStack 长度: ${badStack.length}`);  // 输出: 3
console.log(`goodStack 长度: ${goodStack.length}`); // 输出: 3

坑点2：递归调用导致栈溢出

// 错误：递归深度过大导致栈溢出
function recursiveFunction(n) {
    if (n <= 0) return;
    recursiveFunction(n - 1);  // 递归调用
}

try {
    recursiveFunction(10000);  // 可能会报错
} catch (error) {
    console.error(`错误: ${error.message}`);
}

// 正确：使用迭代方式
function iterativeFunction(n) {
    let count = 0;
    while (n > 0) {
        count++;
        n--;
    }
    return count;
}

console.log(`迭代结果: ${iterativeFunction(10000)}`);  // 输出: 10000

四、C++ Stack 的长度计算

4.1 使用 std::stack

#include <iostream>
#include <stack>
#include <string>

int main() {
    std::stack<std::string> stack;
    
    stack.push("Apple");
    stack.push("Banana");
    stack.push("Cherry");
    
    // 方法1: size() 返回栈中元素数量
    size_t size = stack.size();
    std::cout << "栈的大小: " << size << std::endl;  // 输出: 3
    
    // 方法2: empty() 检查是否为空
    bool isEmpty = stack.empty();
    std::cout << "栈是否为空: " << std::boolalpha << isEmpty << std::endl;  // 输出: false
    
    // 弹出所有元素
    while (!stack.empty()) {
        std::cout << "弹出: " << stack.top() << std::endl;
        stack.pop();
    }
    
    return 0;
}

4.2 使用底层容器

#include <iostream>
#include <stack>
#include <deque>
#include <vector>

int main() {
    // 方法1: 使用默认容器 (deque)
    std::stack<int> stack1;
    stack1.push(1);
    stack1.push(2);
    stack1.push(3);
    
    std::cout << "默认容器栈大小: " << stack1.size() << std::endl;
    
    // 方法2: 使用 vector 作为底层容器
    std::stack<int, std::vector<int>> stack2;
    stack2.push(1);
    stack2.push(2);
    stack2.push(3);
    
    std::cout << "Vector 容器栈大小: " << stack2.size() << std::endl;
    
    // 方法3: 使用 list 作为底层容器
    std::stack<int, std::list<int>> stack3;
    stack3.push(1);
    stack3.push(2);
    stack3.push(3);
    
    std::cout << "List 容器栈大小: " << stack3.size() << std::endl;
    
    return 0;
}

4.3 常见坑点分析

坑点1：混淆 size() 和 容量

#include <iostream>
#include <stack>
#include <deque>

int main() {
    std::stack<int> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    
    // size() 返回实际元素数量
    std::cout << "栈的大小: " << stack.size() << std::endl;  // 输出: 3
    
    // 无法直接获取底层容器的容量
    // 需要通过容器适配器获取
    auto& container = stack.c empty();
    
    return 0;
}

坑点2：在循环中错误使用 pop()

#include <iostream>
#include <stack>

int main() {
    std::stack<int> stack;
    for (int i = 1; i <= 5; i++) {
        stack.push(i);
    }
    
    // 错误：在循环中同时访问 size() 和 pop()
    for (int i = 0; i < stack.size(); i++) {
        std::cout << "弹出: " << stack.top() << std::endl;
        stack.pop();  // size() 会改变，导致循环次数错误
    }
    
    // 正确做法1：使用 while 循环
    while (!stack.empty()) {
        std::cout << "弹出: " << stack.top() << std::endl;
        stack.pop();
    }
    
    // 正确做法2：先保存 size
    std::stack<int> stack2;
    for (int i = 1; i <= 5; i++) {
        stack2.push(i);
    }
    
    size_t size = stack2.size();
    for (size_t i = 0; i < size; i++) {
        std::cout << "弹出: " << stack2.top() << std::endl;
        stack2.pop();
    }
    
    return 0;
}

五、Go Stack 的长度计算

5.1 使用切片作为栈

package main

import (
	"fmt"
)

// 方法1: 使用切片作为栈
func main() {
	stack := make([]string, 0)
	
	stack = append(stack, "Apple")
	stack = append(stack, "Banana")
	stack = append(stack, "Cherry")
	
	// 获取栈的长度
	length := len(stack)
	fmt.Printf("栈的长度: %d\n", length)  // 输出: 3
	
	// 检查是否为空
	isEmpty := len(stack) == 0
	fmt.Printf("栈是否为空: %v\n", isEmpty)  // 输出: false
	
	// 弹出元素
	for len(stack) > 0 {
		lastIndex := len(stack) - 1
		fmt.Printf("弹出: %s\n", stack[lastIndex])
		stack = stack[:lastIndex]
	}
}

5.2 使用结构体封装栈

”`go package main

import (

"fmt"

)

// 栈结构体 type Stack struct {

items []string

}

// 创建新栈 func NewStack() *Stack {

return &Stack{
	items: make([]string, 0),
}

}

// 压栈 func (s *Stack) Push(item string) {

s.items = append(s.items, item)

}

// 弹栈 func (s *Stack) Pop() (string, bool) {

if s.IsEmpty() {
	return "", false
}

lastIndex := len(s.items) - 1
item := s.items[lastIndex]
s.items = s.items[:lastIndex]

return item, true

}

// 查看栈顶元素 func (s *Stack) Peek() (string, bool) {

if s.IsEmpty() {
	return "", false
}

return s.items[len(s.items)-1], true

}

// 检查是否为空 func (s *Stack) IsEmpty() bool {

return len(s.items) == 0

}

// 获取栈的长度 func (s *Stack) Size() int {

return len(s.items)

}

// 清空栈 func (s *Stack) Clear() {

s.items = make([]string, 0)

}

func main() {

stack := NewStack()

stack.Push("Apple")
stack.Push("Banana")
stack.Push("Cherry")

fmt.Printf("栈的大小: %d\n", stack.Size())       // 输出: 3
fmt.Printf("栈顶元素: %s\n", stack.Peek())       // 输出: Cherry
fmt.Printf("栈是否为空: %v\n", stack.IsEmpty())  // 输出: false

// 弹出所有元素
for
-- 展开阅读全文 --