数据结构-栈&队列&Deque实现比较

超、凢脫俗 2022-06-07 13:23 194阅读 0赞

*  栈
    
     *  栈的ADT
     *  进栈出栈
     *  栈的存储结构实现
 *  队列
    
     *  队列的ADT
     *  入队列出队列
     *  栈的存储结构实现
 *  Deque
    
     *  Deque的链式存储实现LinkList
        
         *  入栈
         *  出栈
     *  Deque的顺序存储实现 ArrayDeque
        
         *  添加元素
         *  删除元素
     *  BlockingDeque

# 栈 #

**栈：** 限定仅在表尾进行插入和删除操作的线性表；

*  后进先出（LIFO)。
 *  在表尾进行操作，表尾是栈顶；最新进栈的元素在栈底。

## 栈的ADT ##

![Stack\_ADT][Stack_ADT]

## 进栈&出栈 ##

![栈][1240]

## 栈的存储结构实现 ##

*  顺序栈

栈也是线性表，只是对表中元素的插入和删除位置做了限定，因此我们很容易想到利用**一维数组**实现栈的存储结构。Java中的Stack类继承自Vector，就是用数组实现。

**Stack.java**

public class Stack<E> extends Vector<E> {
        
    
        public Stack() {
        }
    
        public E push(E item) {
            addElement(item);
    
            return item;
        }
    
        public synchronized E pop() {
            E       obj;
            int     len = size();
    
            obj = peek();
            removeElementAt(len - 1);
    
            return obj;
        }
    
        public synchronized E peek() {
            int     len = size();
    
            if (len == 0)
                throw new EmptyStackException();
            return elementAt(len - 1);
        }
    
        public boolean empty() {
            return size() == 0;
        }
    
        public synchronized int search(Object o) {
            int i = lastIndexOf(o);
    
            if (i >= 0) {
                return size() - i;
            }
            return -1;
        }
    
        private static final long serialVersionUID = 1224463164541339165L;
    }

*  两栈共享存储空间
    
    如果我们有两个相同类型的栈，我们为他们各自开辟了数组空间，极有可能第一个栈已经满了，再进栈就溢出了，而另一个栈还有很多存储空间空闲。这时，我们可以充分利用顺序栈的单向延伸的特性，使用一个数组来存储两个栈，让一个栈的栈底为数组的始端，另一个栈的栈底为数组的末端，每个栈从各自的端点向中间延伸。

![share\_stack][share_stack]

**ShareStack.java**

/**
     * Created by engineer on 2017/10/22.
     */
    
    public class ShareStack<T> {
        
        private Object[] element; //存放元素的数组
    
        private int stackSize;  // 栈大小
    
        private int top1; //栈1的栈顶指针
    
        private int top2; //栈2的栈顶指针
    
    
        /**
         * 初始化栈
         * @param size
         */
        public ShareStack(int size){
            element = new Object[size];
            stackSize = size;
            top1 = -1;
            top2 = stackSize;
        }
    
    
        /**
         * 压栈
         * @param i 第几个栈
         * @param o 入栈元素
         * @return
         */
        public boolean push(int i , Object o){
    
            if(top1 == top2 - 1)
                throw new RuntimeException("栈满！");
            else if(i == 1){
                top1++;
                element[top1] = o;
            }else if(i == 2){
                top2--;
                element[top2] = o;
            }else
                throw new RuntimeException("输入错误！");
    
            return true;
        }
    
        /**
         * 出栈
         * @param i
         * @return
         */
        @SuppressWarnings("unchecked")
        public T pop(int i){
    
            if(i == 1){
                if(top1 == -1)
                    throw new RuntimeException("栈1为空");
                return (T)element[top1--];
            } else if(i == 2){
                if(top2 == stackSize)
                    throw new RuntimeException("栈2为空");
                return (T)element[top2++];
            } else
                throw new RuntimeException("输入错误！");
    
        }
    
    
        /**
         * 获取栈顶元素
         * @param i
         * @return
         */
        @SuppressWarnings("unchecked")
        public T get(int i){
    
            if(i == 1){
                if(top1 == -1)
                    throw new RuntimeException("栈1为空");
                return (T)element[top1];
            } else if(i == 2){
                if(top2 == stackSize)
                    throw new RuntimeException("栈2为空");
                return (T)element[top2];
            } else
                throw new RuntimeException("输入错误！");
        }
    
    
        /**
         * 判断栈是否为空
         * @param i
         * @return
         */
        public boolean isEmpty(int i){
    
            if(i == 1){
                if(top1 == -1)
                    return true;
                else
                    return false;
            } else if(i == 2){
                if(top2 == stackSize)
                    return true;
                else
                    return false;
            } else
                throw new RuntimeException("输入错误！");
        }
    
    }

当然，考虑到数组需要在初始化的时候限定大小，同时也要考虑扩容的问题。因此栈也可以使用链表来实现；这个后面一起讨论，这里就不展开来说了。

**栈这种数据结构，非常实用；Android中Activity的回退栈就是最好的例子，正常模式下，我们通过startActivity就是将一个Activity压入了回退栈，finish()方法就是从回退栈里弹出最顶部的Activity；当然，实际流程有很多别的操作，这里也只是大体流程；递归思想也是利用了栈这种结构。**

# 队列 #

**队列：** 只允许在一端进行插入操作、而在另一端进行删除操作的线性表。

*  先进先出(FIFO)
 *  在队尾进行插入，从队头进行删除

## 队列的ADT ##

![Queue\_ADT][Queue_ADT]

## 入队列&出队列 ##

![Deque][]

## 栈的存储结构实现 ##

*  顺序存储结构

使用数组实现队列的存储结构时，为了避免每次从队头删除元素时，移动后面的每个元素，加入了front和rear两个指针，分别指向队头和队尾；这样每次从队头删除元素时，移动front指针即可，而不必移动大量的元素，但是这样势必会造成**假溢出**的问题，存储空间得不到充分的利用，因此需要采用循环队列的方式实现了队列的顺序存储结构。

*  循环队列

假定在循环队列中，QueueSize为循环队列大小，即数组长度，则有以下结论：

1.  循环队列空的条件：front==rear;
2.  循环队列满的条件：(rear+1)%QueueSize=front;
3.  循环队列长度：(rear-front\*QueueSize)%QueueSize;

总的来说，采用顺序存储结构，还是需要考虑容量的问题。因此，在我们无法预估队列长度的情况下，需要关注链式存储结构。

*  链式存储结构

在[上文中][Link 1]我们已经说过，LinkList实现了Deque接口，因此它就是用链表实现的队列。这里简单分析一下入队push和出队pop操作的实现。

**LinkedList-add 队列入队**

public boolean add(E e) {
            linkLast(e);
            return true;
        }
        /**
         * Links e as last element.
         */
        void linkLast(E e) {
            final Node<E> l = last;
            //创建新的结点，其前驱指向last,后继为null
            final Node<E> newNode = new Node<>(l, e, null);
            //last 指针指向新的结点
            last = newNode;
            if (l == null)
                first = newNode;  //如果链表为空，frist指针指向新的结点
            else
                l.next = newNode; //链表不为空，新的结点连接到原来最后一个结点之后
            size++; //链表长度+1
            modCount++;
        }

LinkList是一个双向链表，这里first是执行第一个结点的指针，last是指向最后一个结点指针。

**LinkList-pop 队列出队**

public E pop() {
            return removeFirst();
        }
        public E removeFirst() {
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return unlinkFirst(f);
        }
        private E unlinkFirst(Node<E> f) {
            // assert f == first && f != null;
            //获取要删除结点的值
            final E element = f.item;
            //得到f的下一个结点，也就是第二个结点
            final Node<E> next = f.next;
            // f 释放
            f.item = null;
            f.next = null; // help GC
            // first 指针指向f的下个结点，
            first = next;
            // f 后面已经没有结点了
            if (next == null)
                last = null; 
            else
                next.prev = null; // 第二个结点（也就是现在的第一个结点)前驱为null,因为LinkList 是双端链表，非循环。
            size--;
            modCount++;
            return element;
        }

这里就是一个典型的单链表删除头结点的实现。至此，我们已经掌握了栈和队列这两种数据结构各自的特点；下面再来看看Java官方提供的关于栈和队列的实现。

# Deque #

这里主要说一下Deque这个类。

/**
     * A linear collection that supports element insertion and removal at
     * both ends.  The name <i>deque</i> is short for "double ended queue"
     * and is usually pronounced "deck".  Most {@code Deque}
     * implementations place no fixed limits on the number of elements
     * they may contain, but this interface supports capacity-restricted
     * deques as well as those with no fixed size limit.
     * /
    public interface Deque<E> extends Queue<E> {
        void addFirst(E var1);
    
        void addLast(E var1);
    
        boolean offerFirst(E var1);
    
        boolean offerLast(E var1);
    
        E removeFirst();
    
        E removeLast();
    
        E pollFirst();
    
        E pollLast();
    
        E getFirst();
    
        E getLast();
    
        E peekFirst();
    
        E peekLast();
    
        boolean add(E var1);
    
        boolean offer(E var1);
    
        E remove();
    
        E poll();
    
        E element();
    
        E peek();
    
        void push(E var1);
    
        E pop();
    
        ........
    }

> Deque接口是“double ended queue”的缩写(通常读作“deck”)，即双端队列，支持在线性表的两端插入和删除元素，继承Queue接口。大多数的实现对元素的数量没有限制，但这个接口既支持有容量限制的deque，也支持没有固定大小限制的。

我们知道Queue接口定义了队列的操作集合，而Deque接口又在其基础上扩展，定义了在双端进行插入删除的操作。因此，我们很可以认为，Deque接口既可以当做队列，也可以当做栈。

## Deque的链式存储实现LinkList ##

因此，回过头来，我们可以发现**LinkList以链表结构，同时实现了队列和栈**。前面已经分析了LinkList作为一个队列的操作。下面我们可以看看，他又是如何实现链式结构实现队列的。

### 入栈 ###

public void addLast(E e) {
            linkLast(e);
        }

可以看到，对于入栈操作和队列样，都是在链表最后插入元素，和队列一样使用了linkLast()方法。

### 出栈 ###

public E removeLast() {
            final Node<E> l = last;
            if (l == null)
                throw new NoSuchElementException();
            return unlinkLast(l);
        }

出栈同样是用了unlinkLast 方法，只不过出栈的元素是last。而不是队列中的first。

## Deque的顺序存储实现 ArrayDeque ##

ArrayDeque 用一个动态数组实现了栈和队列所需的所有操作。

### 添加元素 ###

public void addFirst(E e) {
            if (e == null)
                throw new NullPointerException();
            elements[head = (head - 1) & (elements.length - 1)] = e;
            if (head == tail)
                doubleCapacity();
        }
    
        public void addLast(E e) {
            if (e == null)
                throw new NullPointerException();
            elements[tail] = e;
            if ( (tail = (tail + 1) & (elements.length - 1)) == head)
                doubleCapacity();
        }
    
        private void doubleCapacity() {
            assert head == tail;
            int p = head;
            int n = elements.length;
            int r = n - p; // number of elements to the right of p
            int newCapacity = n << 1;
            if (newCapacity < 0)
                throw new IllegalStateException("Sorry, deque too big");
            Object[] a = new Object[newCapacity];
            System.arraycopy(elements, p, a, 0, r);
            System.arraycopy(elements, 0, a, r, p);
            elements = a;
            head = 0;
            tail = n;
        }

这里可以看到，无论是头部还是尾部添加新元素，当需要扩容时，会直接变化为原来的2倍。同时需要复制并移动大量的元素。

### 删除元素 ###

public E pollFirst() {
            final Object[] elements = this.elements;
            final int h = head;
            @SuppressWarnings("unchecked")
            E result = (E) elements[h];
            // Element is null if deque empty
            if (result != null) {
                elements[h] = null; // Must null out slot
                head = (h + 1) & (elements.length - 1);
            }
            return result;
        }
    
        public E pollLast() {
            final Object[] elements = this.elements;
            final int t = (tail - 1) & (elements.length - 1);
            @SuppressWarnings("unchecked")
            E result = (E) elements[t];
            if (result != null) {
                elements[t] = null;
                tail = t;
            }
            return result;
        }

从头部和尾部删除（获取）元素，就比较方便了，修改head和tail位置即可。head是当前数组中第一个元素的位置，tail是数组中第一个空的位置。

## BlockingDeque ##

/**
     * A {@link Deque} that additionally supports blocking operations that wait
     * for the deque to become non-empty when retrieving an element, and wait for
     * space to become available in the deque when storing an element.
     * /
    
    public interface BlockingDeque<E> extends BlockingQueue<E>, Deque<E> {
    }

关于Deque最后一点，BlockingDeque 在Deque 基础上又实现了**阻塞**的功能，当栈或队列为空时，不允许出栈或出队列，会保持阻塞，直到有可出栈元素出现；同理，队列满时，不允许入队，除非有元素出栈腾出了空间。常用的具体实现类是LinkedBlockingDeque，使用链式结构实现了他的阻塞功能。Android中大家非常熟悉的AsyncTask 内部的线程池队列，就是使用LinkedBlockingDeque实现，长度为128，保证了AsyncTask的串行执行。

**这里比较一下可以发现，对于栈和队列这两种特殊的数据结构，由于获取（查找）元素的位置已经被限定，因此采用顺序存储结构并没有非常大的优势，反而是在添加元素由于数组容量的问题还会带来额外的消耗；因此，在无法预先知道数据容量的情况下，使用链式结构实现栈和队列应该是更好的选择。**

--------------------

好了，栈和队列就先到这里了。

[Stack_ADT]: /images/20220607/19d0d4b166cf412b9ac30f1750bda03f.png
[1240]: /images/20220607/b536dc69659548acaf38bc046e53fcb0.png
[share_stack]: /images/20220607/e400cc1165244506b4296205df00be5b.png
[Queue_ADT]: /images/20220607/521c76aa06f4458dad99bfb6bf41258f.png
[Deque]: /images/20220607/0d2d88247b4b4698b352f1ca7c8aaedc.png
[Link 1]: http://www.jianshu.com/p/3d47ad99a18e