（数据结构）栈讲解和栈实现_栈中的数据元素

栈的概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

举几个例子更好的理解栈：
1.羽毛球桶，把羽毛球一个一个放进去，先取出来的一定是最后放进去的。
2.吃进去，吐出来（这个例子可能不太恰当，但是很直观）

栈的结构

栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小

栈的结构包括定长的静态栈和支持动态增长的栈。一般使用后者较多。以下是动态增长栈的实现：
Stack.h

#pragma once

typedef int SDataType;

typedef struct Stack
{
	SDataType* array;
	int capacity;
	int size;//栈中元素的个数 栈顶
}Stack;

void StackInit(Stack* ps);
//入栈：尾插
void StackPush(Stack* ps, SDataType data);
//出栈：尾删
void StackPop(Stack* ps);
//获取栈顶元素
SDataType StackTop(Stack* ps);
//获取栈中有效元素个数
int StackSize(Stack* ps);
//检测是否为空
int StackEmpty(Stack* ps);
//销毁
void StackDestroy(Stack* ps);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Stack.c

#include "Stack.h"
#include <malloc.h>
#include <assert.h>
#include <stdio.h>
#include <string.h>

void StackInit(Stack* ps)
{
	assert(ps);
	ps->array = (SDataType*)malloc(sizeof(SDataType)* 10);
	if (NULL == ps->array)
	{
		assert(0);
		return;
	}
	ps->capacity = 10;
	ps->size = 0;
}
void CheckCapacity(Stack* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		//1.开辟新空间
		SDataType* temp = (SDataType*)malloc(sizeof(SDataType)*ps->size * 2);
		if (temp == NULL)
		{
			assert(0);
			return;
		}
		//2.拷贝元素
		memcpy(temp, ps->array, sizeof(SDataType)*ps->size);
		//3.释放旧空间
		free(ps->array);
		ps->array = temp;
		ps->capacity *= 2;
	}
}
//入栈：尾插
void StackPush(Stack* ps, SDataType data)
{
	assert(ps);
	CheckCapacity(ps);
	ps->array[ps->size++] = data;
}
//出栈：尾删
void StackPop(Stack* ps)
{
	if (StackEmpty(ps))
		return;
	ps->size--;
}
//获取栈顶元素
SDataType StackTop(Stack* ps)
{
	assert(!StackEmpty(ps));
	return ps->array[ps->size - 1];
}
//获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->size;
}
//检测是否为空
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->size == 0;
}
//销毁
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->array);
	ps->array = NULL;
	ps->capacity = 0;
	ps->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79