链式栈
一、链式栈的栈顶在哪里？
二、链式栈的结构：
typedef struct LSNode
{
int data;
struct LSNode* next;
}LSNode, *PLStack;
// 链栈的节点，由于栈顶在第一个数据节点，所以不需要top指针
三、链式栈的实现
//初始化
void InitStack(PLStack ps)
{
assert(ps != NULL);
ps->next = NULL;
}
//往栈中入数据
bool Push(PLStack ps, int val)
{
assert(ps != NULL);
LSNode *p = (LSNode*)malloc(sizeof(LSNode));
assert(p != NULL);
p->data = val;
p->next = ps->next;
ps->next = p;
return true;
}
//获取栈顶元素的值，但是不删除
bool GetTop(PLStack ps, int* rtval)
{
assert(ps != NULL);
if(IsEmpty(ps))
return false;
*rtval = ps->next->data;
return true;
}
//获取栈顶元素的值，但是删除
bool Pop(PLStack ps, int* rtval)
{
assert(ps != NULL);
if(IsEmpty(ps))
return false;
LSNode* p = ps->next;
*rtval = p->data;
ps->next = p->next;
free(p);
return true;
}
//判空
bool IsEmpty(PLStack ps)
{
assert(ps != NULL);
return ps->next == NULL;
}
//获取栈中有效元素的个数
int GetLength(PLStack ps)
{
assert(ps != NULL);
int count = 0;
for(LSNode *p = ps->next; p != NULL; p = p->next)
{
count++;
}
return count;
}
//清空所有数据
void Clear(PLStack ps)
{
Destroy(ps);
}
//销毁
void Destroy(PLStack ps)
{
assert(ps != NULL);
//总是删除第一个数据节点
LSNode *p
while(p->next != NULL)
{
p = p->next;
ps->next = p->next;
free(p);
}
}
四、链式栈的总结
**链栈栈顶：栈顶在表头（即第一个数据节点）（时间复杂度为O(1)）
