数据结构链式栈

Source

上一节我们学习了顺序栈

我们了解到栈就是特殊的线性表

我们之前用过顺序表实现了栈那么我们也可以用单链表的方式来实现一个链式栈

我们可以回顾一下单链表的结构

基础数据结构链表_iccoke的博客-CSDN博客

我们可以看到简单的对尾部进行操作

很难实现时间复杂度达到O（1）

那么我们设计这样的链式栈就没有意义了

因此我们要找到一个方法让出栈和入栈的时间复杂度达到最小

我们就考虑到了单链表中对于头结点操作

时间复杂度可以达到O（1）

因此我们就把头插当作入栈头删当作出栈

依然可以实现先进后出和后进先出的栈的特点

同时可以在链式结构中达到了 O(1)

那么他的代码就就很简单了

我们可以直接给出因为代码和普通单链表的重复较高

直接学习单链表的时候我们提到过

单链表在数据结构的学习中重要性举足轻重

#pragma once

typedef int ELEM_TYPE;
typedef struct LStack
{
	ELEM_TYPE data;//数据域
	struct LStack *next;//指针域
}LStack, *PLStack;

//链式栈的操作实现：
//初始化
void Init_LStack(struct LStack *ls);

//入栈(相当于单链表的头插)
bool Push(struct LStack* ls, ELEM_TYPE val);

//出栈(相当于单链表的头删)
bool Pop(struct LStack* ls);

//获取栈顶元素值 //获取栈顶的元素值，但是不删除
ELEM_TYPE Top(struct LStack* ls);

//判空
bool Is_Empty(struct LStack* ls);

//搜索
struct LStack* Search(struct LStack* ls, ELEM_TYPE val);

//清空
void Clear(struct LStack* ls);

//销毁
void Destroy(struct LStack* ls);

//打印
void Show(struct LStack* ls);

//获取有效值个数
int Get_length(struct LStack* ls);

但是因为我们只是来实现链式栈的结构

因此我们的实现函数只有出栈出栈获取栈顶元素销毁打印获取有效值个数搜索

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "list_stack.h"

//初始化
void Init_LStack(struct LStack *ls)
{
	//assert ls
	ls->next = NULL;
}

//入栈(相当于单链表的头插)
bool Push(struct LStack* ls, ELEM_TYPE val)
{
	//assert 
	struct LStack *pnewnode = (struct LStack *)malloc(1 * sizeof(struct LStack));
	assert(pnewnode != NULL);
	pnewnode->data = val;

	pnewnode->next = ls->next;
	ls->next = pnewnode;
	return true;
}

//出栈(相当于单链表的头删)
bool Pop(struct LStack* ls)
{
	//assert ls
	if(Is_Empty(ls))
	{
		return false;
	}

	struct LStack* p = ls->next;
	ls->next = p->next;
	free(p);

	return true;
}

//获取栈顶元素值 //获取栈顶的元素值，但是不删除
ELEM_TYPE Top(struct LStack* ls)
{
	//assert ls
	if(Is_Empty(ls))
	{
		return false;
	}

	return ls->next->data;
}

//判空
bool Is_Empty(struct LStack* ls)
{
	//assert

	return ls->next == NULL;
}

//搜索
struct LStack* Search(struct LStack* ls, ELEM_TYPE val)
{
	//assert
	//使用哪种for循环？ 使用不需要前驱的for循环
	//而不需要前驱的for循环，指针p初始时指向第一个有效节点

	struct LStack* p = ls->next;
	for(; p!=NULL; p=p->next)
	{
		if(p->data == val)
		{
			return p;
		}
	}
	return NULL;
}

//清空
void Clear(struct LStack* ls)
{
	Destroy(ls);
}

//销毁2
void Destroy(struct LStack* ls)
{
	//assert

	struct LStack *p = ls->next;
	struct LStack *q = NULL;

	ls->next = NULL;

	while(p != NULL)
	{
		q = p->next;
		free(p);
		p = q;
	}
}

//打印
void Show(struct LStack* ls)
{
	struct LStack* p = ls->next;
	for(; p!=NULL; p=p->next)
	{
		printf("%d ", p->data);
	}
	printf("\n");
}

//获取有效值个数
int Get_length(struct LStack* ls)
{
	int count = 0;
	struct LStack* p = ls->next;
	for(; p!=NULL; p=p->next)
	{
		count++;
	}
	return count;
}

这里比较重要的就是两个结点互相配合销毁链表的方式

还有就是在打印统计个数时我们使用不依赖头结点的循环