数据结构之栈(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指向处数据.