【数据结构】顺序栈

1.栈

1.1栈的概念

栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

栈顶（Top）：线性表允许进行插入和删除的一端。
栈底（base）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素。

1.2 栈的基本操作

void StackInit(STp) //初始化栈
voidStackPush(STp,intx) //进栈
voidStackPop(STp) //出栈
voidStackDestory(STp) //销毁栈
intStackTop(STp) //获取栈顶人数
voidStackShow(STp) //打印所有栈内元素
intStackSize(STp) //获取栈的现有元素个数
boolStackEmpty(ST*p) //判断栈是否为空

1.3 顺序栈的实现

采用顺序存储的栈称为顺序栈，它是利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶的位置。
栈的顺序存储类型可以用以下表示：

typedef struct stack
{
	int* arr;
	int top;
	int capcity;
}ST;
1
2
3
4
5
6

栈顶指针：ST.top，初始时设置ST.top = 0
进栈操作：栈不满时，用下表arr[top]进行赋值，如果栈满了就进行扩容。
出栈操作：栈非空时，将栈顶指针减1
栈空条件：ST.top == 0
栈满条件：ST.top == capcity - 1
栈长：ST.top + 1
栈的基本操作

1.4 函数实现

初始化

void StackInit(ST* p)
{
	p->arr = (int*)malloc(sizeof(int) * 4);
	p->capcity = 4;
	p->top = 0;
}
1
2
3
4
5
6

入栈

void StackPush(ST* p, int x)
{
	if (p->top == p->capcity)
	{
		int* temp = (int*)realloc(p->arr, sizeof(int) * (p->capcity * 2));
		if (temp != NULL)
		{
			p->arr = temp;
			p->capcity *= 2;
		}
		p->arr[p->top] = x;
		p->top++;
	}
	else
	{
		p->arr[p->top] = x;
		p->top++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

出栈

void StackPop(ST* p)
{
	assert(p);
	assert(p->top > 0);
	if (StackEmpty(p) == true)
	{
		printf("ջΪ");
		return;
	}
	else
	{
		p->top--;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

获取栈顶元素

int StackTop(ST* p)
{
	assert(p);
	assert(p->top > 0);
	return p->arr[p->top-1];
}
1
2
3
4
5
6

判断栈是否为空

bool StackEmpty(ST* p)
{
	assert(p);
	return p->top == 0;
}
1
2
3
4
5

打印栈里现有元素

void StackShow(ST p)
{
	if (StackEmpty(&p) == 1)
	{
		printf("ջΪ");
		return;
	}
	else
	{
		for (int i = p.top-1; i >=0; i--)
		{
			printf("%d ", p.arr[i]);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

获取栈的现有元素个数

int StackSize(ST* p)
{
	assert(p);
	return p->top;
}
1
2
3
4
5

销毁栈

void StackDestory(ST* p)
{
	if (StackEmpty(p) == true )
	{
		printf("ջΪ");
		return;
	}
	else
	{
		free(p->arr);
		p->arr = NULL;
		p->top = 0;
		p->capcity = 0;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

完整代码

#include
#include
#include
#include
typedef struct stack
{
	int* arr;
	int top;
	int capcity;
}ST;
bool StackEmpty(ST* p);
void StackInit(ST* p)
{
	p->arr = (int*)malloc(sizeof(int) * 4);
	p->capcity = 4;
	p->top = 0;
}
void StackPush(ST* p, int x)
{
	if (p->top == p->capcity)
	{
		int* temp = (int*)realloc(p->arr, sizeof(int) * (p->capcity * 2));
		if (temp != NULL)
		{
			p->arr = temp;
			p->capcity *= 2;
		}
		p->arr[p->top] = x;
		p->top++;
	}
	else
	{
		p->arr[p->top] = x;
		p->top++;
	}
}
void StackPop(ST* p)
{
	assert(p);
	assert(p->top > 0);
	if (StackEmpty(p) == true)
	{
		printf("ջΪ");
		return;
	}
	else
	{
		p->top--;
	}
}
void StackDestory(ST* p)
{
	if (StackEmpty(p) == true )
	{
		printf("ջΪ");
		return;
	}
	else
	{
		free(p->arr);
		p->arr = NULL;
		p->top = 0;
		p->capcity = 0;
	}
}
int StackTop(ST* p)
{
	assert(p);
	assert(p->top > 0);
	return p->arr[p->top-1];
}
bool StackEmpty(ST* p)
{
	assert(p);
	return p->top == 0;
}
void StackShow(ST p)
{
	if (StackEmpty(&p) == 1)
	{
		printf("ջΪ");
		return;
	}
	else
	{
		for (int i = p.top-1; i >=0; i--)
		{
			printf("%d ", p.arr[i]);
		}
	}
}
int StackSize(ST* p)
{
	assert(p);
	return p->top;
}
int main()
{
	int max = 0, length = 0;
	ST stack;
	StackInit(&stack);
	StackPush(&stack, -1);
	char* s = ")()())";
	for (int i = 0; i < strlen(s); i++)
	{
		if (*(s + i) == '(')
		{
			StackPush(&stack, i);
		}
		else
		{
			if (StackSize(&stack) == 1)
			{
				StackPop(&stack);
				StackPush(&stack, i);
				length = 0;
			}
			if (StackSize(&stack) > 1)
			{
				StackPop(&stack);
				length = i - StackTop(&stack);
				max = max < length ? length : max;
			}
		}
	}
	printf("%d", max);
}
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127