首页 > 代码库 > 链式栈总结
链式栈总结
基本数据结构之—链式栈
链式栈-其实简单的理解就是一个受到操作限制的单向链表,因为栈只有简单的一些操作,比如:入栈,出栈,获取栈顶,栈的清空等
先分析一下栈的基本数据吧
栈作为一种容器,那么需要存储数据的地方,为了方便,只存储数据的开始地址是一个不错的选择
为了快速的知道栈的长度,我们在维护一个长度的参数,和顺序栈的区别是我们不用考虑容量的问题
当然你也可以维护更多的参数来支持你想要的操作。
栈的链式存储,底部使用的是链表的知识。为了方便操作和提升性能,我们将链表的头结点当做栈顶。
为了有个统一的结点来传递地址,直接定义一个指针
typedef struct _STACKNODE
{
struct _STACKNODE *Next;
}StackNode;
栈的基本结构
typedef struct _LINKSTACK
{
// 栈的数据(其实是地址)
StackNode Head;
// 栈的长度
int Size;
}LinkStack;
先判断现在栈的结点的情况,如果为空,则开辟一个空间。
//初始化
int Init_LinkStack(void **linkstack)
{
if (linkstack == NULL)
{
exit(-1);
}
// 将数据类型进行转化,便于后面的操作
LinkStack **stack = (LinkStack **)linkstack;
// 检查栈是否已经有可用的内存
if (*stack == NULL)
{
*stack = (LinkStack *)malloc(sizeof(LinkStack));
}
// 对开辟空间的检测
if (*stack == NULL)
{
exit(-2);
}
// 将数据和长度初始化
(*stack)->Head.Next = NULL;
(*stack)->Size = 0;
return 0;
}
入栈操作就是将数据的头指针的数据 (地址)和加入数据(地址)做一个交换
// 入栈
int Push_LinkStack(void *linkstack, void *Data)
{
if (linkstack == NULL)
{
return -1;
}
if (Data =http://www.mamicode.com/= NULL)
{
return -2;
}
// 将数据类型进行转化,便于后面的操作
LinkStack *stack = (LinkStack *)linkstack;
StackNode *data = http://www.mamicode.com/(StackNode *)Data;
data->Next = stack->Head.Next;
stack->Head.Next = data;
++stack->Size;
return 0;
}
将第一个位置的元素指向下一个位置,如果长度为0,就不操作
// 出栈
int Pop_LinkStack(void *linkstack)
{
if (linkstack == NULL)
{
return -1;
}
// 将数据类型进行转化,便于后面的操作
LinkStack *stack = (LinkStack *)linkstack;
// 栈为空,不能出栈
if (stack->Size == 0)
{
return -2;
}
else
{
stack->Head.Next = stack->Head.Next->Next;
--stack->Size;
}
return 0;
}
// 返回栈顶元素
void *Top_LinkStack(void *linkstack)
{
if (linkstack == NULL)
{
return NULL;
}
// 将数据类型进行转化,便于后面的操作
LinkStack *stack = (LinkStack *)linkstack;
// 栈为空,不能出栈
if (stack->Size == 0)
{
return NULL;
}
// 返回第一个元素
return stack->Head.Next;
}
栈的大小
int Size_LinkStack(void *linkstack)
{
if (linkstack == NULL)
{
return 0;
}
// 将数据类型进行转化,便于后面的操作
LinkStack *stack = (LinkStack *)linkstack;
return stack->Size;
}
// 销毁栈
int Destory_LinkStack(void *linkstack)
{
if (linkstack == NULL)
{
return -1;
}
// 将数据类型进行转化,便于后面的操作
LinkStack *stack = (LinkStack *)linkstack;
if (stack->Head.Next != NULL)
{
stack->Head.Next = NULL;
}
stack->Size = 0;
return 0;
}
链式栈总结