顺序事 6)入操作 Push(SqStack&s, SElemTypee) 功能:将e入栈; void Push( SqStack&s, SElem Type e) elem top +1 if(s top>=S. stacksize stacksize100 I incrementStackSize(S); incrementi a S elem[S top++]=e; ex xa X 1)S是否已满著钱满,重新分配存储间 2)将元素e写入栈顶; 3)修改顶指针使栈顶指针向栈顶元素的下后面}个位置
void Push( SqStack &S, SElemType e ) { if ( S.top>=S.stacksize) incrementStackSize( S ); S.elem[S.top++] = e; } 1) S是否已满, 若栈满，重新分配存储空间； 2) 将元素e 写入栈顶； 3) 修改栈顶指针,使栈顶指针指向栈顶元素的下(后面)一个位置； 6) 入栈操作Push(SqStack &S, SElemType e ) 功能：将e入栈; 顺序栈算法 elem top stacksize increment i 100 10 a1 a2 ai-1 aiai+1 . . . . . . e x i+1 x
顺序算 6)出栈操作 Pop(SqStack &S, SElem Type&e) 功能:栈顶元素退栈,并用e返回 bool Pop_sql sqStack &S, sElem Type &e) elem a top if(s top==0)return FALSE; stacksize 100I e=Selem[- -s top]; increment10 a return true y/Pop a i+1
6) 出栈操作Pop(SqStack &S, SElemType &e ) 功能：栈顶元素退栈，并用e 返回; bool Pop_Sq( SqStack &S, SElemType &e) { if ( S.top== 0) return FALSE; e = S.elem[--S.top]; return TRUE; }//Pop 顺序栈算法 elem top stacksize increment i 100 10 a1 a2 ai-1 aiai+1 . . . . . . e a ai i i-1
3、的录与实现— 链栈 链式栈无栈满问题,空间可扩充 无栈满问题除非分插入与删除仅在栈顶处执行 栈顶一链表的表链式栈的栈顶在链头 可以不必引入头结点·适合于多栈操作 mpN匚 约定:mp指向栈顶元素所在的结点 栈游8 a a1∧ 注意:链栈中指针的方向 底元录
约定：top指向栈顶元素所在的结点 • 链栈 –无栈满问题(除非分配不出内存), 空间可扩充 –栈顶----链表的表头 –可以不必引入头结点 top ^ 栈顶指针 an a1 ∧ 注意: 链栈中指针的方向 an-1 栈底元素 N 2、栈的表示与实现──链栈 ▪ 链式栈无栈满问题，空间可扩充 ▪ 插入与删除仅在栈顶处执行 ▪ 链式栈的栈顶在链头 ▪ 适合于多栈操作
链栈 找顶 top -data next 结点定义: typedef struct node i int data struct node * next 3 Node typedef LinkList LinkStack op 入栈算法 栈脂 X 出栈算法 top- …
链栈 栈顶 top data next … ^ 栈底 结点定义: –入栈算法 –出栈算法 typedef struct node { int data; struct node *next; } Node; typedef LinkList LinkStack; …... ^ 栈底 top top x p …... ^ 栈底 top q
链情的定义 顺序算 typedef int bool; 初始化 tdefine TrUe 1 void InitStack_L( LinkStack "S define False o S= NULLE typedef int Data; typedef struct node( 入栈 ElemType data void PushL(LinkStack"S, Elem Type e) struct node"next: aNOde; LNode*p= new LNode; Typedef LinkList LinkStack p->data=e p->next= s p top 入栈算法 找底
链栈的定义 typedef int bool; #define TRUE 1; #define FALSE 0; typedef int Data; typedef struct node { ElemType data; struct node *next; } LNode; Typedef LinkList LinkStack ▪ 初始化 void InitStack_L( LinkStack *S ) { S = NULL; } ▪ 入栈 void Push_L ( LinkStack *S, ElemType e ) { LNode *p = new LNode ; p->data = e; p->next = S; S = p; } 顺序栈算法 –入栈算法 …... ^ 栈底 top top x p