栈的实现过程拆解：数组和链表如何一步步造一个栈？

这篇咱们不绕弯，直接从 “造栈” 的角度出发，分别用数组和链表实现一个简单的 “商品 ID 栈”（存最近浏览的商品 ID），每一步都讲清 “结构怎么定义、内存怎么变、操作怎么执行”，看完你就能自己写一个栈。

一、用数组实现栈：3 步造一个 “固定容量的栈”

数组实现栈的核心是 “用数组存数据 + 用一个指针记栈顶位置”，因为数组是连续内存，操作栈顶只需要动指针，不用挪数据。咱们分 “定义结构→初始化→核心操作”3 步来实现。

1. 第一步：定义数组栈的 “骨架”（数据结构）

要实现一个能存商品 ID 的栈，需要 3 个关键部分：

• 数组 data：存商品 ID（比如 int 类型，每个 ID 占 4 字节）；

• 栈顶指针 top：记录当前栈顶的位置（用 int 表示，初始值很关键）；

• 容量 capacity：数组的最大大小（比如设为 5，最多存 5 个商品 ID）。

用代码表示（以 Java 为例，伪代码简化，好懂）：

// 数组栈的结构定义

class ArrayStack {

   int\[] data;       // 存商品ID的数组

   int top;          // 栈顶指针（记录栈顶索引）

   int capacity;     // 栈的最大容量（数组大小）

   // 构造方法：初始化栈

   public ArrayStack(int capacity) {

       this.capacity = capacity;

       this.data = new int\[capacity];  // 申请一个capacity大小的数组

       this.top = -1;                  // 栈顶指针初始为-1：表示栈是空的（没有元素）

   }

}

初始化后的内存状态：

假设我们初始化一个容量为 5 的栈（new ArrayStack(5)），内存里会有：

• 数组 data：占 20 字节（5 个 int，每个 4 字节），内存地址假设从0x400开始，此时数组里都是默认值 0（还没存数据）；

• 栈顶指针 top：存在栈对象里，值为 - 1（表示栈空，还没指向数组的任何索引）；

• 容量 capacity：值为 5，固定不变。

内存可视化（初始化后）：

2. 第二步：实现核心操作 1—— 压栈（push）：往栈顶加数据

压栈就是 “把商品 ID 存到栈顶”，核心是 “先动指针，再存数据”，因为 top 初始为 - 1，要先让 top 指向数组的第一个空位置（索引 0），再存数据。

压栈的步骤（以压入第一个商品 ID 1001 为例）：

1. 判满：先检查栈是不是满了（top == capacity-1）—— 如果 top 等于 4（capacity=5，5-1=4），说明数组索引 4 已经存了数据，栈满了，不能再压栈；

2. 指针上移：top 从 - 1 变成 0（top++），现在 top 指向数组索引 0（第一个空位置）；

3. 存数据：把商品 ID 1001 存到数组索引 0 的位置（data [0] = 1001）。

压栈后的内存变化：

再压入 2 个商品 ID（1002、1003）：

• 压 1002：top 从 0→1，data [1] = 1002；

• 压 1003：top 从 1→2，data [2] = 1003；

最终内存状态（存了 3 个数据）：

压栈的代码实现：

// 压栈：把商品ID存到栈顶

public boolean push(int goodsId) {

   if (top == capacity - 1) {  // 判满：top到最大索引，栈满了

       System.out.println("栈满了，不能再存数据了");

       return false;

   }

   top++;                      // 指针上移，指向新的栈顶位置

   data\[top] = goodsId;        // 存数据到栈顶

   return true;

}

3. 第三步：实现核心操作 2—— 弹栈（pop）：从栈顶删数据

弹栈就是 “把栈顶的商品 ID 取出来，并且从栈里删掉”，核心是 “先取数据，再动指针”—— 因为栈顶的数据在 top 指向的位置，取完后把 top 往下移，原来的栈顶数据就 “失效” 了（下次压栈会覆盖）。

弹栈的步骤（从存了 3 个数据的栈里弹栈）：

1. 判空：先检查栈是不是空的（top == -1）—— 如果 top 是 - 1，说明没数据，不能弹栈；

2. 取数据：把 top 指向的索引 2 的数据（1003）取出来（这是要返回给用户的 “最新浏览商品 ID”）；

3. 指针下移：top 从 2 变成 1（top--），现在栈顶指向索引 1 的 1002，原来索引 2 的 1003 虽然还在数组里，但栈已经 “不认” 它了（下次压栈会把新数据存到索引 2，覆盖 1003）。

弹栈后的内存变化：

弹栈的代码实现：

// 弹栈：从栈顶取数据，并删除栈顶

public Integer pop() {

   if (top == -1) {  // 判空：栈里没数据

       System.out.println("栈空了，没数据可弹");

       return null;

   }

   int topGoodsId = data\[top];  // 取栈顶数据

   top--;                      // 指针下移，栈顶“删除”原数据

   return topGoodsId;

}

4. 数组栈的其他关键操作（判空、取栈顶）

• 判空（isEmpty）：看 top 是不是 - 1，是就是空栈；

• 取栈顶（peek）：和弹栈类似，但只取数据不删（不用 top--），比如 “看最新浏览的商品 ID，但不删除”。

代码实现：

// 判空：栈是不是空的

public boolean isEmpty() {

   return top == -1;

}

// 取栈顶：看栈顶数据，不删除

public Integer peek() {

   if (top == -1) {

       System.out.println("栈空了，没数据可看");

       return null;

   }

   return data\[top];  // 直接返回top位置的数据，不动指针

}

二、用链表实现栈：3 步造一个 “无容量限制的栈”

链表实现栈的核心是 “用单链表存数据 + 链表头作为栈顶”—— 因为单链表的头节点增删最快（不用找前驱节点），刚好符合栈 “只操作栈顶” 的需求。同样分 “定义结构→初始化→核心操作”3 步实现。

1. 第一步：定义链表栈的 “骨架”（节点 + 栈结构）

链表栈需要两个部分：

• 链表节点（Node）：存单个商品 ID 和下一个节点的地址（指针）；

• 链表栈（LinkedStack）：用链表头（head）作为栈顶，记录栈顶位置（不用栈顶指针，头节点就是栈顶）。

用代码表示（Java 伪代码）：

// 1. 链表节点的结构：存数据+指向下一个节点的指针

class Node {

   int goodsId;  // 商品ID（数据域）

   Node next;    // 指向下一个节点的指针（地址）

   public Node(int goodsId) {

       this.goodsId = goodsId;

       this.next = null;  // 新节点默认没有下一个节点

   }

}

// 2. 链表栈的结构：用头节点（head）作为栈顶

class LinkedStack {

   Node head;  // 栈顶 = 链表头节点（存最新的商品ID）

   // 初始化栈：头节点为null，栈空

   public LinkedStack() {

       this.head = null;

   }

}

初始化后的内存状态：

初始化一个链表栈（new LinkedStack()），内存里只有一个栈对象，head 指针为 null（表示栈空，没有任何节点）。

内存可视化（初始化后）：

2. 第二步：实现核心操作 1—— 压栈（push）：往栈顶（链表头）加节点

链表栈的压栈是 “在链表头插一个新节点”—— 因为头节点是栈顶，新节点插在头前面，新节点就变成新的栈顶，操作最快（只改指针，不用找其他节点）。

压栈的步骤（压入第一个商品 ID 1001 为例）：

1. 新建节点：创建一个新 Node，数据是 1001，next 指针为 null（刚创建时没指向任何节点）；

2. 新节点指向原头节点：原头节点是 null（栈空），所以新节点的 next = null；

3. 头节点更新为新节点：栈的 head 指针指向新节点，新节点变成新的栈顶。

压栈后的内存变化（存 1001）：

• 新节点内存地址假设为0x200，数据 1001，next=null；

• head 指针指向0x200（新节点是栈顶）。

内存可视化：

再压入 2 个商品 ID（1002、1003）：

• 压 1002：

1. 新建节点（地址0x20C，数据 1002）；

2. 新节点的 next = 原 head（0x200，指向 1001 的节点）；

3. head 更新为 0x20C（新节点是栈顶）；

• 压 1003：

1. 新建节点（地址0x218，数据 1003）；

2. 新节点的 next = 原 head（0x20C，指向 1002 的节点）；

3. head 更新为 0x218（新节点是栈顶）。

最终内存状态（存了 3 个数据）：

压栈的代码实现：

// 压栈：在链表头插新节点（新节点成为栈顶）

public void push(int goodsId) {

   // 1. 新建节点

   Node newNode = new Node(goodsId);

   // 2. 新节点指向原头节点（原栈顶）

   newNode.next = head;

   // 3. 头节点更新为新节点（新节点成栈顶）

   head = newNode;

}

3. 第三步：实现核心操作 2—— 弹栈（pop）：从栈顶（链表头）删节点

链表栈的弹栈是 “删除链表头节点”—— 因为头节点是栈顶，删头节点就是删栈顶，操作最快（只改 head 指针，不用找其他节点）。

弹栈的步骤（从存了 3 个数据的栈里弹栈）：

1. 判空：检查 head 是不是 null（栈空），是就不能弹栈；

2. 取栈顶数据：头节点（0x218）的数据是 1003，先把这个数据取出来；

3. 头节点更新为原头节点的 next：原头节点（0x218）的 next 指向 0x20C（1002 的节点），所以 head 更新为 0x20C（1002 的节点变成新栈顶）；

4. 原头节点失效：原来的头节点（0x218，数据 1003）没有指针指向它了，会被垃圾回收（相当于从栈里删掉）。

弹栈后的内存变化：

• head 指针现在指向 0x20C（1002 的节点，新栈顶）；

• 原头节点 0x218（1003）变成垃圾内存，后续会被回收。

内存可视化：

弹栈的代码实现：

// 弹栈：删除链表头节点（栈顶），并返回数据

public Integer pop() {

   if (head == null) {  // 判空：栈里没节点

       System.out.println("栈空了，没数据可弹");

       return null;

   }

   int topGoodsId = head.goodsId;  // 取栈顶（头节点）数据

   head = head.next;               // 头节点更新为下一个节点，原头节点失效

   return topGoodsId;

}

4. 链表栈的其他关键操作（判空、取栈顶）

• 判空（isEmpty）：看 head 是不是 null，是就是空栈；

• 取栈顶（peek）：只取头节点的数据，不删节点（不用改 head）。

代码实现：

// 判空：栈是不是空的

public boolean isEmpty() {

   return head == null;

}

// 取栈顶：看栈顶数据，不删除

public Integer peek() {

   if (head == null) {

       System.out.println("栈空了，没数据可看");

       return null;

   }

   return head.goodsId;  // 直接返回头节点数据，不动指针

}

三、数组栈 vs 链表栈：核心区别和选型建议

现在你已经知道两种实现的完整过程了，最后总结一下它们的区别，帮你选对实现方式：

选型建议：

• 如果你知道栈最多存多少数据（比如 “最近浏览最多 10 条”），用数组栈 —— 速度快、省内存；

• 如果你不知道栈的最大数据量（比如 “浏览记录不限条数”），用链表栈 —— 无容量限制，不会溢出。

最后：一句话搞懂栈的实现本质

• 数组栈：用 “连续内存的数组” 存数据，用 “top 指针” 记栈顶，操作栈顶就是 “动指针 + 存 / 取数组数据”；

• 链表栈：用 “离散的节点” 存数据，用 “链表头” 当栈顶，操作栈顶就是 “头插 / 头删节点 + 改 head 指针”。

不管是哪种实现，栈的核心规则 “先进后出” 都没变 —— 只是用不同的内存结构（连续 vs 离散）来实现这个规则，搞懂实现过程，你就真的懂栈了。