堆栈是一个抽象数据类型(ADT),在大多数编程语言中常用。它被命名堆,因为它就像一个现实世界的堆,例如 - 扑克牌板或堆等。
一个真实世界的堆栈允许保存操作仅在一端进行。例如,我们只可以把或从堆栈顶部取出存储卡或板。同样地,堆栈ADT允许仅在一端执行所有数据操作。在任何特定时间,我们只能访问一个堆栈的顶部元素。
这一特点使它成为后进先出的数据结构。 LIFO表示后进先出。这里放置(插入或添加)最后元素,在第一次访问。在堆的术语中,插入操作被称为PUSH操作,删除操作称为POP操作。
堆栈表示
如下图试图描绘出堆栈及其操作 -
堆栈可通过数组,结构和链表来实现。堆栈可以是固定大小或它可动态调整。在这里,我们要实现使用堆栈数组,这使用的是一个固定大小的堆栈实现。
基本操作
堆栈操作可能涉及初始化堆栈,使用它,然后去对其进行初始化。除了这些基本的东西,堆栈用于以下两个主要的操作 -
-
push() − 推(存储)在栈上的元素。
-
pop() − 除去(访问)堆栈上的元素。
当数据被压入堆栈。
要使用堆栈有效,我们需要检查栈的情况也是如此。为了同样的目的,下面的功能添加到栈 -
-
peek() − 得到的堆栈顶部的数据元素,但不删除它。
-
isFull() − 检查堆栈是否满了。
-
isEmpty() − 检查堆栈是否为空的。
在任何时候,我们保持一个指向最后压入堆栈的数据。这种指针总是代表堆栈的顶部,因此命名为:top(顶部)。顶部指针提供堆栈顶部的值,但不删除它。
首先,我们应该了解程序,以支持堆栈功能 -
peek()
peek()函数算法
begin procedure peek return stack[top] end procedure
peek()函数的 C语言编程实现,如下:
int peek() { return stack[top]; }
isfull()
isfull()函数算法:
begin procedure isfull if top equals to MAXSIZE return true else return false endif end procedure
isfull()函数的C语言编程实现
bool isfull() { if(top == MAXSIZE) return true; else return false; }
isempty()
isEmpty()函数算法
begin procedure isempty if top less than 1 return true else return false endif end procedure
isEmpty()函数的 C语言编程实现略有不同。我们初始化顶部值为 -1, 由于指数数组从0开始。因此,我们检查如果顶部是小于零或-1,以确定是否堆栈是空的。下面的代码
bool isempty() { if(top == -1) return true; else return false; }
PUSH/推送操作
把一个新的数据元素到堆栈的过程被称为推入操作。推操作涉及一系列步骤 -
-
步骤 1 − 检查堆栈是否满了
-
步骤 2 − 如果堆栈已满,则产生错误并退出
-
步骤 3 − 如果堆栈未满,增加顶部指向下一个空的空间
-
步骤 4 − 添加数据元素堆栈位置,其中指向顶部
-
步骤 5 − 返回成功
如果链表用于实现堆栈,则在步骤3中,我们需要动态分配的空间。
算法PUSH操作
一个简单的算法推送操作可推导如下 -
begin procedure push: stack, data if stack is full return null endif top ← top + 1 stack[top] ← data end procedure
这个算法用C语言来实现,是很容易的。请参见下面的代码 -
void push(int data) { if(!isFull()) { top = top + 1; stack[top] = data; } else { printf("Could not insert data, Stack is full.\n"); } }
弹出操作
访问内容要从堆栈取出,被称为弹出操作。在数组实现POP()操作,数据元素实际上未被删除,而是顶部递减到一个较低的位置,栈指向下一个值。但在链表实现,pop()方法实际上删除数据元素,并释放内存空间。
弹出操作可能包括以下步骤 −
-
步骤 1 − 检查堆栈是否为空
-
步骤 2 − 如果栈为空,则产生错误并退出
-
步骤 3 − 如果堆栈不空,访问数据元素是在顶部指向
-
步骤 4 − 顶部值降低1
-
步骤 5 − 返回成功
POP算法操作
一个简单的算法弹出操作可以如下 -
begin procedure pop: stack if stack is empty return null endif data ← stack[top] top ← top - 1 return data end procedure
这个算法的 C语言实现,如下所示 -
int pop(int data) { if(!isempty()) { data = stack[top]; top = top - 1; return data; } else { printf("Could not retrieve data, Stack is empty.\n"); } }
对于C编程语言的完整堆栈程序,请点击