第三章栈与队列 东南大学计算机学院方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件
第三章 栈与队列 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件
本章主要内容 栈 ■栈的应用:表达式求值 栈与递归 队列 队列的应用:电路布线
本章主要内容 ◼ 栈 ◼ 栈的应用：表达式求值 ◼ 栈与递归 ◼ 队列 ◼ 队列的应用：电路布线 2
■定义:只允许在表的末端进行插入和删除的线 性表 特点:先进后出 栈的操作 口进栈push 出栈pp0 口栈顶top( 置空 setEmpty() 判断是否为空 isEmpty() 口栈满 isFul(
栈 ◼ 定义：只允许在表的末端进行插入和删除的线 性表 ◼ 特点：先进后出 ◼ 栈的操作 进栈 push() 出栈 pop() 栈顶 top() 置空 setEmpty() 判断是否为空 isEmpty() 栈满 isFull() 3
栈的数组表示 ■栈的操作 进栈push0 push( 口出栈pop0 口栈顶top( 置空 makeEmpty0 top→ 判断是否为空 isEmpty0 口栈满 isFull( top→ top→空栈
栈 ◼ 栈的数组表示 ◼ 栈的操作 进栈 push() 出栈 pop() 栈顶 top() 置空 makeEmpty() 判断是否为空 isEmpty() 栈满 isFull() 4 top a top b top c top 空栈
■栈的单链表表示 栈的数组表示可能栈满 栈的单链表表示无栈满问题 口入栈在表头进行插入操作 top c 出栈在表头进行删除操作 a null
栈 ◼ 栈的单链表表示 栈的数组表示可能栈满 栈的单链表表示无栈满问题 入栈在表头进行插入操作 出栈在表头进行删除操作 5 top c b a null