一、栈栈和队列可看作是特 殊的线性表,它们是 运算受限的线性表 定义:栈是只能在表的一端(表尾)进行 插入和删除的线性表
特点:后进先出 栈中元素按a1,a2,a3,…an的次序进栈,出栈的第一个元素应 为栈顶元素。换句话说,栈的修改是按后进先出的原则进行的。 因此,栈称为后进先出线性表(LIFO)。 栈的用途:常用于暂时保存有待处理的数据。 栈的基本操作
栈的分类:按照顺序结构存储是顺序栈、按照链式结果存储是链栈 二、顺序栈 顺序栈—— 即栈的顺序实现; 栈容量——栈中可存放的最大元素个数; 栈顶指针 top——指示当前栈顶元素在栈中的位置; 栈空——栈中无元素时,表示栈空; 栈满——数组空间已被占满时,称栈满; 下溢——当栈空时,再要求作出栈运算,则称“下溢”; 上溢——当栈满时,再要求作进栈运算,则称“上溢”。
1、顺序栈的类型定义 const int maxsize=6; typedef struct seqstack { DataType data[maxsize]; int top; }SeqStk; SeqStk *s ; 定义一顺序栈s 2、初始化: int Initstack(SeqStk *stk){ stk->top=0; return 1; } 3、判栈空(栈空时返回值为1,否则返回值为0) int EmptyStack(SeqStk *stk){ if(stk->top= =0) return 1; else return 0; } 4、进栈 int Push(SeqStk *stk, DataType x){ /*数据元素x进顺序栈sq*/ if(stk->top==maxsize -1) /*判是否上溢*/ { error(“栈满”);return 0;} /*上溢*/ else { stk->top++;/*修改栈顶指针,指向新栈顶*/ stk->data[stk->top]=x; /*元素x插入新栈顶中*/ return 1; } } } 5、出栈 int Pop(SeqStk *stk){ /*顺序栈sq的栈顶元素退栈*/ if(stk->top==0) /*判是否下溢*/ { error(“栈空”);return 0;} /*下溢*/ else { stk->top-- ; /*修改栈顶指针,指向新栈顶*/ return 1; } }/*Pop*/ 6、取栈顶元素 DataType GetTop(SeqStk *stk) { if(EmptyStack(stk)) return NULLData; else return stk->data[stk->top]; } 三、链栈链栈的定义: 栈的链式存储结构称为链栈,它是运算受限的单链表, 插入和删除操作仅限制在表头位置上进行。栈顶指针就是链 表的头指针
1、初始化 void InitStack(LkStk *LS) { LS=(LkStk *)malloc(sizeof(LkStk)); LS->next=NULL; } 2、判栈空 int EmptyStack(LkStk *LS) { if(LS->next= =NULL) return 1; else return 0; } 3、进栈——在栈顶插入一元素x
void Push (LkStk *LS, DataType x){ LkStk *temp; temp= (LkStk *) malloc (sizeof (LkStk)); temp->data=x; temp->next=LS->next; LS->next=temp; } 4、出栈——在栈顶删除一元素,并返回
int Pop (LkStk *LS) { LkStk *temp; if (!EmptyStack (LS)) { temp=LS->next; LS->next=temp->next; free(temp); return 1; } else return 0; } 5、取栈顶元素 DataType GetTop(LkStk *LS) { if (!EmptyStack(LS)) return LS->next->data; else return NULLData; }
|
|
来自: python_lover > 《待分类》