KJHの博客

记录&回忆

0%

数据结构的线性堆栈

发表于 更新于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

栈也是一种很重要的数据结构，具备“先进后出”的特点。程序中的函数调用以及递归都涉及栈这一数据结构，熟悉栈有利于我们更好地理解函数的调用过程(主要是形参，局部变量以及函数的返回值)和递归算法的实现过程

1、栈的数据节点

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
typedef struct _Stack
{
	int *pData;   //数据域指针
	int size;     //栈容量
	int top;      //栈顶
}Stack;
2、创建指定容量的栈
Stack* createStack(int MaxElements)
{
	Stack *pStack = NULL;
	if (0 == MaxElements)
		return NULL;

	pStack = (Stack *)malloc(sizeof(Stack));   //开辟栈节点空间
	assert(NULL != pStack);
	memset(pStack, 0, sizeof(Stack));
	 
	pStack->pData = (int *)malloc(sizeof(int)* MaxElements);   //开辟数据空间
	if (NULL == pStack->pData)
	{
		free(pStack);
		pStack = NULL;
	}
	 
	memset(pStack->pData, 0, sizeof(int)* MaxElements);
	pStack->size = MaxElements;
	pStack->top = -1;    //这里按照数组形式，初始值为-1
	                         //也设置为栈顶“指针”时刻指向栈顶元素
	return pStack;

}

3、判断栈满，栈空

1
2
3
4
5
6
7
8
9
bool isFull(Stack *pStack)
{
	return (pStack->size == (pStack->top + 1));
}

bool isEmpty(Stack *pStack)
{
	return (-1 == pStack->top);
}

4、压栈操作
异常情况;

1) 栈不存在

2) 栈已满

1
2
3
4
5
6
7
8
9
10
11
12
bool push(Stack *pStack, int value)
{
	if (NULL == pStack)
		return false;

	if (isFull(pStack))
		return false;
	 
	pStack->pData[++pStack->top] = value;
	return true;

}

5、出栈操作
异常情况：

1) 栈不存在

2) 栈为空

1
2
3
4
5
6
7
8
9
10
11
12
bool pop(Stack *pStack, int *value)
{
	if (NULL == pStack)
		return false;

	if (isEmpty(pStack))
		return false;
	 
	*value = pStack->pData[pStack->top--];
	return true;

}

6、释放栈空间
类似于C++中的基类，继承类析构，先释放数据空间，再释放栈节点空间。

这里也可传递一级指针，同样可以释放栈空间内存，但是不能把栈指针设置为NULL，打印数据时也就不能进行判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool freeStack(Stack **ppStack)
{
	if (NULL == *ppStack)
		return false;

	if (NULL == (*ppStack)->pData)
	{
		free(*ppStack);
		*ppStack = NULL;
		return true;
	}
	 
	free((*ppStack)->pData);
	free(*ppStack);
	*ppStack = NULL;   //设置，便于后面判断
	                   //所以设置二级指针传递
	return true;

}

7、打印栈数据

1
2
3
4
5
6
7
8
9
10
11
void printStack(Stack *pStack)
{
	if (pStack)
	{
		int num = pStack->top;

		while (-1 != num)
			printf("%d\n", pStack->pData[num--]);
	}

}

这里创建的栈数据结构实质就是开辟一个指定容量的数组空间，然后设置栈顶位置时刻指向栈顶元素