尽管数组是堆栈最常见的底层表示形式,但也可以使用链表实现Stack类。 如果这样做,空堆栈的概念表示就是NULL指针: 当你将新元素推入堆栈时,该元素只会添加到链表的前端。因此,如果将元素e1 push到空栈上,该元素将存储在一个新单元格中,该单元格将成为链中唯一的链接: 将一个新元素push栈将该元素添加到链的开头。所涉及的步骤与将字符插入链表列表缓冲区所需的步骤相同。 首先分配一个新的单元格,然后输入数据,最后更新链接指针,使新单元格成为链中的第一个元素。 因此,如果将元素e2推到栈上,将得到以下配置: 在链表表示中,pop操作包括删除链中的第一个单元格并返回存储在该列中的值。因此,来自上图所示的栈的pop操作返回e2并恢复栈的先前状态,如下所示:
先看一下这两个功能的实现(我们以数字栈为例子):
class StackInt { // in StackInt.hpublic: StackInt (); // constructor void push(int value); // append a value int pop(); // return the first-in valueprivate: struct Node { int value; Node * link; }; Node * data; // member variables};
void StackInt::push(int v) { Node * temp = new Node; temp->value = v; temp->link = data; data = temp;}
链栈是链表的一种,我们当然要画图去理解这个过程: (1) Node* data这句话的意思我们说过,就是建立一个指向这组数据的首指针,如图: (2)这个时候我们要push(7),因此我们的目的应该是这样的: (3)代码的前两句,是建立一个指向新的Node的指针,然后为新建的节点赋值为7,如下: (4)这里我们好像可以把第三句删了,直接 data = temp; 让我们看看会发生什么? (5)这里我们很明显看到,如果这样做,那么data就直接指向新的节点,但是新的节点并没有链接到我们的下一个数据,相当于断开了,因此正确的应该是这样: 然后: (6)最后我们可以执行删除操作,把我们的temp空间删除,大功告成!!
int StackInt::pop() { int toReturn = data->value; Node * temp = data; data = temp->link; delete temp; return toReturn;}
(1)首先我们把我们要pop出去的值给保存起来,定义一个新的变量: (2)如果我们直接用 data = data->link;而不建立临时的空间,我们来看看如果这样会怎么样 (3)这显然不是我们想要的,所以我们接着再试一次,首先我们建立临时变量: (4)然后我们将temp的link直接赋值给我们的data。如下; (5)最后删除节点,然后返回原来的值就ok了
由于我们并没有涉及到其他的数据移动,我们只是进行了一次的插入删除操作,所以他们的算法复杂度均为我们的O(1)
下一篇我们就用通用的模板来实现我们一般的链栈结构!