堆栈是一种抽象数据类型(ADT),通常在大多数编程语言中使用,它被称为堆栈,因为它的行为类似于现实世界中的堆栈,如,一副纸牌或一堆盘子等。
实际堆栈仅允许在一端进行操作。如我们只能从堆栈顶部放置或取出数据。同样堆栈ADT仅允许在一端进行所有数据操作。在任何给定时间,我们只能访问堆栈的顶部元素。
此函数使其成为LIFO数据结构,LIFO代表后进先出。在此首先访问最后放置(插入或添加)的元素。在堆栈术语中,插入操作称为 PUSH 操作,而删除操作称为 POP 操作。
下图描述了堆栈及其操作-
堆栈可以通过数组,结构,指针和链表实现,堆栈可以是固定大小的堆栈,也可以具有动态调整大小的感觉。在这里,我们将使用数组来实现堆栈,这使其成为固定大小的堆栈实现。
堆栈操作可能涉及初始化堆栈,使用堆栈然后取消初始化。除了这些基本内容,堆栈还用于以下两个主要操作-
push() - 将一个元素压入堆栈。
pop() - 从堆栈中删除元素。
peek() - 获取堆栈的顶部数据元素,而不删除它。
isFull() - 检查堆栈是否已满。
isEmpty() - 检查堆栈是否为空。
peek() - 函数的算法-
begin procedure peek return stack[top] end procedure
用C编程语言实现peek()函数-
int peek() { return stack[top]; }
isfull() - 函数的算法-
begin procedure isfull if top equals to MAXSIZE return true else return false endif end procedure
用C编程语言实现isfull()函数-
bool isfull() { if(top == MAXSIZE) return true; else return false; }
isempty() - 函数的算法-
begin procedure isempty if top less than 1 return true else return false endif end procedure
用C编程语言实现isempty()函数略有不同。我们将top初始化为-1,因为数组中的索引从0开始。因此我们检查top是否小于0或-1以确定堆栈是否为空。
bool isempty() { if(top == -1) return true; else return false; }
将新数据元素放入堆栈的进程称为推入操作,推送操作涉及一系列步骤-
步骤1 - 检查堆栈是否已满。
步骤2 - 如果堆栈已满,则会产生错误并退出。
步骤3 - 如果堆栈未满,则将 top 递增以指向下一个空白空间。
步骤4 - 将数据元素添加到顶部指向的堆栈位置。
步骤5 - 返回成功。
如果使用链表实现堆栈,则在步骤3中,我们需要动态分配空间。
推操作的简单算法可以得出如下-
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()操作的数组实现中,实际上未删除数据元素,而是将top递减到堆栈中下一个值。但是在链表实现中,pop()实际上会删除数据元素并重新分配内存空间。
pop操作可能涉及以下步骤-
步骤1 - 检查堆栈是否为空。
步骤2 - 如果堆栈为空,则会产生错误并退出。
步骤3 - 如果堆栈不为空,则访问 top 所指向的数据元素。
步骤4 - 将top的值减小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"); } }
#include <stdio.h> int MAXSIZE = 8; int stack[8]; int top = -1; int isempty() { if(top == -1) return 1; else return 0; } int isfull() { if(top == MAXSIZE) return 1; else return 0; } int peek() { return stack[top]; } int pop() { int data; if(!isempty()) { data = stack[top]; top = top - 1; return data; } else { printf("Could not retrieve data, Stack is empty.\n"); } } int push(int data) { if(!isfull()) { top = top + 1; stack[top] = data; } else { printf("Could not insert data, Stack is full.\n"); } } int main() { // push items on to the stack push(3); push(5); push(9); push(1); push(12); push(15); printf("Element at top of the stack: %d\n" ,peek()); printf("Elements:\n"); // print stack data while(!isempty()) { int data = pop(); printf("%d\n",data); } printf("Stack full: %s\n" , isfull()?"true":"false"); printf("Stack empty: %s\n" , isempty()?"true":"false"); return 0; }
Element at top of the stack: 15 Elements: 15 12 1 9 5 3 Stack full: false Stack empty: true
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)