12 项目 3 - 构建堆栈数据结构
在本章中，我们将实现一个堆栈数据结构，作为本书的下一个小项目。用任何语言实现基本数据结构在计算机科学（CS）中都属于“幼儿园任务”（如果这个术语存在的话），因为我们通常在CS的第一个学期学习和实现它们。
但这实际上很好！因为这应该是一个非常简单的任务，我们不需要太多解释什么是堆栈，然后，我们可以专注于真正重要的事情，即学习如何在 Zig 语言中实现“泛型”的概念，以及 Zig 的一个关键特性，即计算时间，是如何工作的，并使用堆栈数据结构来动态演示这些概念。
但在开始构建堆栈数据结构之前，我们首先需要了解comptime关键字对代码的作用，之后，我们还需要了解泛型在 Zig 中的工作原理。
12.1comptime Zig 中的理解
Zig 的一个关键特性是comptime。这个关键字引入了一个全新的概念和范式，它与编译过程紧密相关。在第 3.1.1 节中，我们描述了“编译时与运行时”在 Zig 中的重要性和作用。在那一节中，我们了解到，应用于值/对象的规则会根据该值是在编译时已知还是仅在运行时已知而发生很大变化。
关键字comptime与这两个时间空间（编译时和运行时）密切相关。让我们快速回顾一下它们之间的区别。编译时是指zig编译器编译 Zig 源代码的时间段，而运行时是指执行 Zig 程序的时间段，即我们执行编译器生成的二进制文件的时间zig。
有三种方法可以应用comptime关键字，分别是：
- 应用于
comptime函数参数。 - 应用于
comptime物体。 - 应用于
comptime一组表达式。
12.1.1应用函数参数
comptime当你在函数参数上应用该关键字时，你是在告诉zig编译器，赋给该特定函数参数的值必须在编译时已知。我们在3.1.1 节详细解释了“编译时已知的值”的具体含义。所以，如果你对此有任何疑问，请参考该节。
现在让我们思考一下这个想法的后果。首先，我们对特定的函数参数施加了一个限制，或者说一个要求。如果程序员不小心尝试给这个函数参数赋一个编译时未知的值，编译器zig会注意到这个问题，并因此引发编译错误，提示无法编译你的程序。因为你给一个必须“编译时已知”的函数参数提供了一个“运行时已知”的值。
请看下面这个非常简单的例子，我们定义了一个twice()名为 的函数，它只是将输入值加倍num。注意，我们comptime在函数参数名称前使用了 关键字。这个关键字将函数参数标记num为“comptime 参数”。
这是一个函数参数，其值必须是编译时已知的。这就是为什么表达式twice(5678)是有效的，并且不会引发编译错误。因为该值5678是编译时已知的，所以这是该函数的预期行为。
fn twice(comptime num: u32) u32 {
return num * 2;
}
test "test comptime" {
_ = twice(5678);
}
1/1 filef044375a1f16.test.test comptime...OKAll 1
tests passed.
但是，如果我们提供一个函数在编译时不知道的数字，该怎么办？例如，你的程序可能会通过stdin系统通道接收来自用户的输入。来自用户的输入可能有很多种，并且在编译时无法预测。这些情况使得这个“来自用户的输入”成为一个只有运行时才知道的值。
在下面的例子中，这个“来自用户的输入”最初以字符串的形式接收，然后被解析并转换为整数值，并且此操作的结果存储在n对象内部。
由于“用户的输入”仅在运行时才可知，因此对象的值n也仅在运行时确定。因此，我们无法将此对象作为twice()函数的输入。zig编译器不允许这样做，因为我们将num参数标记为“comptime 参数”。因此，zig编译器会引发如下所示的编译时错误：
const std = @import("std");
fn twice(comptime num: u32) u32 {
return num * 2;
}
pub fn main() !void {
var buffer: [5]u8 = .{ 0, 0, 0, 0, 0 };
const stdout = std.io.getStdOut().writer();
const stdin = std.io.getStdIn().reader();
_ = try stdout.write("Please write a 4-digit integer number\n");
_ = try stdin.readUntilDelimiter(&buffer, '\n');
try stdout.print("Input: {s}", .{buffer});
const n: u32 = try std.fmt.parseInt(
u32, buffer[0 .. buffer.len - 1], 10
);
const twice_result = twice(n);
try stdout.print("Result: {d}\n", .{twice_result});
}
t.zig:12:16: error: unable to resolve comptime value
const twice_result = twice(n);
^
Comptime 参数经常用于返回某种泛型结构的函数。事实上，这是在 Zig 中创建泛型的本质（或基础）。我们将在第 12.2 节comptime中详细讨论泛型。
现在，让我们看一下Seguin ( 2024 )中的这段代码示例。您可以看到，此IntArray()函数有一个名为 的参数length。此参数标记为 comptime，并接收一个 类型的值usize作为输入。因此，赋予此参数的值必须是编译时已知的。我们还可以看到，此函数返回一个i64值数组作为输出。
fn IntArray(comptime length: usize) type {
return [length]i64;
}
现在，这个函数的关键部分是length参数。这个参数用于确定函数生成的数组的大小。让我们思考一下这样做的后果。如果数组的大小取决于赋给length参数的值，这意味着函数输出的数据类型取决于这个参数的值length。
仔细思考一下这句话。正如我在1.2.2 节中所述，Zig 是一种强类型语言，尤其是在函数声明方面。因此，每次用 Zig 编写函数时，我们都必须注释函数返回值的数据类型。但是，如果这种数据类型取决于赋予函数参数的值，我们该怎么做呢？
想一想。length例如，如果 等于 3，那么函数的返回类型就是[3]i64。但如果length等于 40，那么返回类型就变成了[40]i64。这时zig编译器就会感到困惑，并引发编译错误，如下所示：
嘿！你注释了这个函数应该返回一个
[3]i64值，但我得到的[40]i64却是一个值！这看起来不对劲！
那么该如何解决这个问题呢？我们该如何克服这个障碍呢？这时type关键字就派上用场了。这个type关键字的作用是告诉编译器，这个函数将返回某种数据类型，但它还不知道具体是什么数据类型。我们将在12.2 节zig中详细讨论这个问题。
12.1.2应用表达式
当你在表达式上应用该comptime关键字时，编译器保证会zig在编译时执行此表达式。如果由于某种原因，此表达式无法在编译时执行（例如，此表达式可能依赖于一个只有在运行时才知道的值），那么zig编译器将引发编译错误。
以 Zig 官方文档（Zig Software Foundation 2024）中的这个例子为例。我们fibonacci()在运行时和编译时都执行同一个函数。该函数默认在运行时执行，但由于我们comptime在第二个“try 表达式”中使用了关键字，因此该表达式在编译时执行。
这可能会让一些人感到困惑。没错！当我说这个表达式在编译时执行时，我的意思是这个表达式是在zig编译器编译 Zig 源代码时编译并执行的。
const expect = @import("std").testing.expect;
fn fibonacci(index: u32) u32 {
if (index < 2) return index;
return fibonacci(index - 1) + fibonacci(index - 2);
}
test "fibonacci" {
// test fibonacci at run-time
try expect(fibonacci(7) == 13);
// test fibonacci at compile-time
try comptime expect(fibonacci(7) == 13);
}
1/1 filef0447cb16f4d.test.fibonacci...OKAll 1 test
ts passed.
很多 Zig 源代码可能会在编译时执行，因为编译器可以计算出某些表达式的输出。尤其是当这些表达式仅依赖于编译时已知值时。我们在第 3.1.1 节zig中讨论过这个问题。
comptime但是当你在表达式上使用关键字时，就不再有“它可能在编译时执行”的说法了。使用comptime关键字，你命令zig编译器在编译时执行这个表达式。你强加了这条规则，保证了编译器总是会在编译时执行它。或者，至少，编译器会尝试执行它。如果编译器因为任何原因无法执行该表达式，编译器将引发编译错误。
12.1.3应用到块上
块在1.7 节中进行了描述。将comptime关键字应用于表达式块时，其效果与将此关键字应用于单个表达式基本相同。也就是说，编译器会在编译时执行整个表达式块zig。
在下面的例子中，我们将标有的块标记blk为 comptime 块，因此，该块内的表达式在编译时执行。
const expect = @import("std").testing.expect;
fn fibonacci(index: u32) u32 {
if (index < 2) return index;
return fibonacci(index - 1) + fibonacci(index - 2);
}
test "fibonacci in a block" {
const x = comptime blk: {
const n1 = 5;
const n2 = 2;
const n3 = n1 + n2;
try expect(fibonacci(n3) == 13);
break :blk n3;
};
_ = x;
}
1/1 filef044524d5e27.test.fibonacci in a block...O
OKAll 1 tests passed.
12.2泛型介绍
首先，什么是泛型？泛型的理念是允许一个类型（f64以及u8用户自定义类型，例如我们在2.3 节中定义的结构体）作为方法、类和接口（Geeks for Geeks 2024）u32的参数。换句话说，“泛型”是一个可以处理多种数据类型的类（或方法）。bool``User
例如，在 Java 中，泛型是通过运算符 创建的<>。使用此运算符，Java 类能够接收某种数据类型作为输入，因此该类可以根据此输入数据类型调整其功能。再例如，C++ 中的泛型是通过模板的概念来支持的。C++ 中的类模板就是泛型。
在 Zig 中，泛型是通过 实现的comptime。该comptime关键字允许我们在编译时收集数据类型，并将该数据类型作为输入传递给一段代码。
12.2.1泛型函数
以max()下面展示的函数作为第一个例子。这个函数本质上是一个“泛型函数”。在这个函数中，我们有一个名为 的 comptime 函数参数T。注意，这个T参数的数据类型是type。很奇怪吧？这个type关键字在 Zig 中是“所有类型之父”，或者说是“类型的类型”。
因为我们在参数中使用了 thistype关键字T，所以我们告诉zig编译器此T参数将接收某种数据类型作为输入。还要注意comptime此参数中关键字的用法。正如我在12.1 节中所述，每次在函数参数中使用 this 关键字时，都意味着此参数的值必须在编译时已知。这很合理，对吧？因为没有哪种数据类型在编译时是未知的。
想想看。你编写的任何数据类型在编译时都是已知的。尤其因为数据类型是编译器实际编译源代码的必要信息。考虑到这一点，将此参数标记为 comptime 参数是有意义的。
fn max(comptime T: type, a: T, b: T) T {
return if (a > b) a else b;
}
还要注意，参数的值T实际上用于定义函数中其他参数的数据类型，a以及b，以及函数的返回类型注释。也就是说，这些参数的数据类型（a和b），以及函数本身的返回数据类型，由赋予参数的输入值决定T。
因此，我们有一个可以处理不同数据类型的泛型函数。例如，我可以u8为该max()函数提供值，它会按预期工作。但如果我提供f64值，它也会按预期工作。如果没有泛型函数，我将不得不max()为每种想要使用的数据类型编写不同的函数。这个泛型函数为我们提供了一个非常有用的快捷方式。
const std = @import("std");
fn max(comptime T: type, a: T, b: T) T {
return if (a > b) a else b;
}
test "test max" {
const n1 = max(u8, 4, 10);
std.debug.print("Max n1: {d}\n", .{n1});
const n2 = max(f64, 89.24, 64.001);
std.debug.print("Max n2: {d}\n", .{n2});
}
Max n1: 10
Max n2: 89.24
12.2.2通用数据结构
Zig 标准库中所有数据结构（例如 ArrayList、HashMap等）本质上都是通用数据结构。这些数据结构之所以通用，是因为它们可以处理任何你想要的数据类型。你只需指定要存储在这个数据结构中的值的数据类型，它们就能按预期工作。
Zig 中的通用数据结构是如何从 Java 复制通用类，或从 C++ 复制类模板的。但你可能会问自己：如何在 Zig 中构建通用数据结构？
其基本思想是编写一个泛型函数，用于创建我们想要的特定类型的数据结构定义。换句话说，这个泛型函数就像一个“数据结构工厂”。泛型函数输出struct为特定数据类型定义该数据结构的定义。
要创建这样的函数，我们需要为该函数添加一个 comptime 参数，该参数接收一个数据类型作为输入。我们已经在上一节（12.2.1 节）学习了如何实现这一点。我认为演示如何创建通用数据结构的最佳方法是实际编写一个。本书的下一个小项目就在这里。这是一个非常小的项目，旨在编写一个通用堆栈数据结构。
12.3什么是堆栈？
堆栈数据结构是一种遵循 LIFO（后进先出）原则的结构。堆栈数据结构通常仅支持两种操作： 和push。pop操作push用于向堆栈中添加新值，而pop操作用于从堆栈中删除值。
当人们尝试解释堆栈数据结构的工作原理时，他们最常用的类比是一叠盘子。想象一下，你有一叠盘子，例如，你的桌子上有 10 个盘子。每个盘子代表当前存储在此堆栈中的一个值。
我们从一叠包含 10 个不同值（或 10 个不同的盘子）的堆栈开始。现在，假设你想向这个堆栈中添加一个新盘子（或一个新的值），这相当于一个push操作。你只需将新盘子放在堆栈顶部即可添加这个盘子（或这个值）。然后，堆栈中的盘子数量将增加到 11 个。
但是，如何从这个堆栈中移除盘子（或移除其中的物品）（也就是pop操作）呢？要做到这一点，我们必须移除堆栈顶部的盘子，这样，堆栈中又会有 10 个盘子。
这演示了后进先出（LIFO）的概念，因为栈中的第一个盘子，也就是栈底的盘子，总是最后一个被取出。想想看，为了从栈中取出这个特定的盘子，我们必须取出栈中的所有盘子。因此，栈中的每个操作，无论是插入还是删除，总是在栈顶进行。下图 12.1直观地展示了这一逻辑：
图 12.1：堆栈结构图。来源：维基百科，自由的百科全书。
12.4编写堆栈数据结构
我们将分两步编写堆栈数据结构。首先，我们将实现一个只能存储u32值的堆栈。然后，我们将扩展我们的实现，使其具有通用性，以便它能够处理我们想要的任何数据类型。
首先，我们需要确定如何在栈中存储值。栈结构背后的存储机制有多种实现方式。有些人喜欢使用双向链表，有些人喜欢使用动态数组等等。在本例中，我们将使用一个数组来存储栈中的值，也就是items我们结构体定义的数据成员Stack。
还要注意Stack，我们的结构体中还有另外三个数据成员：capacity、length和allocator。capacity成员包含存储堆栈中值的底层数组的容量。length包含当前存储在堆栈中的值的数量。allocator包含分配器对象，每当堆栈结构需要为正在存储的值分配更多空间时，它将使用该对象。
我们首先定义init()该结构体的一个方法，该方法负责实例化一个Stack对象。注意，在这个init()方法内部，我们首先根据参数指定的容量分配一个数组capacity。
const std = @import("std");
const Allocator = std.mem.Allocator;
const Stack = struct {
items: []u32,
capacity: usize,
length: usize,
allocator: Allocator,
pub fn init(allocator: Allocator, capacity: usize) !Stack {
var buf = try allocator.alloc(u32, capacity);
return .{
.items = buf[0..],
.capacity = capacity,
.length = 0,
.allocator = allocator,
};
}
};
12.4.1实施push操作
现在我们已经编写了创建新对象的基本逻辑Stack，接下来可以开始编写执行推送操作的逻辑了。记住，在堆栈数据结构中，推送操作是将新值添加到堆栈的操作。
那么，我们如何向Stack已有的对象添加新值呢？push()下面给出的函数可能是这个问题的答案。还记得我们在12.3 节中讨论过的内容吗？值总是被添加到栈顶。这意味着该push()函数必须始终在底层数组中找到当前表示栈顶位置的元素，然后将输入值添加到那里。
首先，这个函数中有一个 if 语句。这个 if 语句检查是否需要扩展底层数组来存储添加到堆栈的新值。换句话说，底层数组可能没有足够的容量来存储这个新值，在这种情况下，我们需要扩展数组以获得所需的容量。
因此，如果此 if 语句中的逻辑测试返回 true，则表示数组容量不足，我们需要先扩展它，然后再存储新值。因此，在此 if 语句中，我们执行必要的表达式来扩展底层数组。请注意，我们使用分配器对象分配了一个比当前数组大两倍的新数组（self.capacity * 2）。
之后，我们使用另一个名为 的内置函数@memcpy()。此内置函数相当于memcpy()C 标准库1中的函数。它用于将值从一个内存块复制到另一个内存块。换句话说，你可以使用此函数将值从一个数组复制到另一个数组。
我们使用这个@memcpy()内置函数将当前存储在堆栈对象底层数组 ( self.items) 中的值复制到我们分配的新的更大的数组 ( new_buf) 中。执行此函数后，new_buf包含当前 处的值的副本self.items。
现在我们已经在对象中获得了当前值的副本new_buf，现在可以释放当前分配在 处的内存了self.items。之后，我们只需要将新的更大的数组赋值给self.items。这是扩展数组所需的步骤序列。
pub fn push(self: *Stack, val: u32) !void {
if ((self.length + 1) > self.capacity) {
var new_buf = try self.allocator.alloc(
u32, self.capacity * 2
);
@memcpy(
new_buf[0..self.capacity], self.items
);
self.allocator.free(self.items);
self.items = new_buf;
self.capacity = self.capacity * 2;
}
self.items[self.length] = val;
self.length += 1;
}
在确保有足够的空间存储要添加到堆栈的新值之后，我们要做的就是将该值赋给堆栈的顶部元素，并将length属性的值加一。我们使用该length属性找到堆栈中的顶部元素。
12.4.2实施pop操作
现在我们可以实现栈对象的弹出操作了。这是一个更容易实现的操作，pop()下面的方法总结了所需的所有逻辑。
我们只需要在底层数组中找到当前代表栈顶的元素，并将该元素设置为“undefined”，以指示该元素为“空”。之后，我们还需要将length栈的属性减一。
如果堆栈的当前长度为零，则表示堆栈中当前没有存储任何值。因此，在这种情况下，我们可以直接返回，什么也不做。这就是此函数中的 if 语句所检查的内容。
pub fn pop(self: *Stack) void {
if (self.length == 0) return;
self.items[self.length - 1] = undefined;
self.length -= 1;
}
12.4.3实现deinit方法
我们实现了负责与堆栈数据结构相关的两个主要操作的方法，即pop()和push()，我们还实现了负责实例化新Stack对象的方法，即init()方法。
但现在，我们还需要实现负责销毁对象的方法Stack。在 Zig 中，此任务通常与名为 的方法相关联deinit()。Zig 中的大多数结构体对象都具有此类方法，它通常被称为“析构函数方法”。
理论上，要销毁Stack对象，我们只需确保使用存储在Stack对象内部的分配器对象释放为底层数组分配的内存。下面的方法就是这样deinit()做的。
pub fn deinit(self: *Stack) void {
self.allocator.free(self.items);
}
12.5使其通用
现在我们已经实现了堆栈数据结构的基本框架，接下来可以集中讨论如何使其具有泛型。如何使这个基本框架不仅能处理u32值，还能处理我们想要的任何其他数据类型？例如，我们可能需要创建一个堆栈对象来存储User值。如何实现这一点？答案在于使用泛型和comptime。
正如我在12.2.2 节中所述，其基本思想是编写一个返回结构体定义作为输出的泛型函数。理论上，我们不需要做太多工作就能将Stack结构体转换为泛型数据结构。我们只需要将堆栈的底层数组转换为泛型数组即可。
换句话说，这个底层数组需要像一条“变色龙”。它需要适应变化，并将其转换为我们想要的任何数据类型。例如，如果我们需要创建一个用于存储u8值的堆栈，那么这个底层数组就需要是一个u8数组（即[]u8）。但如果我们需要存储User值，那么这个数组就需要是一个User数组（即[]User）。等等。
我们可以使用泛型函数来实现这一点。因为泛型函数可以接收一种数据类型作为输入，并且我们可以将这种数据类型传递给Stack对象的结构体定义。因此，我们可以使用泛型函数创建一个Stack可以存储所需数据类型的对象。如果我们想要创建一个存储User值的堆栈结构，我们将数据类型传递给这个泛型函数，它会为我们创建一个描述可以在其中存储值的对象User的结构体定义。Stack``User
请看下面的代码示例。Stack为了简洁起见，我省略了结构体定义的某些部分。但是，如果Stack本例中没有暴露结构体的某个特定部分，那是因为这部分与上一个示例相比没有变化。它保持不变。
fn Stack(comptime T: type) type {
return struct {
items: []T,
capacity: usize,
length: usize,
allocator: Allocator,
const Self = @This();
pub fn init(allocator: Allocator,
capacity: usize) !Stack(T) {
var buf = try allocator.alloc(T, capacity);
return .{
.items = buf[0..],
.capacity = capacity,
.length = 0,
.allocator = allocator,
};
}
pub fn push(self: *Self, val: T) !void {
// Truncate the rest of the struct
};
}
请注意，我们在此示例中创建了一个名为 的函数Stack()。该函数接受一个类型作为输入，并将该类型传递给Stack对象的结构体定义。数据成员items现在是一个类型为 的数组T，该类型是我们提供给函数的输入数据类型。函数val中的函数参数push()现在也是一个类型为 的值T。
我们只需为该函数提供一个数据类型，它就会创建一个Stack对象的定义，该对象可以存储我们指定的数据类型的值。在下面的示例中，我们创建了一个Stack可以存储u8值的对象的定义。该定义存储在Stacku8对象中。这个Stacku8对象将成为我们的新结构体，我们将使用它来创建我们的Stack对象。
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
const Stacku8 = Stack(u8);
var stack = try Stacku8.init(allocator, 10);
defer stack.deinit();
try stack.push(1);
try stack.push(2);
try stack.push(3);
try stack.push(4);
try stack.push(5);
try stack.push(6);
std.debug.print("Stack len: {d}\n", .{stack.length});
std.debug.print("Stack capacity: {d}\n", .{stack.capacity});
stack.pop();
std.debug.print("Stack len: {d}\n", .{stack.length});
stack.pop();
std.debug.print("Stack len: {d}\n", .{stack.length});
std.debug.print(
"Stack state: {any}\n",
.{stack.items[0..stack.length]}
);
Stack len: 6
Stack capacity: 10
Stack len: 5
Stack len: 4
Stack state: { 1, 2, 3, 4, 0, 0, 0, 0, 0, 0 }
Zig 标准库（ArrayList、、等）中的每个通用数据结构HashMap都是SinlyLinkedList通过此逻辑实现的。它们使用通用函数来创建可以与您提供的输入数据类型一起使用的结构体定义。
12.6结论
本章讨论的堆栈结构的完整源代码可在本书的官方仓库中免费获取。只需查看仓库文件夹中提供的2版本（我们的堆栈版本）和 3 版本（通用版本） 。stack.zigu32generic_stack.zigZigExamples