Java中的Stack和Queue_java queue stack

---

栈和队列

栈和队列是最经常使用的数据结构之一。栈是一种先进后出，后进先出的线性表，队列是一种先进先出，后进后出的线性表。本篇文章主要讲述在Java中如何使用这两种数据结构。

---

一、Java中的Stack

1.Stack类的使用

Stack的声明如下，可以看到Stack继承了Vector，因此Stack可以使用Vector中的方法，如size() 等。

public
class Stack<E> extends Vector<E>
1
2

除此之外，Stack类定义了五个方法，作用如下

示例：

	Stack<Integer> stack = new Stack<>();
	//1、2、3按顺序入栈
	stack.push(1);
	stack.push(2);
	stack.push(3);
	int a = stack.peek(); //返回栈顶元素3
	int b = stack.pop(); //返回栈顶元素3，并将3出栈，此时栈中只剩2和1
	int size = stack.size(); //获取栈的当前大小
	boolean isEmpty = stack.empty(); //判断栈是否为空
	int index = stack.search(1);  //查找栈中是否有1，从栈顶开始计数，栈顶元素索引为1。此时从栈顶到栈底分别为2，1，该方法将返回2
1
2
3
4
5
6
7
8
9
10

2.Stack类的分析

先说说Stack的特点，上面说过Stack是继承自Vector的，而Vector是线程安全的，所以Stack也是线程安全的。下面分析Stack的三个关键方法push()、peek()和pop()。

public E push(E item) {
	addElement(item);
	return item;
}
1
2
3
4

public synchronized E peek() {
	int len = size();
	if (len == 0)
            throw new EmptyStackException();
	return elementAt(len - 1);
}
1
2
3
4
5
6

public synchronized E pop() {
	E obj;
	int len = size();
	obj = peek();
    removeElementAt(len - 1);
	return obj;
}
1
2
3
4
5
6
7

从源码中我们可以看到上述三个方法的具体实现都是通过调用父类Vector里的方法实现的。为了实现线程安全，peek()和pop()加上了同步锁，push()没有添加是因为只调用了Vector中的addElement(E item)方法，这个方法是加锁的。

然而正因为Stack继承自Vector，Stack类已经不被官方推荐使用！！

基于 Vector 实现的栈 Stack。底层实际上还是数组，所以还是存在需要扩容。Vector 是由数组实现的集合类，它包含了大量集合处理的方法。而 Stack 之所以继承 Vector，是为了复用 Vector 中的方法，来实现进栈（push）、出栈(pop)等操作。这里就是 Stack 设计不好的地方，既然只是为了实现栈，不用链表来单独实现，而是为了复用简单的方法而迫使它继承 Vector，Stack 和 Vector 本来是毫无关系的。这使得 Stack 在基于数组实现上效率受影响，另外因为继承 Vector 类，Stack 可以复用 Vector 大量方法，这使得 Stack 在设计上不严谨。

官方推荐使用LinkedList来构建栈

二、Java中的Queue

1.Queue的使用

与Stack不同，Java里的Queue不是一个类，而是一个接口，它的声明为

public interface Queue<E> extends Collection<E>
1

其中声明了六个主要方法，具体如下

LinkedList实现了Queue接口，可以通过LinkedList来构建栈

2.Queue的分析

从上面的表我们发现，Queue中的六个方法，有三对方法的作用非常相似，分别为add和offer，element和peek，remove和poll。

2.1 add 和offer 区别:

看源码中add()和offer()的声明及注释

	/**
     * Inserts the specified element into this queue if it is possible to do so
     * immediately without violating capacity restrictions, returning
     * {@code true} upon success and throwing an {@code IllegalStateException}
     * if no space is currently available.
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Collection#add})
     * @throws IllegalStateException if the element cannot be added at this
     *         time due to capacity restrictions
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this queue
     * @throws NullPointerException if the specified element is null and
     *         this queue does not permit null elements
     * @throws IllegalArgumentException if some property of this element
     *         prevents it from being added to this queue
     */
    boolean add(E e);

    /**
     * Inserts the specified element into this queue if it is possible to do
     * so immediately without violating capacity restrictions.
     * When using a capacity-restricted queue, this method is generally
     * preferable to {@link #add}, which can fail to insert an element only
     * by throwing an exception.
     *
     * @param e the element to add
     * @return {@code true} if the element was added to this queue, else
     *         {@code false}
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this queue
     * @throws NullPointerException if the specified element is null and
     *         this queue does not permit null elements
     * @throws IllegalArgumentException if some property of this element
     *         prevents it from being added to this queue
     */
    boolean offer(E e);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

通过注释我们发现，add()和offer()向队列尾部中添加一个元素。他们的不同在于：当使用有容量限制的队列（如ArrayBlockingQueue）时，若队列已满，调用add会抛出一个IllegalStateException，而调用offer不会抛出异常，只会返回false。

2.2 element 和 peek 区别：

	/**
     * Retrieves, but does not remove, the head of this queue.  This method
     * differs from {@link #peek peek} only in that it throws an exception
     * if this queue is empty.
     *
     * @return the head of this queue
     * @throws NoSuchElementException if this queue is empty
     */
    E element();

    /**
     * Retrieves, but does not remove, the head of this queue,
     * or returns {@code null} if this queue is empty.
     *
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    E peek();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

与add()和offer()类似，element() 和 peek()的区别在于：当队列为空时，调用element() 抛出一个NoSuchElementException 异常，而 peek() 返回 null。

2.3 remove 和 poll 区别：

	/**
     * Retrieves and removes the head of this queue.  This method differs
     * from {@link #poll() poll()} only in that it throws an exception if
     * this queue is empty.
     *
     * @return the head of this queue
     * @throws NoSuchElementException if this queue is empty
     */
    E remove();

    /**
     * Retrieves and removes the head of this queue,
     * or returns {@code null} if this queue is empty.
     *
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    E poll();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

remove() 和 poll() 方法都是从队列中删除第一个元素。如果队列元素为空，调用remove() 的行为与 Collection 接口相似，会抛出NoSuchElementException 异常，而是新的 poll() 方法在用空集合调用时只是返回 null。

add、element、remove为一组，他们均在出错时抛出异常；offer、peek、poll为一组，他们在出错时返回特定的值

总结

以上内容分析了Java中的Stack和Queue，最关键的区别是Stack是一个类而Queue是一个接口。他们的共同点之一是都实现了Collection接口。他们都能通过LinkedList来实现，关于LinkedList将在另一篇文章中介绍。