C# 数据结构 栈 Stack

栈和队列是非常重要的两种数据结构,栈和队列也是线性结构,线性表、栈和队列这三种数据结构的数据元素和元素的逻辑关系也相同

差别在于:线性表的操作不受限制,栈和队列操作受限制(遵循一定的原则),因此栈和队列也称为受限制的线性表。

栈的定义:操作在表的尾端进行的线性表,栈顶:TOP,栈底:Bottom。栈中没有数据:空栈Empty Stack

表示方法:S=(a1,a2,a3,a4……..an)a1为栈底的元素,an为栈顶的元素.这N个数据按照先后顺序插入到栈内,找出栈内数据则相反

遵循的原则(Last In First Out 即 LIFO) 或者 (First In Last Out 即 FILO)

C# 数据结构 栈 Stack

C# 数据结构 栈 Stack

现实生活中也有很多列子:洗盘子,用盘子

C#2.0 以下版本只提供了非泛型的 Stack 类,该类继承了 ICollection、 IEnumerable 和 ICloneable 接口。 C#2.0 提供了泛型的

Stack<T>类,该类继承 了 IEnumerable<T>、ICollection 和 IEnumerable 接口。

栈的存储和实现

1.顺序栈 :用一块连续存储的空间来存储栈中的元素,连续的空间就是数组表示了。

2.链栈:在线性链表的基础上进行操作的,也就说存储结构采用的是链表的形式而操作采用的是FILO方式。

C# 数据结构 栈 Stack

生活中的实例

除了洗盘子是不是还有其他的使用方式呢?

1.数值转换 是将非负数的十进制转换成其他进制的数,一般的解决方法是辗转相除法,例如:十进制5142转

成八进制:

C# 数据结构 栈 Stack

有图我们可以看出 (5142)10=(12026)8

转换思想:

1.判断N不为0 N%8压入到栈中

2.判断N不为0 N%8压入到栈中

最后N为0 停止,从而栈中的数据全部一个一个的POP得到八进制数值。

2.程序设计中常用的问题:括号匹配问题,简化起见,只有两种括号匹配即:()和[] 嵌套的顺序是任意的

([]()) 匹配 [()[()][]] 匹配 [(]) 不匹配,加入有一堆这样的匹配的符号怎么判断呢?

思想:1.如果栈为空,则PUSH

2.如果括号和栈顶的括号匹配,则将栈顶的括号POP

3.如果括号和栈栈顶的括号不匹配,则将括号PUSH

4.最后结束时候判断栈是否为空,为空则匹配,不为空则不匹配

3.常用的算术表达式…..可以自己思考一下……

未完待续………

上一篇:Java数据结构漫谈-Stack


下一篇:Effective C++ -----条款42:了解typename的双重意义