加文

在这个世界上取得成就的人,都努力去寻找他们想要的机会,如果找不到机会,他们便自己创造机会。 -- 萧伯纳
随笔 - 14, 文章 - 56, 评论 - 1, 引用 - 0
数据加载中……

栈和队列

1. 栈和队列的概念

1) 栈:只允许一端进行插入和删除的线性表;允许插入和删除的一端叫做栈顶;不允许插入和删除的一端叫做栈底.先进后出

2) 队列:允许插入的一端为队首,允许删除的一端为队尾.先进先出

2. 存储结构

1) 栈的顺序存储结构:结构体,有数组和顶指针

2) 栈的链式存储结构:单链表

3) 队列的顺序存储结构:结构体,数组,首尾指针

4) 队列的链式存储结构:单链表.

5) 循环队列:队列为空时:rear==front;队列满时:(rear+1)%maxSize = front.(牺牲了一个存储空间单元)

3. 应用

1) 栈在表达式中的应用

① 前缀表达式:(A+B)*C---->*C+AB  (波兰式);(运算符在前,从右到左扫描)

② 后缀表达式:(A+B)*C------>AB+C*.(运算符在后,从左到有扫描)

2) 栈递归中的应用

3) 使用队列主要是为了保存下一步的处理步骤

4) 特殊矩阵的压缩存储

① 二维数组对于二维矩阵对应,数组的下标对应矩阵的下标A[m][n];

② 二维矩阵的行优先存储,a[i][j]对应的存储位置为loc(0,0)+(i*m+j)*L

③ 下三角矩阵行优先存储:a[i,j]在数组B中的存储位置为1+2+3+……+i+j

④ 上三角矩阵行优先存储:a[i,j]在数组B中的存储位置为n+……+(n+1-i)+j-i;

 

posted on 2011-10-26 11:16 chxzwj 阅读(186) 评论(0)  编辑 收藏 引用 所属分类: 数据结构


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理