考研专业课之统考计算机蓝宝书(10)

来源：跨考网 2008-11-27 13:48

2.1.2. 栈的存储实现和运算实现

1．顺序栈
利用顺序存储方式实现的栈称为顺序栈。类似于顺序表的定义，栈中的数据元素用一个预设的足够长度的一维数组来实现：datatype data[MAXSIZE]，栈底位置可以设置在数组的任一个端点，而栈顶是随着插入和删除而变化的，用一个int top 来作为栈顶的指针，指明当前栈顶的位置，同样将data和top封装在一个结构中，顺序栈的类型描述如下：

订阅收藏考研专业课之统考计算机蓝宝书

以下几点说明：
1. 对于顺序栈，入栈时，首先判栈是否满了，栈满的条件为：
s->top= =MAXSIZE-1，栈满时，不能入栈; 否则出现空间溢出，引起错误，这种现象称为上溢。
2. 出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空时常作为一种控制转移的条件。

2．链栈
用链式存储结构实现的栈称为链栈。通常链栈用单链表表示，因此其结点结构与单链表的结构相同，在此用LinkStack表示，即有：
typedef struct node
{ datatype data;
struct node *next;
}StackNode，* LinkStack;

说明top为栈顶指针： LinkStack top ;

因为栈中的主要运算是在栈顶插入、删除，显然在链表的头部做栈顶是最方便的，而且没有必要象单链表那样为了运算方便附加一个头结点。

专业课精选

专业课复习规划专业课知识库专业课真题专业课大纲

教育学统考

心理学统考

西医综合