linglingling,why星球计算机二班上课了。
老师:同学们大家好,这些节课我们来讲一下栈。那么什么是栈呢。栈是一种后进先出的线性表,它是按照后进先出的原则存储数据。Last In First Out ,简称LIFO,是只能在某一端也就是栈顶插入和删除的特殊的线性表,而栈的底部是不可操作的。
我们来看这个图(数字代表下标)
入栈:
说明:先进入的数据被压入栈底(push),同时栈顶的指向指向到刚添加的元素的位置。
出栈:
说明:最上面的数据最先出栈,同时栈顶指向出栈元素的上一个元素的位置。
老师:发散思维,想想生活中有哪些事情类似栈的操作啊?
小白:比如吃完饭收拾盘子,从低到高的罗起来像压栈操作,刷盘子的时候从上到下一个一个拿像是出栈操作。
小红:学委收作业的时候是入栈操作,发作业的时候是出栈操作。
小蓝:我们每访问一个网页就相当于是入栈,点击回退的时候,回到的是上一个页面,相当于出栈。
老师:ok,同学们的想象力很丰富呢。既然栈也是一种线性表,所以栈也分为两种,一种是顺序栈,一种是链式栈。下面我们来参考一下jdk中的Stack的实现。 ——jdk1.8
public class Stack<E> extends Vector<E> {
//...
}
Stack继承自Vector
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
protected Object[] elementData;
//..
}
根据代码可以知道java的Stack是通过顺序表的方式实现的。
Stack类里的方法:
public Stack() //一个无参构造方法
public E push(E item) //向栈添加一个元素
public synchronized E pop() // 移除栈顶元素,返回栈顶元素的值
public synchronized E peek() //查找栈顶对象
public boolean empty() //判断栈是否为空
public synchronized int search(Object o) //返回栈中元素的位置
public
class Stack<E> extends Vector<E> {
/**
* Creates an empty Stack.
*/
public Stack() {
}
/**
* Pushes an item onto the top of this stack. This has exactly
* the same effect as:
* <blockquote><pre>
* addElement(item)</pre></blockquote>
*
* @param item the item to be pushed onto this stack.
* @return the <code>item</code> argument.
* @see java.util.Vector#addElement
*/
public E push(E item) {
addElement(item);
return item;
}
/**
* Removes the object at the top of this stack and returns that
* object as the value of this function.
*
* @return The object at the top of this stack (the last item
* of the <tt>Vector</tt> object).
* @throws EmptyStackException if this stack is empty.
*/
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
/**
* Looks at the object at the top of this stack without removing it
* from the stack.
*
* @return the object at the top of this stack (the last item
* of the <tt>Vector</tt> object).
* @throws EmptyStackException if this stack is empty.
*/
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
/**
* Tests if this stack is empty.
*
* @return <code>true</code> if and only if this stack contains
* no items; <code>false</code> otherwise.
*/
public boolean empty() {
return size() == 0;
}
/**
* Returns the 1-based position where an object is on this stack.
* If the object <tt>o</tt> occurs as an item in this stack, this
* method returns the distance from the top of the stack of the
* occurrence nearest the top of the stack; the topmost item on the
* stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>
* method is used to compare <tt>o</tt> to the
* items in this stack.
*
* @param o the desired object.
* @return the 1-based position from the top of the stack where
* the object is located; the return value <code>-1</code>
* indicates that the object is not on the stack.
*/
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
/** use serialVersionUID from JDK 1.0.2 for interoperability */
private static final long serialVersionUID = 1224463164541339165L;
}
老师:根据jdk的源码,我们了解栈的方法及其特性,那么它有哪些具体的应用呢,哪位同学可以来说说?
小哈:逆转字符串。
小红:十进制换八进制。
小黄: 符号匹配问题。
课代表:还有逆波兰表达式,迷宫问题,最小栈问题等等。
老师:要下课了哦,我们来问问可爱的读者们想听听哪个问题?
a、逆波兰表达式
b、迷宫问题
c、最小栈问题
童鞋们可以把想了解的问题写在下面,或者扫描下面二维码关注小编后在后台留言,小编会根据大家的意见来写这个问题。
转载声明:本文转载自「java小咖秀」,号主是一枚优秀的女程序猿。
本文由“壹伴编辑器”提供技术支持
最后我为大家收集了些学习资料,如果你准备入IT坑,励志成为优秀的程序猿,那么这些资源很适合你,包括java、go、python、springcloud、elk、嵌入式 、大数据、面试资料、前端 等资源。同时我们组建了一个技术交流群,里面有很多大佬,会不定时分享技术文章,如果你想来一起学习提高,可以公众号后台回复【2】,免费邀请加技术交流群互相学习提高,会不定期分享编程IT相关资源。