我所理解的栈 栈（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，你不是喜欢有一个象征物“栈顶”吗，就像链表中的头指针一样？我的回答是，用链表实现栈的时候设置一个头结点,是为了和链表的基本操作方便的接口。虽然浪费了一个空间，但我们可以少写一些代码，所以也是划得来的。但用数组实现栈的时候，我们没有现成的代码可套用，既然一切都要从头开始，设置一个象征物“栈顶”不能为我们带来任何好处，那又必浪费空间呢？呵呵! 为了将某个元素X压入到该栈中,我们将Top加1,然后置Stack[Top] = X,其中Stack是代表具体栈的数组.为了弹出栈元素,我们置返回值为Stack[Top],然后Top减1. //-----------用数组实现栈的存储结构------------- #define EmptyTop -1 #define MinStackSize 5 typedef struct StackRecord{ int StackSize; int TopOfStack; ElemType *Array; } *Stack; //-------------------用数组实现栈的基本操作------------------------ Stack InitStack(int MaxElements); //构造一个空栈 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的栈顶元素, 并返回其值 //--------------------------------------------------------------
评论