算法：栈和队列-理论

营琪

发布于 2019-11-04 16:51:24

4610

发布于 2019-11-04 16:51:24

文章被收录于专栏：营琪的小记录

栈，stack

也可以翻译成堆栈，但是不能翻译成堆(heap)。

栈

百度百科关于栈的介绍是

它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

我们可以吧栈简单的想象成一堆碟子，做饭的时候，每次都从最上面的拿起（出栈），洗干净后又放回最上面（进栈）

Java的栈是怎么实现！

先看看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的实际是通过数组实现的。关于数组的介绍：算法：数组和链表-理论。

队列，Queue

队列在百度百科的介绍是：

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

我们也可以把队列想象成一条排队结账的队伍，先到的再前面，后面到的排在后面。

我们再考虑一下上面关于栈，一叠叠的碟子，每用一个碟子，依此从上到下，洗完再依此一个个叠好，这样是否合理。

其实，这样是不合理的，仔细想一下，最下面的碟子，那不是一直都用不到？一直不洗，一直不干净了。

其实，碟子的使用顺序更应该是队列，每次都是每次拿，从头到尾；每次放，从尾到头。

Java的队列是怎么实现！

先看看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标准，再根据需要选用实现类。实际实现的方法各种各样。队列种的容器有数组的、链表的等等。

下面给一个数据结构时间复杂度和空间复杂度的表，这就不说咯。。