如果在头节点做插入操作和删除操作是可以的,因为头节点知道下一个元素的位置在哪儿,就可以把TOP指向下一个元素。
但插入也能在链尾操作,可以用当前的这个链表的尾巴指向一个新的结点。
删除不可以,因为这是单向链表,删除之后,找不到前面的一个结点。
/*
堆栈的链式存储实现结构
*/
typedef struct SNode *Stack;
struct SNode{
ElementType Data;
struct SNode *Next;
};
/*
1)堆栈初始化(建立空栈)
构建一个堆栈的头结点,返回指针。
这个头结点不代表任何一个元素,只是通过这个头结点可以方便的找到堆栈里面的一些具体的元素。
插入一个结点,实际上就是在头结点插入新的结点。
*/
Stack CreateStack(){
Stack S;
S = (Stack)malloc(sizeof(struct SNode));
S->Next = NULL;
return S;
}
上述建立一个空栈,实际上是形成这种一种结构。
/*
2)判断堆栈是否为空
若为空,函数返回整数1,否则返回0。
*/
int IsEmpty(Stack S){
return (S->Next == NULL);
}
/*
将元素item压入堆栈S
注意这里在做PUSH操作时不去判断堆栈是否满,
如果是数组实现堆栈的时候,数组大小是固定的,所以数组存在是否满的问题。
如果是链表,是通过不断地申请节点空间往里面插,所以就不需要判断是否满的问题。
*/
void push(ElementType item, Stack S){
struct SNode *TmpCell;
TmpCell=(struct SNode *)malloc(sizeof(struct SNode));
TmpCell->Element = item;
TmpCell->Next = S->Next;
S->Next = TmpCell;
}
/*
将元素item弹出堆栈S
*/
ElementType Pop(Stack S){
//删除并返回堆栈S的栈顶元素(跟插入操作颠倒过来)
struct SNode *FirstCell;
ElementType TopElem;
if(IsEmpty(S)){
printf("堆栈空");
return NULL;
}else{
//下述的三个FirstCell是同一个对象
FirstCell = S->Next;
//完成结点指针的重新指向
S->Next = FirstCell->Next;
TopElem = FirstCell->Element;
//删掉的结点的空间必须要释放
free(FirstCell);
return TopElem;
}
}
标题:(数据结构)第二讲-线性结构(2.2.3堆栈的链式存储实现)
作者:yazong
地址:https://blog.llyweb.com/articles/2023/08/15/1692030187242.html