栈的链式存储结构及实现

缺乏、安全感 2022-06-03 10:13 185阅读 0赞

今天学习栈的链式存储结构。

链式存储结构最大的好处就是没有空间的限制，通过指针指向将结点像一个链子一样把结点链接，那么栈的同样可以用于链式存储结构。

**栈的链式存储结构，简称为链栈**。想想看，栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？由于单链表有头指针，而栈顶指针也是必须的，那么干嘛不让他们合二为一呢，所以比较好的办法是把栈顶放到单链表的头部。另外栈顶在头部了，那么单链表的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。

同样对于链栈来说，基本不存在栈满的情况，除非内存已经没有可用的空间了。

下面是链栈的指向图：

![Center][]

同样链栈中最重要的算法是压栈和弹栈。

**压栈操作：**

操作很简单，新建结点，给结点数据域赋值，指针域指向原来栈顶元素。

然后将栈顶指针指向新结点，元素个数+1,就ok。如下图：

![Center 1][]

弹栈操作：

和压栈相反，将栈顶元素的数据域取通过指针返回这个数据，将要弹出的元素的指针域赋值给栈顶指针，然后释放这个元素，这样栈顶指针就指向新的栈顶了，然后元素个-1。如图：

![Center 2][]

下面我们来看一下相关代码的实现。

#define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <stdlib.h>
    #define ERROR 0
    #define OK 1
    #define TRUE 1
    #define FALSE 0
    typedef int Status;
    typedef int EleType;
    typedef struct StackNode {
    	EleType data;//结点数据域
    	struct StackNode* next;//结点指针域
    }StackNode,* LinkStackPoi;
    //链栈的数据结构
    typedef struct LinkStack {
    	LinkStackPoi top;//栈顶结点
    	int count;//元素个数
    }LinkStack;
    //初始化
    Status InitLinkStack(LinkStack* stack)
    {
    	if (!stack)
    	{
    		return	ERROR;
    	}
    	stack->top = NULL;
    	stack->count = 0;
    	return OK;
    }
    //清空数据，释放结点内存，实际上就是pop所有数据
    Status ClearLinkStack(LinkStack* stack)
    {
    	if (!stack||!stack->count)
    	{
    		return	ERROR;
    	}
    	while (stack->count)
    	{
    		StackNode* node = stack->top;
    		stack->top = node->next;
    		free(node);
    		stack->count--;
    	}
    	return OK;
    }
    //判断链栈是否为空
    Status EmptyLinkStack(LinkStack* stack) {
    	if (!stack)
    	{
    		return ERROR;
    	}
    	return stack->count == 0 ? 1 : 0;
    }
    //获取元素个数
    int GetLengthLinkStack(LinkStack* stack)
    {
    	if (!stack )
    	{
    		return	-1;
    	}
    	return stack->count;
    }
    Status GetTop(LinkStack* stack, StackNode** stackNode)
    {
    	if (!stack)
    	{
    		return	ERROR;
    	}
    	*stackNode = stack->top;//将栈顶元素的指针返回，获取指向可修改栈顶元素内容。
    	return OK;
    }
    //Status GetTop(LinkStack* stack, StackNode* stackNode)
    //{
    //	if (!stack)
    //	{
    //		return	ERROR;
    //	}
    //	*stackNode = *(stack->top);//将栈顶元素的副本内容，修改不会影响到栈顶元素。
    //	return OK;
    //}
    /*
    弹栈
    栈顶指针指向要弹出元素前置结点，然后释放弹出元素内存空间，然后count-1
    */
    Status pop(LinkStack* stack,EleType *e)
    {
    	if (!stack && stack->count)
    	{
    		return	ERROR;
    	}
    	StackNode* node = stack->top;
    	*e = node->data;
    	stack->top = node->next;//栈顶指针指向新的栈顶元素
    	free(node);//释放元素空间
    	stack->count--;
    	return OK;
    }
    /*
    压栈
    先将压入元素放入到链表表中，然后再将栈顶指针指向压入的元素，然后count+1.
    */
    Status push(LinkStack* stack,EleType e)
    {
    	if (!stack)
    	{
    		return ERROR;
    	}
    	StackNode* node = (StackNode*)malloc(sizeof(StackNode));
    	node->next = stack->top;//将元素加入链表中
    	node->data = e;
    	stack->top = node;//栈顶元素指向压入元素
    	stack->count++;
    	return OK;
    }
    void PrintfLinkStack(LinkStack* stack)
    {
    	if (!stack&&stack->count)
    	{
    		return;
    	}
    	StackNode* node = stack->top;
    	while (node)
    	{
    		printf("%d,", node->data);
    		node = node->next;
    	}
    	puts("");
    	return;
    }
    int main(int argc, char *argv[])
    {
    	LinkStack stack;
    	InitLinkStack(&stack);//初始化
    	push(&stack, 1);
    	push(&stack, 2);
    	push(&stack, 3);
    	push(&stack, 4);
    	push(&stack, 5);
    	puts("链栈元素：");
    	PrintfLinkStack(&stack);
    	printf("链栈元素个数：%d\n", GetLengthLinkStack(&stack));
    	EleType e1,e2;
    	pop(&stack, &e1);
    	printf("弹出第一个元素：%d\n", e1);
    	pop(&stack, &e2);
    	printf("弹出第二个元素：%d\n", e2);
    	puts("链栈元素：");
    	PrintfLinkStack(&stack);
    	printf("链栈元素个数：%d", GetLengthLinkStack(&stack));
    	printf("\n");
    	return 0;
    }

验证结果：

![Center 3][]

学习算法，我们首先要去领悟它的这种思想，以后在遇到问题时才会有思路。

[Center]: /images/20220603/95f7b75d17ab4cbaa5a6d39aaa5d52c1.png
[Center 1]: /images/20220603/b48b75b9a64c41718fc2c6886b149ccb.png
[Center 2]: /images/20220603/61e6ee5e33e24be08f2ee87291473590.png
[Center 3]: /images/20220603/16e6438a3b0745df9f2e4ec63850b2a6.png