数据结构c课件第三章栈与队列.ppt

根据栈定义，每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“必威体育精装版”的元素，即最后进栈的元素。因此，栈又称为后进先出的线性表。简称为LIFO表。如下图所示： InitStack(S) 操作前提：S为未初始化的栈。 操作结果：将S初始化为空栈。 ClearStack(S) 操作前提：栈S已经存在。 操作结果：将栈S置成空栈。 IsEmpty(S) 操作前提：栈S已经存在。 操作结果：判栈空函数，若S为空栈则函数值为“TRUE真”，否则为“FALSE”。 IsFull(S) 操作前提：栈S已经存在。 操作结果：判栈满函数，若S栈已满，则函数值为“TRUE”，否则为“FALSE”。 Push(S,x) 操作前提：栈S已经存在。 操作结果：在S的顶部插入(亦称压入)元素x；若S栈未满，将x插入栈顶位置，若栈已满，则返回FALSE，表示操作失败，否则，返回TRUE。 Pop(S, x) 操作前提：栈S已经存在。 操作结果：删除(亦称弹出)栈S的顶部元素，并用x带回该值；若栈为空，返回值为FALSE，表示操作失败，否则，返回TRUE。 GetTop(S, x) 操作前提：栈S已经存在。 操作结果：取栈S的顶部元素。与Pop(S, x)不同之处在于GetTop(S,x)不改变栈顶的位置。 3.1.2 栈的表示和实现 栈在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。 顺序存储的栈为顺序栈； 链式存储的栈为链栈。 1.顺序栈 顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以top = -1表示空栈。 用C语言定义栈的顺序存储结构 typedef int StackElementType #define Stack_Size 50 ?typedef struct { StackElementType elem[Stack_Size]; /*用来存放栈中元素的一维数组*/ int top; /*用来存放栈顶元素的下标*/ }SeqStack; 顺序栈基本操作的实现 1）初始化 void InitStack(SeqStack *S) { /*构造一个空栈S*/ S-top= -1; } 2）判栈空 int IsEmpty(SeqStack *S) /*判栈S为空栈时返回值为真，反之为假*/ { return(S-top==-1?TRUE:FALSE); } 3） 判栈满 int IsFull(SeqStack *S) /*判栈S为满时返回真，否则返回假*/ { return(S-top== Stack_Size?TRUE:FALSE); } 4）进栈 int Push(SeqStack * S, StackElementType x) { if(S-top== Stack_Size-1) return(FALSE); /*栈已满*/ S-top++; S-elem[S-top]=x; return(TRUE); } 5）出栈 int Pop(SeqStack * S, StackElementType *x) { if(S-top==-1) /*栈为空*/ return(FALSE); else { *x= S-elem[S-top]; S-top--; /* 修改栈顶指针 */ return(TRUE); } } 6） 取栈顶元素 int GetTop（SeqStack S, StackElementType *x） { /* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变 */ if(S-top==-1) /*栈为空*/ return(FALSE); else { *x = S-elem[S-top]; return(TRUE); } } 两栈共享技术 两栈共享技术： 主要利用了栈，“栈底位