C语言实现栈数据结构的完整教程与代码示例

1 年 ago

文, 翔

1 minute

引言

简介

栈是一种线性数据结构，它是由相同类型的项组成的集合。

在栈中，元素的插入和删除仅发生在一个端点。栈的行为被描述为”后进先出”(LIFO)。当一个元素被”推入”栈时，它成为将要被”弹出”的第一项。为了访问最早输入的项，必须先弹出所有在其之后添加的项。

在本文中，你将学习关于栈数据结构的概念，以及在C语言中使用数组实现栈的方法。

对栈执行的操作

下面是栈所提供的基本操作：

push（入栈）：向栈顶添加一个元素。
pop（出栈）：移除栈顶的元素。
isEmpty（判空）：检查栈是否为空。
isFull（判满）：检查栈是否已满。
top（取顶）：显示栈顶的元素。

栈的基本机制

最初，设置一个指针（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()操作。首先，它会检查top是否等于SIZE – 1。如果为真，则显示”溢出!!”。否则，程序会要求用户提供要添加到栈中的新元素。
如果用户选择2，程序将执行pop()操作。首先，它会检查top是否等于-1。如果为真，则显示”下溢!!”。否则，将移除栈顶元素并显示结果栈。
如果用户选择3，程序将执行show()操作。首先，它会检查top是否等于-1。如果为真，则显示”下溢!!”。否则，程序将显示栈中的所有元素。
如果用户选择4，程序将退出。

执行此代码将数字”10″推送到栈上。

输出：在栈上执行操作：
1.推入元素
2.弹出元素
3.显示
4.结束

输入选择：1

输入要插入到栈中的元素：10

然后在堆栈上展示元素：

输出：在栈上执行操作：
1.推入元素
2.弹出元素
3.显示
4.结束

输入选择：3

栈中存在的元素：
10

然后弹出（pop()）。

输出：在栈上执行操作：
1.推入元素
2.弹出元素
3.显示
4.结束

输入选择：2
弹出的元素：10

现在，堆栈是空的。再次尝试pop()：

输出：在栈上执行操作：
1.推入元素
2.弹出元素
3.显示
4.结束

输入选择：3
下溢!!

继续尝试这个程序，以了解堆栈的工作原理。

栈操作的时间复杂度

在栈中一次只能访问一个元素。

在对栈执行push()和pop()操作时，它需要O(1)的时间。

结论

在这篇文章中，你学到了栈数据结构的概念以及在C语言中使用数组实现的方法。

堆栈被用来解决一些普遍的问题，比如：

继续学习吧，学习如何在C语言中创建队列和如何初始化数组。

#C语言 #数据结构 #栈数据结构 #算法 #编程教程