介绍
栈是一种线性数据结构，它存储着相同类型的元素。在栈中，元素的插入和移除只能在一个端点进行。栈的行为遵循“后进先出”（LIFO）原则。当一个元素被“压入”（PUSHED）到栈中时，它会成为第一个被“弹出”（pop）出栈的元素。要访问最早插入的元素，必须先弹出所有之前插入的元素。.
本文将介绍栈数据结构的概念及其在 C 语言中使用数组的实现。.
对堆栈执行的操作
以下是栈提供的基本操作。.
- push：将元素添加到堆栈顶部。.
- pop：从堆栈中移除最顶层的元素。.
- isEmpty：检查栈是否为空。.
- isFull：检查堆栈是否已满。.
- top：显示堆栈的最顶层元素。.
堆栈的底层机制
初始时，设置一个指向栈顶元素的指针（向上）。栈的初始值为-1。.
然后，通过比较栈顶元素和 -1 来检查栈是否为空。.
当元素添加到堆栈中时，堆栈顶部的位置会更新。.
一旦元素被弹出或删除，最顶层的元素就会被移除，并且顶部位置会更新。.
C语言栈的实现
栈可以用结构体、指针、数组或链表来表示。.
本示例使用 C 语言中的数组实现栈：
#include <stdio.h>
#include <stdlib.h>
#define SIZE 4
int top = -1, inp_array[SIZE];
void push();
void pop();
void show();
int main()
{
int choice;
while (1)
{
printf("\nPerform operations on the stack:");
printf("\n1.Push the element\n2.Pop the element\n3.Show\n4.End");
printf("\n\nEnter the choice: ");
scanf("%d", &choice);
switch (choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
show();
break;
case 4:
exit(0);
default:
printf("\nInvalid choice!!");
}
}
}
void push()
{
int x;
if (top == SIZE - 1)
{
printf("\nOverflow!!");
}
else
{
printf("\nEnter the element to be added onto the stack: ");
scanf("%d", &x);
top = top + 1;
inp_array[top] = x;
}
}
void pop()
{
if (top == -1)
{
printf("\nUnderflow!!");
}
else
{
printf("\nPopped element: %d", inp_array[top]);
top = top - 1;
}
}
void show()
{
if (top == -1)
{
printf("\nUnderflow!!");
}
else
{
printf("\nElements present in the stack: \n");
for (int i = top; i >= 0; --i)
printf("%d\n", inp_array[i]);
}
}该程序为用户提供四个选项：
- 推动元素
- 弹出元素
- 展示
- 结尾
等待用户输入数字。.
- 如果用户选择 1，程序会执行 push() 操作。它首先检查栈顶元素是否等于 SIZE - 1。如果是，则显示“溢出！！”。否则，提示用户输入要添加到栈中的新元素。.
- 如果用户选择 2，程序会执行 pop() 操作。它首先检查栈顶元素是否等于 -1。如果是，则显示“下溢！！”。否则，移除栈顶元素，并将结果栈输出。.
- 如果用户选择 3，程序会执行 show() 操作。它首先检查栈顶指针是否等于 -1。如果是，则显示“下溢！！”。否则，程序输出堆栈结果。.
- 如果用户选择 4，程序将退出。.
运行以下代码，将数字“10”压入堆栈：
Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 1
Enter the element to be inserted onto the stack: 10然后显示 Stack() 中的元素：
Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 3
Elements present in the stack:
10然后 pop():
Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 2
现在栈已为空。再次尝试调用 Pop() 函数：
Output
Perform operations on the stack:
1.Push the element
2.Pop the element
3.Show
4.End
Enter the choice: 3
Underflow!! Your code... */继续尝试使用此程序，以了解堆栈的工作原理。.
栈操作的时间复杂度
栈中一次只能访问一个元素。.
对栈执行 push() 和 pop() 操作时，需要 O(1) 时间。.
结果
在本文中，您学习了栈数据结构的概念及其在 C 语言中使用数组的实现。.
