链栈的存储结构其实就是单链表,插入和删除在链表头进行(书上这么写,个人认为只要是在链表一端操作即可)。
链栈的数据结构类型为:
#include <cstdio>
#include <cstdlib>
typedef int DataType;
struct LinkStack
{
DataType data;
struct LinkStack *next;
};
基本操作实现:
//初始化头节点, 数据域存储链栈大小,指针域置空
void InitStack(LinkStack &s)
{
s.data = 0;
s.next = NULL;
}
bool isEmpty(LinkStack &s)
{
return s.data == 0 ? true : false;
}
void Push(LinkStack &s, DataType e)
{
LinkStack *p;
p = (LinkStack*)malloc(sizeof(LinkStack));
p->data = e;
p->next = s.next;
s.next = p;
s.data++;
}
DataType Pop(LinkStack &s)
{
if(isEmpty(s))
{
printf("Empty!\n");
return NULL;
}
LinkStack *p;
DataType top;
p = s.next;
s.next = p->next;
s.data--;
top = p->data;
free(p);
return top;
}
测试代码:
int main()
{
LinkStack s;
InitStack(s);
for(int i = 0; i < 10; i++)
Push(s, i);
int t;
while(!isEmpty(s))
{
t = Pop(s);
printf("%d ", t);
}
printf("\n");
t = Pop(s);
Push(s, 100);
t = Pop(s);
printf("%d\n", t);
return 0;
}