栈(stack):是限定仅在表尾进行插入和删除操作的线性表。 把允许插入和删除的一端称为栈顶(top),不含任何数据元素的栈称为空栈。栈是一种后进先出(LIFO)的线性表。
栈的结构定义
1 | typedef int SElemType; |
压栈操作
1 | Status push(SqStack *S,SElemType e) |
弹栈操作
1 | Status pop(SqStack *S,SElemType *e) |
压栈和弹栈的时间复杂度均为O(1)
栈的应用-逆波兰表达式
逆波兰表达式的使用规则:从左至右遍历表达式的每个数字和字符,遇到数字就进栈,遇到符号就将栈顶的两个元素出栈,并进行运算,将运算结果压栈,直到获得最终的结果。
假设我们直到如下表达式:1
9 3 1 - 3 * + 10 2 / +
它对应的四则运算表达式为:1
9 + ( 3 - 1 ) * 3 + 10 / 2
我们需要明确以下算法,然后进行程序设计:
- 从左至右遍历
- 遇到数字则进栈
- 遇到运算符则将栈顶两元素出栈,运算后将运算结果进栈
- 获取最终运算结果
1 | package com.xiaopeng.npl; |
队列(Queue):一种只允许在一端进行插入操作,另一端进行删除操作的线性表。队列是一种先进先出(FLFO)的线性表。允许插入的一端称为队尾,允许删除的一端称为队头。
总结:
顺序存储结构的栈与队列都是特殊的线性表.
Java中栈与堆:
- Java应用程序在执行时,栈中数据会保存以下内容:基本数据类型的值,引用变量的值(堆区对象的引用)
- 栈中的数据和堆中的数据销毁并不是同步的。方法一旦结束,栈中的局部变量(方法栈或线程栈)立即销毁,但是堆中对象不一定销毁。因为可能有其他变量也指向了这个对象,直到栈中没有变量指向堆中的对象时,它才销毁,而且还不是马上销毁,要等垃圾回收扫描时才可以被销毁【垃圾回收机制自动判断对象是否可以被销毁,可以调用System.gc(),但是不确保一定能销毁对象】。
- 每个方法执行的时候都会建立自己的栈区,在方法中定义的局部变量(参数,方法中定义的变量)都在栈区中存放当方法结束时这些局部变量也就结束了,但是堆内存中的对象不会随着方法的结束而销毁,而是判断还有没有引用变量引用到这个对象如果有的话就是说这个对象可达所以不会轻易的被GC回收。
本文作者:
肖鹏
本文链接: http://www.xiaopeng.pro/articles/8d66b5f2.html
版权声明: 本原创文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!
本文链接: http://www.xiaopeng.pro/articles/8d66b5f2.html
版权声明: 本原创文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!