本文主要是介绍数据结构之栈(LIFO)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、栈的认识：
首先，栈可以被理解为一种容器，一种类似于弹夹的一边开口一边闭口的容器，这是对栈的实际理解。
其次，栈虽然也是一种数据结构，但是它并没有固定的表现形式。总而言之，栈就是一种抽象的数据结构。或言之，他就是一种数学逻辑。
最后，其实栈是寄托于数组，链表等实体进行实现的。
下面我们将讨论栈的实现。
二、栈的实现：（有两种实现方法：数组、链表）
1）基于数组的顺序栈：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>#define MAX 101
int a[MAX] = { 0 };
int top = -1;
//插入：
void Push() {int n = 0;printf("请输入插入的数据：");scanf("%d", &n);a[++top] = n;
}
//弹出；
void Pop() {top--;printf("删除成功！");
}
//返回栈顶元素；
int Top() {if (top != -1) {return a[top];}else {printf("栈中没有元素了！");return top;}
}void print() {for (int i = 0; i <= top; i++) {printf("%d ", a[i]);}puts("");
}
int main() {//基于数组实现栈：
//准备一个数组，作为栈这个容器；Push();print();Push();print();Push();print();Pop();print();Top();print();
}
2）基于链表的线性栈：
基于链表实现栈；
基本思想：一个单链表就是一个栈，栈顶就是链表头，因此不论是push，pop都是对头操作；
其实实现的就是链表的一个头插法，头删法；
typedef struct Node {int data;struct Node* next;
}Node;
Node* top = NULL;//创建链表头指针，也就是栈顶的指针；
Node* createNode(int n) {Node* p = (Node*)malloc(sizeof(Node));p->next = NULL;p->data = n;return p;
}
void Push(int n) {Node* p = createNode(n);p->next = top;top = p;
}
void Pop() {if (top == NULL) {return;}Node* temp = top;top = top->next;free(temp);
}
int Top() {if (top == NULL) {return;}return top->data;
}
void print() {printf("栈：");Node* temp = top;while (temp != NULL) {printf("%d", temp->data);temp = temp->next;}printf("\n");
}int main(){Push(1);print();Push(2);print();Push(3);print();Push(4);print();Pop();print();printf("%d", Top());return 0;
}对于栈的主要实现细节：
在解释前，先说明栈这种数据结构有个特点，对于元素的添加、删除、返回栈顶元素，他们的实现都需要满足时间复杂度为O(1)，其实就是他们的实现与元素的数量无关。
1.基于数组，对于一个数组，怎么去对应栈的各部分呢？
数组的添加在数组尾可以达到O(1)，删除可以在数组头和数组尾进行达到O(1)。但是只有一边开口，所以只有数组尾满足条件，数组尾作为栈头。
1) push()函数（不考虑栈空间不足）：直接对top+1（数组尾），这样就加入了一个元素。
2) pop()函数：如果栈中有元素（top != -1），直接top-1;
3) top()函数:直接返回数组尾,top就是栈顶元素的索引.
2.基于链表，对于一个链表呢？
链表的尾插需要O(n)的时间复杂度，所以我们直接选择头插法和头删法作为Push和Pop，同时也满足在O(1)下返回栈头元素。
1) push()函数（不考虑栈空间不足）：直接头插法,无任何注意事项.
2) pop()函数：直接让top向后移动一位,这里注意:最后free掉的是原本top处的内存,而不是top指向的结点,所以需要有一个临时变量 = top,free(临时变量).
3) top()函数:如果有结点,直接返回head指向处数据.
这篇关于数据结构之栈(LIFO)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
