大厂之路的第四篇 栈和队列(Stack and Queue)
前面三篇我们都在讲线性表，今天我们介绍两种特殊的线性表来做为线性表专题的结尾。----栈和队列
先看一下这两者的定义(来源百度百科):
栈: 栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
上学的时候就特别不爱背定义，我想用张图来描述可能会更清晰一些:
栈.png
队列：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
同样，我们也用一张图来解释队列的特点：
队列.png
概念讲完了，我们就从java源码的角度来进一步了解它们。
首先，我们看栈，即Stack。
我们先看一下jdk中对Stack的注释
* The <code>Stack</code> class represents a last-in-first-out
* (LIFO) stack of objects. It extends class <tt>Vector</tt> with five
* operations that allow a vector to be treated as a stack. The usual
* <tt>push</tt> and <tt>pop</tt> operations are provided, as well as a
* method to <tt>peek</tt> at the top item on the stack, a method to test
* for whether the stack is <tt>empty</tt>, and a method to <tt>search</tt>
* the stack for an item and discover how far it is from the top.
今天我打算翻译一下这段话，又学编程又学英语，还不错！！
Stack这个类代表着一堆后进先出的对象集合。Stack继承自Vector，如果一个Vector对象有以下五种行为，那么它就可以被看作是Stack:
- 含有
push和pop这两个函数- 提供
peek方法以获取栈顶部的item- 提供
empty方法以校验Stack是否为空- 提供
search方法以在栈中寻找一个item以及判断它距离栈顶有多远
之前我们有提到过Vector，它跟ArrayList是很类似的，最根本的区别在于它是线程安全的。既然Stack继承自Vector，那么首先它也是线程安全的。
接着又提到了Stack的特殊之处在于它所特有的五个函数:
push,pop,peek,empty, search。
那么，我们就来分别看一下这五个函数：
1.push函数
public E push(E item) {
addElement(item);
return item;
}
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
push函数特别的简单:
1.判断是否需要扩容。因为Vector和ArrayList一样，底层都是动态数组，所以第一步需要判断是否需要对数组进行扩容。
2.将要添加的元素添加至线性表的尾部。由于我们之前分析过ArrayList的增删改查，Vector其实也差不多，所以我们就不再解释了。
2.peek函数
由于在pop函数中有用到peek，所以我们先看peek函数
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
public synchronized E elementAt(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
}
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
不难看出，peek函数其实就是取线性表的队尾元素，并将其返回。
3.pop函数
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
public synchronized void removeElementAt(int index) {
modCount++;
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
int j = elementCount - index - 1;
if (j > 0) {
System.arraycopy(elementData, index + 1, elementData, index, j);
}
elementCount--;
elementData[elementCount] = null; /* to let gc do its work */
}
同样很简单，先拿到队尾的元素作为返回值，再将队尾元素置为null，同时改变线性表的长度。
4.empty函数
public boolean empty() {
return size() == 0;
}
这个就更简单了，判断size是否为0。
5.search函数
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
}
return -1;
}
public synchronized int lastIndexOf(Object o) {
return lastIndexOf(o, elementCount-1);
}
public synchronized int lastIndexOf(Object o, int index) {
if (index >= elementCount)
throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
if (o == null) {
for (int i = index; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = index; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
search函数一样也很简单，就是从队尾开始遍历查找线性表中是否包含指定元素，并将其距离栈顶的距离返回。
栈看完了，接着看队列，即Queue。
通过Queue的源码我们可以看到，它是一个接口。那所有继承他的类都必须实现以下几个方法(特有的方法):
element,offer,peek,poll,remove。
由于我们前面分析过LinkedList的源码，而又由于LinkedList其实是实现了Deque也就是双端队列，而Deque又是实现自Queue，所以在此我们就不再展开了。
今天，栈和队列我们就看到这里了。下一篇我们看另一个特别重要的集合，hash表。
网友评论