数据结构之栈结构_栈的结点个数

数据结构之栈结构

一：认识栈结构

栈结构是一种FILO(First In Last Out)的批量数据存储结构。其特点是先进后出，后来者居上
栈的基本属性: 栈内存、栈顶标记、栈的当前元素个数（万金油属性：size）
栈的基本操作：

• 入栈：把数据存储到栈内存中去
• 出栈：把数据从栈内存中删除掉
• 获取栈顶元素：栈顶标记的元素

万金油的的操作：

• 判断是否为空
• 当前栈中数据个数

根据实现的不同将栈结构分为两种：
1.链式栈

2.数组

二：链式栈

利用有表头链表的头插法来完成栈的功能：

1. 设计数据结构：

//链表结构
struct Node
{
	int data;
	struct Node* next;
};
//栈结构
struct stack
{
	struct Node* stackTop;//栈顶标记
	int sizeStack;//栈中当前元素的个数 
};
1
2
3
4
5
6
7
8
9
10
11
12

2. 数据初始化（创建结点，创建栈）

//创建结点
struct Node* createNode(int data)
{
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}
//创建栈-->描述结点的最初状态
struct stack* createStack()
{
	struct stack* newStack = (struct stack*)malloc(sizeof(struct stack));
	newStack->sizeStack = 0;
	newStack->stackTop = NULL;
	return newStack;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3. 万金油函数

//万金油函数
int size(struct stack* pStack)//栈中元素个数
{
	return pStack->sizeStack;
}
int empty(struct stack* pStack)//判断栈是否为空
{
	return pStack->sizeStack == 0;
}
1
2
3
4
5
6
7
8
9

4. 栈的基本方法的实现：入栈、出栈、获取去栈顶元素。

//入栈操作--->链表的头插法。（无头链表，栈顶指针永远都指向第一个结点）
void push(struct stack* pStack, int data)
{
	struct Node* newNode = createNode(data);
	newNode->next = pStack->stackTop;
	pStack->stackTop = newNode;
	pStack->sizeStack++;
}
//出栈：链表的删除（无头链表的头删法）
void pop(struct stack* pStack)
{
	if (pStack->sizeStack == 0)
	{
		printf("栈为空,无法出栈！\n");
		return;
	}
	struct Node* nextNode = pStack->stackTop->next;
	free(pStack->stackTop);
	pStack->stackTop = nextNode;
	pStack->sizeStack--;
}
//获取栈顶元素
int top(struct stack* pStack)
{
	if (pStack->sizeStack == 0)
	{
		printf("栈为NULL,无法获取栈顶元素！\n");
		return -1;//标记操作(测试数据中不含有-1)
	}
	return pStack->stackTop->data;
}
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

完整测试代码：

//链式栈：链表的头插法
#include<stdio.h>
#include<stdlib.h>
//链表结构
struct Node
{
	int data;
	struct Node* next;
};
//栈结构
struct stack
{
	struct Node* stackTop;//栈顶标记
	int sizeStack;//栈中当前元素的个数 
};
//创建结点
struct Node* createNode(int data)
{
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}
//创建栈-->描述结点的最初状态
struct stack* createStack()
{
	struct stack* newStack = (struct stack*)malloc(sizeof(struct stack));
	newStack->sizeStack = 0;
	newStack->stackTop = NULL;
	return newStack;
}
//万金油函数
int size(struct stack* pStack)
{
	return pStack->sizeStack;
}
int empty(struct stack* pStack)
{
	return pStack->sizeStack == 0;
}
//入栈操作--->链表的头插法。（无头链表，栈顶指针永远都指向第一个结点）
void push(struct stack* pStack, int data)
{
	struct Node* newNode = createNode(data);
	newNode->next = pStack->stackTop;
	pStack->stackTop = newNode;
	pStack->sizeStack++;
}
//出栈：链表的删除（无头链表的头删法）
void pop(struct stack* pStack)
{
	if (pStack->sizeStack == 0)
	{
		printf("栈为空,无法出栈！\n");
		return;
	}
	struct Node* nextNode = pStack->stackTop->next;
	free(pStack->stackTop);
	pStack->stackTop = nextNode;
	pStack->sizeStack--;
}
//获取栈顶元素
int top(struct stack* pStack)
{
	if (pStack->sizeStack == 0)
	{
		printf("栈为NULL,无法获取栈顶元素！\n");
		return -1;//标记操作(测试数据中不含有-1)
	}
	return pStack->stackTop->data;
}
int main()
{
	struct stack* myStack = createStack();
	push(myStack, 1);
	push(myStack, 2);
	push(myStack, 3);
	while (!empty(myStack))
	{
		printf("%d ", top(myStack));
		pop(myStack); 
	}
	printf("\n");
	return 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
80
81
82
83
84
85

三：进制转换问题

栈结构的先进后出这一特点使得它适用于回退的过程，在短除法进行进制转换（最后有一个逆序打印的过程）时我们就可以运用栈这一结构进行实现。

//接上面链式栈
//接上面链式栈
//接上面链式栈
//用栈结构实现进制转换：
	int num = 20000105;//将十进制的num转换为2进制（除k取余法）
	struct stack* D2B = createStack();//将十进制的20000105转换为二进制数
	printf("%d的二进制数为：", num);
	while (num)
	{
		push(D2B, num % 2);
		num /= 2;
	}
	while (!empty(D2B))
	{
		printf("%d", top(D2B));
		pop(D2B);
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

四：数组栈

通常情况下，数组本身就可以充当栈内存，可以直接用数组来实现栈的功能
并其相对于链式栈，数组栈相对简便。因而用数组栈更多

//数组栈的使用示例：
//进制转换问题：
#include<stdio.h>
#include<stdlib.h>
int main()
{
	int stack[100];//栈内存,有范围！
	int stackTop = -1;//栈顶标记,用下标去充当位置 初始为-1是为了让栈顶标记与数组下标同步
	int num = 20000105;//将十进制的num转换为二进制数
	printf("%d的二进制数为：",num);
	while (num)
	{
		stack[++stackTop] = num % 2;//数组栈的入栈操作
		num /= 2;
	}
	while (stackTop != -1)//与栈顶标记最开始时进行比较
	{
		printf("%d", stack[stackTop--]);//数组栈的出栈(伪删除)过程
	}

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

需要注意的是数组栈无法进行出栈操作，上面的出栈操作实际上是一种伪删除的过程