例:进栈、出栈顺序问题 有1,2,3三个元素依次入栈序。写出可 能的出栈序列。 出栈序列 操作序列 123 S X S X S X 132 S X SS XX 3 SS XX S X 231 SS X S XX 321 SSS XXX 2021年2月24日 11
2021年2月24日 11 例：进栈、出栈顺序问题 有1，2，3三个元素依次入栈序。写出可 能的出栈序列。 出栈序列 操作序列 1 2 3 s x s x s x 1 3 2 s x s s x x 2 1 3 s s x x s x 2 3 1 s s x s x x 3 2 1 s s s x x x
算法1-8进栈算法 ■算法步骤 stepl 判别栈满否,若满,则显示栈溢出 信息,停止执行;否则,执行step Step. 2 栈顶指针top上移(加1); Step3 在top所指的位置插入元素x 2021年2月24日
2021年2月24日 12 算法1-8 进栈算法 ◼ 算法步骤: ◼ step1 判别栈满否，若满，则显示栈溢出 信息，停止执行；否则，执行step 2； ◼ Step2 栈顶指针top上移(加1)； ◼ Step3 在top所指的位置插入元素x
算法1-8进栈算法程序 push (int x) t if (top== MAXSIzE-1 printf(“栈上溢!n?) exit(1) else top++;/*栈指针加1*/ stack[top]=x;/米元素x进 栈*/ 2021年2月24日 13
2021年2月24日 13 算法1-8 进栈算法程序 push（int x） { if（top = = MAXSIZE -1） { printf（“栈上溢！\n”）; exit （1）; } else { top + +；/* 栈指针加 1 */ stack [ top ] = x ；/* 元素 x进 栈*/ } }
算法1-9出栈算法 算法步 stepl判别栈是否为空;若空,则 输出 栈下溢信息,并停止执行; 否则, 执行step2; step2弹出(删除)栈顶元素; step3栈顶指针top下移(减1) 2021年2月24日 14
2021年2月24日 14 算法1-9 出栈算法 ◼ 算法步骤: ◼ step1 判别栈是否为空；若空，则 输出 栈下溢信息，并停止执行； 否则， 执行step2； ◼ step2 弹出（删除）栈顶元素； ◼ step3 栈顶指针top下移(减1)
算法1-9出栈算法程序 pop() int x: if( top printf(“栈下溢\n?); exit(1) e lse t x= stack[ top top--;/*栈顶指针减 1*/ 2021年2月24日 return x
2021年2月24日 15 算法1-9 出栈算法程序 pop（ ） { int x; if( top = = -1） { printf(“ 栈下溢 \n”); exit(1); } else { x = stack [ top ]； top - - ；/* 栈顶指针 减 1*/ } return x ； }