C# · 12月 19, 2021

数据结构知识整理 – 链栈

主要内容

栈的定义

链栈的存储结构

链栈的各项操作

初始化

入栈

出栈

取栈顶元素

 

栈的定义

栈和队列是两种重要的线性结构,与一般线性表不同,它们是操作受限的特殊线性表,主要用于辅助其他数据结构的操作和处理,基本不用于存储数据元素信息。

栈(stack)是限定仅在表尾进行插入或删除操作的线性表,即后进先出(Last In First Out,LIFO)。因此,对栈来说,表尾端有其特殊含义,称为栈顶(top),相应地,表头端称为栈底(bottom)。不含元素的空表称为空栈。

日常生活中有许多栈的例子。例如,盘子洗好从下往上叠,用的时候从上往下拿;货物进仓从里往外堆放,取货的时候从外往里取出等等。

在程序设计时,如果需要按照保存数据时相反的顺序来使用数据,则可以用栈来实现。例如,括号(字符)的嵌套,从里往外嵌套,从外往里求解;算术运算符的优先级,按一定条件入栈和出栈运算等等。

链栈的存储结构

链栈是指采用链式存储结构实现的栈,通常采用单链表。

初始状态时,栈底结点为空,即 LinkStack S == NULL; ,这同时也是判断空栈的条件;

当插入新结点时,S指向新结点,新结点指向栈底结点。

typedef struct StackNode

{

Elemtype data;

struct StackNode *next;

} StackNode,*LinkStack;

链栈的各项操作

栈的主要操作是在栈顶插入和删除元素,所以以链表的头部作为栈顶(指针)最为合适。

初始化

构造空栈。

void InitStack(LinkStack &S)

{

S = NULL;

}

入栈

链栈在入栈前不需要判断是否栈满,只需要为入栈元素动态分配一个结点空间。

void Push(LinkStack &S,Elemtype e)

{

StackNode *p = new StackNode;

p->data = e;

p->next = S;

S = p;

}

出栈

链栈在出栈前同样需要判断是否空栈,而且还需要释放出栈元素的空间。

Elemtype Pop(LinkStack &S,Elemtype &e)

{

if(S == NULL) exit(-1);

e = S->data;

StackNode *p = S; /*用p临时保存出栈结点的空间,以备释放*/

S = S->next;

delete p; /*使用完出栈元素,可以释放空间*/

return e; /*返回出栈元素信息*/

}

取栈顶元素

栈非空,取元素,栈顶指针不变。

Elemtype GetTop(LinkStack S,Elemtype &e)

{

if(S != NULL)

return S->data;

}