C语言程序设计 清华大学郑莉安颖莲 第十二讲数据结构基础 ①《计算机程序程序设计基础》第10章 ②《数据结构》(严蔚敏等编著)第3章
C语言程序设计 清华大学 郑莉 安颖莲 第十二讲 数据结构基础 （二） ①《计算机程序程序设计基础》第10章 ②《数据结构》（严蔚敏 等 编著）第3章
C语言程序设计 清华大学郑莉安颖莲 本讲主要内容 栈的概念和基本操作 栈的存储结构 ·栈的应用举例 ·队列的概念和基本操作 队列的存储结构 队列的疝用举例
C语言程序设计 清华大学 郑莉 安颖莲 Page 2 本讲主要内容 • 栈的概念和基本操作 • 栈的存储结构 • 栈的应用举例 • 队列的概念和基本操作 • 队列的存储结构 • 队列的应用举例
C语言程序设计 清华大学郑莉安颖莲 栈的概念和基本操作 栈的定义 栈是限定仅在表尾进行插入或删除操作的线性表。 表尾称为栈顶,表头称为栈底。不含元素的空表称 为空栈。 栈又称为后进先出(LIFO)的线性表。 栈的基本操作 生成空栈 进栈 出栈 查询栈顶结点 判断栈是否为空
C语言程序设计 清华大学 郑莉 安颖莲 Page 3 栈的概念和基本操作 • 栈的定义 - 栈是限定仅在表尾进行插入或删除操作的线性表。 - 表尾称为栈顶，表头称为栈底。不含元素的空表称 为空栈。 - 栈又称为后进先出（LIFO）的线性表。 • 栈的基本操作 - 生成空栈 - 进栈 - 出栈 - 查询栈顶结点 - 判断栈是否为空
C语言程序设计 清华大学郑莉安颖莲 栈的存储结构 栈的顺序存储结构一顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈 顶的数据元素。 栈的链式存储结构一链栈
C语言程序设计 清华大学 郑莉 安颖莲 Page 4 栈的存储结构 • 栈的顺序存储结构－顺序栈 利用一组地址连续的存储单元依次存放自栈底到栈 顶的数据元素。 • 栈的链式存储结构－链栈
C语言程序设计 清华大学郑莉安颖莲 栈的应用举例 数制转换 输入任意一个非负十进制整数,输出与其等值 的八进制数。 void conversion o InitStack(S scanf(%d,N while(n push(S,N‰8);n=n/8;} while(! StackEmpty) Pop(s, e): printf( %d", e)
C语言程序设计 清华大学 郑莉 安颖莲 Page 5 栈的应用举例 ——数制转换 • 输入任意一个非负十进制整数，输出与其等值 的八进制数。 void conversion() { InitStack(S); scanf("%d",N); while(N) { push(S,N%8); n=n/8; } while(!StackEmpty) { Pop(S,e); printf("%d",e); } }