C 语言实现栈

定义

1. 栈 stack 是限定仅在尾部进行插入和删除操作的线性表
2. 我们把允许插入和删除的一端称为栈顶 top，另一端称为栈底 bottom，不包含任何数据的元素为空栈
3. 栈又称为后进先出 Last in First Out 的线性表，简称 LIFO 结构
4. 当 top 为空时，表示空栈

注：

1. 首先栈是一种特殊的线性表，其具有线性表的关系，前驱和后继，而且特性属性，从栈顶进，从栈顶出
2. 栈底是固定的，最先进栈的在栈底 bottom
3. 栈的插入操作称为 入栈 push
4. 栈的删除操作称为 出栈 pop

C 语言实现栈

#include <stdio.h>
#include <stdlib.h>

// 节点数据类型
typedef struct node
{
	int data;	// 可以是其他类型，这里用 int 型做演示
	struct node *next;	
}node_t;

// 链栈数据类型
typedef struct linkStack
{
	node_t *top;
	int length;
}linkStack_t;

// 函数声明
node_t *createNode(int data);
linkStack_t *createStack();
int pushStack(linkStack_t *stack, node_t *node);
node_t *popStack(linkStack_t *stack);
int emptyStack(linkStack_t *stack);
node_t *getTop(linkStack_t *stack);
int getLength(linkStack_t *stack);
void printStack(linkStack_t *stack);
void destoryStack(linkStack_t *stack);

// 需要一个 top 指针标记栈顶的位置,如果 top == NULL 表示为空栈

// 创建节点
node_t *createNode(int data)
{
	node_t *node = (node_t *)malloc(sizeof(node_t));
	if (NULL == node) {
		return NULL;
	}
	node->data = data;
	node->next = NULL;
	return node;
}

// 创建栈
linkStack_t *createStack()
{
	linkStack_t *linkStack = (linkStack_t *)malloc(sizeof(linkStack_t));
	if (NULL == linkStack) {
		return NULL;
	}
	linkStack->top = NULL;
	linkStack->length = 0;
	return linkStack;
}

// 入栈
int pushStack(linkStack_t *stack, node_t *node)
{
	if (NULL == stack || NULL == node) {
		return 0;
	}
	// 栈的 top 节点永远是顶部节点，入栈的话，此节点就为入栈节点的 next
	node->next = stack->top;
	stack->top = node;	// 栈的 top 将执行当前节点，而且这两步不能颠倒
	stack->length++;
	return 1;
}

// 出栈
node_t *popStack(linkStack_t *stack)
{
	if (emptyStack(stack)) {
		return NULL;
	}
	node_t *node = stack->top;
	stack->top = stack->top->next;
	stack->length--;
	return node;
}

// 判断是否空栈[1 为空 0 非空]
int emptyStack(linkStack_t *stack)
{
	if (NULL == stack) {
		return 1;
	}
	// top 为 NULL 表示为空栈
	if (NULL == stack->top || 0 == stack->length) {
		return 1;
	}
	return 0;
}

//获取栈顶元素
node_t *getTop(linkStack_t *stack)
{
	if (emptyStack(stack)) {
		return NULL;
	}
	// 只返回栈顶元素，不出栈
	return stack->top;
}

// 获取栈长度
int getLength(linkStack_t *stack)
{
	if (NULL == stack) {
		return 0;
	}
	return stack->length;
}

// 打印栈元素
void printStack(linkStack_t *stack)
{
	if (emptyStack(stack)) {
		perror("empty stack not print");
		return;
	}
	// 循环打印栈元素
	node_t *cursor = stack->top;
	while (NULL != cursor) {
		printf("%d\n", cursor->data);
		cursor = cursor->next;
	}
}

// 销毁栈
void destoryStack(linkStack_t *stack)
{
	if (emptyStack(stack)) {
		return;
	}
	node_t *delete = NULL;
	// 从 top 开始循环
	while (NULL != stack->top) {
		delete = stack->top;	// 临时记录 top 指针，top 下移，然后删除 delete，循环一个一个删除节点
		stack->top = delete->next;
		free(delete);
		delete = NULL;
	}
	if (NULL != delete) {
		free(delete);
		delete = NULL;
	}
	free(stack);	// 最后删除链栈，然后置为 NULL，防止野指针出现
	stack = NULL;
}

int main(void)
{
	// 下面是栈测试
	linkStack_t *stack = createStack();
	if (NULL != stack) {
		node_t *node = createNode(1);
		node_t *node1 = createNode(2);
		if (NULL != node && pushStack(stack, node) && pushStack(stack, node1)) {
			printStack(stack);
		}
		node_t *pop = popStack(stack);
		if (NULL != pop) {
			printf("pop:%d\n", pop->data);
		}
		printStack(stack);
		destoryStack(stack);
	}
	return 0;
}

©版权声明：原创作品，允许转载，转载时请务必以超链接形式标明文章 原始出处 & 作者信息。

End