栈(stack)是限制插入和删除只能在一个位置上进行的线性表,该位置通常在表的末端,叫做栈顶(top)----实际上我喜欢把链表的表头作为栈顶,栈顶不存储任何值,只是一个标志,所谓的“栈顶元素”实际上
是链表的头结点的直接后继的值。这样实行插入和删除操作都很方便。栈可以用链表(包括动态链表和静态链表)实现,也可以用数组实现。我们先来看看如何用链表实现(以动态链表为例,大家可以推广到静态链表中)。
//-----------用动态单链表实现栈的存储结构-------------
typedef struct Node{
ElemType data;
struct Node *next;
} *LNode, *Stack;
//-------------------用动态单链表实现栈的基本操作------------------------
Stack InitStack(void); //构造一个空栈
void DestroyStack(Stack *S);//初始条件:栈S已存在。 操作结果:销毁栈S。
Stack MakeEmpty(Stack S);//初始条件:栈S非空。 操作结果:将栈S重置为空栈。
int IsEmpty(Stack S);//初始条件:栈S已存在。 操作结果:判断栈是否为空栈。
int StackLength(Stack S);//初始条件:栈S已存在。 操作结果:返回栈S结点的个数。
ElemType GetTop(Stack S);//初始条件:栈S非空。 操作结果:返回栈顶元素的值
LNode NewLNode(ElemType X);//构造一个数据域为X的新结点
//初始条件:栈S已存在。 操作结果:插入元素X为新的栈顶元素
void Push(Stack S, ElemType X);
ElemType Pop(Stack S);//初始条件:栈S非空。 操作结果:删除S的栈顶元素, 并返回其值
//---------------------------------------------------------------
其实我们很容易发现,上面的9个基本操作中有6个与动态链表的基本操作是一样的,这里就不重复了,我们把剩下的3个的算法实现列出来。
注意:在这里我将直接调用动态链表的基本操作.
//----------用动态单链表实现栈的基本操作的算法实现-----
ElemType GetTop(Stack S);//初始条件:栈S非空。 操作结果:返回栈顶元素的值
{
return S->next->data;
}
//初始条件:栈S已存在。 操作结果:插入元素X为新的栈顶元素
void Push(Stack S, ElemType X)
{
LNode P;
P = NewLNode(X);
ListInsert(S, P);
}
ElemType Pop(Stack S);//初始条件:栈S非空。 操作结果:删除S的栈顶元素, 并返回其值
{
ElemType X = GetTop(S);
ListDelete(S);
return X;
}
//---------------------------------------------------------------------------------
栈的数组实现.一个数组实现栈是很简单的.每一个栈有一个TopOfStack(简称Top),对于空栈它是-1---这就是空栈的初始化(有朋友也许会问,为什么不取值0,你不是喜欢有一个象征物“栈顶”吗,就像链表中的头指针一样?