也可以翻译成堆栈,但是不能翻译成堆(heap)。
栈
百度百科关于栈的介绍是
它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
我们可以吧栈简单的想象成一堆碟子,做饭的时候,每次都从最上面的拿起(出栈),洗干净后又放回最上面(进栈)
先看看stack的继承结构
栈继承vector类,vector类依此继承AvstractLIst、AbstractCollection(抽象集合类)实现Collection(集合)、Iterable(迭代器)接口。设计模式:适配器模式。
Java实现了栈(Stack类)的什么方法呢?
我们还是找一个方法看看,Java栈是怎么实现。那就push方法吧。
java.util.Stack
public E push(E item) {
addElement(item);
return item;
}
package java.util.Vector;
...
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);//数组下标处理(判断更新等)
elementData[elementCount++] = obj; //数组
}
protected Object[] elementData;
protected int elementCount;
我们通过一步步的阅读push方法的源码,我们发现Java中Stack的实际是通过数组实现的。关于数组的介绍:算法:数组和链表-理论。
队列在百度百科的介绍是:
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
我们也可以把队列想象成一条排队结账的队伍,先到的再前面,后面到的排在后面。
我们再考虑一下上面关于栈,一叠叠的碟子,每用一个碟子,依此从上到下,洗完再依此一个个叠好,这样是否合理。
其实,这样是不合理的,仔细想一下,最下面的碟子,那不是一直都用不到?一直不洗,一直不干净了。
其实,碟子的使用顺序更应该是队列,每次都是每次拿,从头到尾;每次放,从尾到头。
先看看Queue的继承结构,Java中的Queue是一个接口,继承结构比较简单,向上继承Collection集合接口
我们可以看看它的实现类或者抽象类
我们通过ArrayBlockintQueue实现类,探究一下Java中的队列是怎么实现的。通过添加方法offer探究一下。
package java.util.concurrent.ArrayBlockingQueue;
public boolean offer(E e) {
checkNotNull(e); //检查是否为空
final ReentrantLock lock = this.lock; //可重用锁
lock.lock();
try {
if (count == items.length) //检查大小
return false;
else {
enqueue(e); //实际添加方法
return true;
}
} finally {
lock.unlock();
}
}
final Object[] items;
private void enqueue(E x) {
// assert lock.getHoldCount() == 1;
// assert items[putIndex] == null;
final Object[] items = this.items;
items[putIndex] = x; //实际添加步骤
if (++putIndex == items.length)
putIndex = 0;
count++;
notEmpty.signal();
}
好像没怎么明白过意思来,Queue接口,实现一些必要规则,实际的队列有很多种,那么实际的添加方法,存储的容器又根据类的特性进行设计。
我们再看看Queue的实现类LinkedList类。也是实现了Queue接口的。也看看offer接口。
package java.util.LinkedList;
...
public boolean offer(E e) {
return add(e);
}
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) { //请查看链表文章
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
可以确定上面这个判断了,为了更方便的使用队列,设计一个Queue标准,再根据需要选用实现类。实际实现的方法各种各样。队列种的容器 有 数组的、链表的等等。
下面给一个数据结构时间复杂度和空间复杂度的表,这就不说咯。。