栈操作

栈操作说明

栈的常用操作主要包括，栈的初始化、判断是否为空、元素入栈、元素出栈、遍历以及给清空栈元素等。

栈定义

栈的结构如下：

typedef struct Node
{
	int data;    //数据结点
	struct Node * pNext;  //下一个元素
}NODE, * PNODE;
typedef struct Stack
{
	PNODE pTop;   //栈顶
	PNODE pBottom; //栈底
}STACK, * PSTACK;

我们定义了一个栈结点的结构 Node，其有两个成员，具体每个成员的意思见上面的注释。接着，我们定义了栈结构 Stack，其中包括了栈顶元素和栈底元素。如果现在，我们需要定义个栈结构，具体的代码如下：

STACK stack;

如果需要定义一个的指针，那么具体代码如下：

PSTACK pStack;

栈初始化

函数原型

int init(PSTACK pStack); //初始化栈

参数

参数	说明
pStack	需要初始化的栈。

返回值

初始化成功，返回 1，否则，返回 0。

图解

具体实现

//初始化栈 
int init(PSTACK pStack)
{
	//为栈顶元素分配内存 
	pStack->pTop = (PNODE)malloc(sizeof(PNODE));
	if (pStack->pTop == NULL)
	{
		return 0;
	}
	else
	{
		//将栈底执行栈顶，即栈顶和栈底是同一个元素，所以为空栈 
		pStack->pBottom = pStack->pTop;
		//将栈底元素的Next指针设置为NULL 
		pStack->pBottom->pNext = NULL;
	}
	return 1;
}

说明

我们只需要创建一个结点，并将栈顶指针和栈底指针指向该结点即可。

判断栈为空

函数原型

int isempty(PSTACK pStack);

参数

参数	说明
pStack	需要判断的栈。

返回值

如果栈为空，返回 1，否则返回 0。

具体实现

//判断栈是否Wie空 
int isempty(PSTACK pStack)
{
	if (pStack->pBottom == pStack->pTop)
	{
		return 1;
	}
	return 0;
}

说明

如果栈顶元素和栈底元素相等，那么就说明栈为空。

元素入栈

函数原型

int push(PSTACK pStack, int val);

参数

参数	说明
pStack	需要插入元素的栈。
val	需要入栈的元素。

返回值

如果入栈成功，则返回 1，否则，返回 0。

图解

具体实现

//向栈中添加一个元素val 
int push(PSTACK pStack, int val)
{
	//分配一个新的结点 
	PNODE pNewNode = (PNODE)malloc(sizeof(PNODE));
	if (pNewNode == NULL)
	{
		return 0;
	}
	//设置新结点的值
	pNewNode->data = val;
	//设置新结点的指针指向当前栈的栈顶 
	pNewNode->pNext = pStack->pTop;
	//将栈顶重新指向新的结点 
	pStack->pTop = pNewNode;
	return 1;
}

说明

首先，我们分配一个要入栈的结点，接着，将入栈的元素的结点的值设置为入栈的值，并且将新结点的指针指向当前栈的栈顶，最后，再次将栈顶指针移到新插入的结点即可。

元素出栈

函数原型

int pop(PSTACK pStack, int *pRetVal);

参数

参数	说明
pStack	需要删除元素的栈。
pRetVal	出栈的元素的值。

返回值

如果出栈成功，则返回 1，否则，返回 0。

图解

具体实现

//从栈中弹出（删除） 一个元素，并将弹出的元素通过pRetVal返回 
int pop(PSTACK pStack, int *pRetVal)
{
	if (isempty(pStack) == 1)
	{
		return 0;
	}
	//先获取到当前要删除的元素，也就是栈顶元素 
	PNODE pPopNode = pStack->pTop;
	//将栈顶元素的值返回出去 
	*pRetVal = pPopNode->data;
	//将栈顶指针下移一位 
	pStack->pTop = pPopNode->pNext;
	//释放结点，防止内存泄露 
	free(pPopNode);
	pPopNode = NULL;
	return 1;
}

说明

首先，我们使用 pPopNode 指针指向栈顶，接着，将栈顶元素的值赋值给返回值，并将栈顶指针下移一位，释放 pPopNode 即可。

遍历栈

函数原型

void traverse(PSTACK pStack);

参数

参数	说明
pStack	需要遍历的栈。

具体实现

//遍历栈 
void traverse(PSTACK pStack)
{
	if (isempty(pStack) == 1)
	{
		return;
	}
	//获取栈顶元素
	PNODE pNode = pStack->pTop;
	printf("栈的元素为：[ ");
	//如果栈不为空，则一直循环遍历 
	while(pNode != pStack->pBottom)
	{
		printf("%d ", pNode->data);
		//将指针下移 
		pNode = pNode->pNext;
	}
	printf("]\n");
}

说明

从栈顶获取元素，每次将指针往下移一位即可。

清空栈

函数原型

void clear(PSTACK pStack);

参数

参数	说明
pStack	需要清空的栈。

具体实现

//清空栈 
void clear(PSTACK pStack)
{
	//如果栈不为空，则一直循环遍历 
	while(isempty(pStack) == 0)
	{
		//获取栈顶元素 
		PNODE pNode = pStack->pTop;
		//将栈顶元素指针下移
		pStack->pTop = pNode->pNext;
		//释放结点 
		free(pNode);
		pNode = NULL;
	}
}

说明

如果栈不为空，则一直获取栈顶元素，将指针下移，释放结点即可。

案例

栈操作的综合案例如下：

# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>
typedef struct Node
{
	int data;
	struct Node * pNext;
}NODE, * PNODE;
typedef struct Stack
{
	PNODE pTop;
	PNODE pBottom;
}STACK, * PSTACK;
int init(PSTACK);
int isempty(PSTACK);
int push(PSTACK, int);
int pop(PSTACK, int *);
void traverse(PSTACK);
void clear(PSTACK pS);
int main()
{
	printf("嗨客网(www.haicoder.net)\n");
	PSTACK pStack = (PSTACK)malloc(sizeof(PSTACK));
	init(pStack);
	if (isempty(pStack) == 1)
	{
		printf("初始化后栈为空\n");
	}
	else
	{
		printf("初始化后栈不为空\n");
	}
	push(pStack, 1);
	push(pStack, 2);
	push(pStack, 100);
	push(pStack, 1024);
	if (isempty(pStack) == 1)
	{
		printf("Push元素后栈为空\n");
	}
	else
	{
		printf("Push元素后栈不为空\n");
	}
	traverse(pStack);
	int retVal = 0;
	pop(pStack, &retVal);
	printf("出栈元素为:%d\n", retVal);
	pop(pStack, &retVal);
	printf("出栈元素为:%d\n", retVal);
	traverse(pStack);
	clear(pStack);
	if (isempty(pStack))
	{
		printf("清空后栈为空\n");
	}
	else
	{
		printf("清空后栈不为空\n");
	}
	return 0;
}
//初始化栈 
int init(PSTACK pStack)
{
	//为栈顶元素分配内存 
	pStack->pTop = (PNODE)malloc(sizeof(PNODE));
	if (pStack->pTop == NULL)
	{
		return 0;
	}
	else
	{
		//将栈底执行栈顶，即栈顶和栈底是同一个元素，所以为空栈 
		pStack->pBottom = pStack->pTop;
		//将栈底元素的Next指针设置为NULL 
		pStack->pBottom->pNext = NULL;
	}
	return 1;
}
//判断栈是否Wie空 
int isempty(PSTACK pStack)
{
	if (pStack->pBottom == pStack->pTop)
	{
		return 1;
	}
	return 0;
} 
//向栈中添加一个元素val 
int push(PSTACK pStack, int val)
{
	//分配一个新的结点 
	PNODE pNewNode = (PNODE)malloc(sizeof(PNODE));
	if (pNewNode == NULL)
	{
		return 0;
	}
	//设置新结点的值
	pNewNode->data = val;
	//设置新结点的指针指向当前栈的栈顶 
	pNewNode->pNext = pStack->pTop;
	//将栈顶重新指向新的结点 
	pStack->pTop = pNewNode;
	return 1;
}
//从栈中弹出（删除） 一个元素，并将弹出的元素通过pRetVal返回 
int pop(PSTACK pStack, int *pRetVal)
{
	if (isempty(pStack) == 1)
	{
		return 0;
	}
	//先获取到当前要删除的元素，也就是栈顶元素 
	PNODE pPopNode = pStack->pTop;
	//将栈顶元素的值返回出去 
	*pRetVal = pPopNode->data;
	//将栈顶指针下移一位 
	pStack->pTop = pPopNode->pNext;
	//释放结点，防止内存泄露 
	free(pPopNode);
	pPopNode = NULL;
	return 1;
}
//遍历栈 
void traverse(PSTACK pStack)
{
	if (isempty(pStack) == 1)
	{
		return;
	}
	//获取栈顶元素
	PNODE pNode = pStack->pTop;
	printf("栈的元素为：[ ");
	//如果栈不为空，则一直循环遍历 
	while(pNode != pStack->pBottom)
	{
		printf("%d ", pNode->data);
		//将指针下移 
		pNode = pNode->pNext;
	}
	printf("]\n");
}
//清空栈 
void clear(PSTACK pStack)
{
	//如果栈不为空，则一直循环遍历 
	while(isempty(pStack) == 0)
	{
		//获取栈顶元素 
		PNODE pNode = pStack->pTop;
		//将栈顶元素指针下移
		pStack->pTop = pNode->pNext;
		//释放结点 
		free(pNode);
		pNode = NULL;
	}
}

程序运行后，输出如下：

我们看到，整个栈的操作运行结果如上所示。