数据结构中栈的表示

栈是一种抽象数据类型（ADT），用于线性存储数据。我们只能通过栈顶来添加或移除数据。

抽象数据类型

对象的行为可以通过一组值和一组操作来描述，这种行为被称为抽象数据类型（ADT）。ADT的定义只规定了必须执行的操作，而没有规定如何执行。它不清楚将使用哪些算法来执行操作以及数据将如何在内存中构造。因为它提供了独立于实现的视图，所以它被称为“抽象”。

抽象是一种只呈现基本要素而隐藏细节的技术。

数据类型的用户不需要知道该数据类型是如何实现的。例如，我们一直在使用int、float和char等原始数据类型，只知道这些数据类型可以操作和执行，而不知道它们是如何实现的。

因此，用户只需要知道数据类型能做什么，而不需要知道它将如何使用。将ADT视为一个“黑盒子”，它隐藏了数据类型的内部组织和设计。现在我们将定义三种ADT：列表、栈和队列。

栈ADT

• 栈ADT的实现不是在每个节点中存储数据，而是存储对数据的引用。
• 地址被提供给栈ADT，软件为数据分配内存。
• ADT包含头节点和数据节点。调用函数唯一能看到的是栈指针。
• 栈头结构还包括对栈顶的引用和当前栈中元素数量的计数。
• push()函数将一个元素推入栈顶。
• pop() - 如果栈不为空，则移除并返回栈顶元素。
• 如果栈不为空，peek()方法返回栈顶元素而不删除它。

LIFO（后进先出）

我们将使用后进先出（LIFO）方法将数据项插入数据结构中。我们将在这里突出显示最新的数据项。这意味着最后一个组件将首先出现。

真实生活中的例子

在此示例中应考虑以下元素

• 有一个装有球的容器。
• 不同种类的球被放入桶中。
• 最后放入桶中的球将是第一个被取出的球。
• 它上面的球将首先被移除，然后是最后进入桶中的球（较新的球）。
• 这样，第一个进入桶中的球将最后离开。
• 结果是，最后进入桶中的球（蓝色）首先被取出，然后是第一个球（红色）。

书籍示例

书本堆叠的数量

• 汉诺塔是另一个极好的真实生活示例。这个引人入胜的游戏的全部基础是后进先出规则。
• 栈是一种使用LIFO概念的数据结构。
• 我们将在栈数据结构上进行第一次push操作和第二次pop操作。
• 最近放入栈中的数据元素将首先被移除，反之，首先推入栈中的数据元素将最后被移除，直到它之前存在的所有项都被移除。
• 栈只有一个末端，或者你可以说它在一侧是开放的。
• LIFO概念是大多数程序的基础。
• 栈在各种表达式的求值中至关重要，包括后缀到中缀、中缀到前缀和前缀到后缀。
• 递归的实现是它的主要用途。递归用于更有效地解决问题。
• 此外，在运行程序时，激活记录使用LIFO技术填充堆。
• 栈数据结构用于构建下推自动机，以确定字符串是否被机器接受。
• 为了轻松计算给定字符串中存在的字母数量，并确定它是否属于所提及的上下文无关文法，它主要基于LIFO原则，根据需要我们将输入字符串一个接一个地推入栈中，并以同样的方式弹出相同数量的字符串。

基于栈的数据结构基于LIFO概念。push和pop是我们对其使用的两个主要操作。数据项通过push操作推入栈中，并通过pop操作从栈中移除。

栈数据结构中的top指针指向栈顶的值。下溢情况是指栈最初为空时链接到空指针的状态。我们已经提供了栈的容量；假设为n，在栈中。数据值必须一个接一个地添加到栈中，直到栈顶达到其最大大小。溢出是指超出容量的情况。

LIFO的应用场景

数据结构：某些数据结构，如栈和各种栈变体，使用LIFO方法处理数据。

获取最新信息：当数据从数组或数据缓冲区中取出时，计算机可能会使用LIFO。当需要检索最新输入的数据时，会使用LIFO技术。

让我们看一个C语言程序，以更好地理解LIFO的结构化工作原理

输出

10 pushed into stack
20 pushed into stack
30 pushed into stack
30 Popped from stack
Top element is : 20
Elements present in stack : 20 10
...........................................................
Process executed in 3.22 seconds
Press any key to continue.

说明

在上面LIFO表示的C程序中，我们可以看到首先10被推入，然后20被推入栈，接着30被推入栈，然后当执行pop函数时，最后进入栈的元素首先被弹出。