堆栈
堆栈是一种抽象数据类型 (ADT)，通常用于大多数编程语言。它被命名为堆栈，因为它的行为类似于现实世界的堆栈，例如-一副纸牌或一堆盘子等。
现实世界的堆栈只允许在一端进行操作。例如，我们只能从堆栈顶部放置或移除卡片或盘子。同样，堆栈 ADT 仅允许在一端进行所有数据操作。在任何给定时间，我们只能访问堆栈的顶部元素。
此功能使其成为 LIFO 数据结构。 LIFO 代表后进先出。在这里，最后放置（插入或添加）的元素首先被访问。在堆栈术语中，插入操作称为
PUSH操作，移除操作称为
POP操作。
堆栈表示
下图描述了堆栈及其操作-
堆栈可以通过数组、结构、指针和链表来实现。堆栈可以是固定大小的，也可以是动态调整大小的。在这里，我们将使用数组来实现堆栈，这使它成为一个固定大小的堆栈实现。
基本操作
堆栈操作可能涉及初始化堆栈、使用它然后取消初始化它。除了这些基本的东西，堆栈用于以下两个主要操作-
push()-将元素压入（存储）堆栈。
pop()-从堆栈中移除（访问）一个元素。
当数据被压入堆栈时。
为了有效地使用堆栈，我们还需要检查堆栈的状态。出于同样的目的，堆栈中添加了以下功能-
peek()-获取堆栈的顶部数据元素，而不删除它。
isFull()-检查堆栈是否已满。
isEmpty()-检查堆栈是否为空。
在任何时候，我们都会维护一个指向堆栈上最后一个 PUSHed 数据的指针。因为这个指针总是代表栈顶，因此命名为
top。
top 指针提供堆栈的顶部值而不实际删除它。
首先我们应该了解支持堆栈函数的过程-
peek()
peek() 函数的算法-
begin procedure peek
return stack[top]
end procedure
C语言中peek()函数的实现-
示例
int peek() {
return stack[top];
}
isfull()
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()
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操作
将新数据元素放入堆栈的过程称为Push操作。Push操作涉及一系列步骤-
第 1 步-检查堆栈是否已满。
第 2 步-如果堆栈已满，则产生错误并退出。
第 3 步-如果堆栈未满，则递增 top 以指向下一个空白空间。
第 4 步-将数据元素添加到堆栈位置，顶部指向的位置。
第 5 步-返回成功。
如果使用链表来实现栈，那么在第3步，我们需要动态分配空间。
PUSH 操作算法
可以推导出一个简单的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操作。在 pop() 操作的数组实现中，数据元素实际上并没有被删除，而是将
top 递减到堆栈中的较低位置以指向下一个值。但在链表实现中，pop() 实际上是删除数据元素并释放内存空间。
Pop 操作可能涉及以下步骤-
第 1 步-检查堆栈是否为空。
第 2 步-如果堆栈为空，则产生错误并退出。
第 3 步-如果堆栈不为空，则访问 top 指向的数据元素。
第 4 步-将 top 的值减 1、
第 5 步-返回成功。
Pop操作算法
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");
}
}
