一.链式栈的栈顶在哪里?
二.链栈的结构:
typedef struct LSNode{
int data;
struct LSNode* next;
}LSNode ,*PLStack;
//链栈的节点.由于栈顶在第一个数据节点,所以不需要top指针
三.链式栈的实现:
//初始化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 (ps == NULL)return false;if (IsEmpty(ps))return false;*rtval=ps->next->data;return true;
}
//获取栈顶元素的值,但是删除
bool Pop(PLStack ps, int* rtval)
{assert(ps != NULL);if (ps == NULL)return false;if (IsEmpty(ps))return false;LSNode* p = ps->next;*rtval = p->data;ps->next = p->next;free(p);return true;
}
//判空
bool IsEmpty(PLStack ps)
{return ps->next == NULL;
}
//获取栈中有效元素的个数
int GetLength(PLStack ps)
{assert(ps != NULL);if (ps == NULL)return -1;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)
{//总是删除第一个数据节点LSNode* p;while (ps->next != NULL){p = ps->next;ps->next = p->next;free(p);}
}
四.链式栈的总结:
链栈栈顶:栈顶在表头(即第一个数据节点)(时间复杂度是O(1))