专栏首页JavaJourney数据结构与算法(四)| 队列、栈与Java集合

数据结构与算法(四)| 队列、栈与Java集合

队列和栈的结构非常经典,在面试中会经常出现他们的变种题。

比如,实现图的宽度优先遍历,但是要求用栈实现;实现图的深度优先遍历,但是要求用队列实现。

这个题比较阴的地方就是图的宽度优先遍历通常是用队列来实现的,而深度遍历使用栈实现,所以,这里需要我们做一个转换:

先用队列来实现栈,然后用这个队列实现的栈实现宽度优先遍历,从而达到用栈实现图的宽度优先遍历的目的;

对于深度优先遍历,先用栈来实现队列,然后用这个栈实现的队列实现深度优先遍历。

这篇文章不是讨论这种结构的,主要实现以下两种算法:

  • 用栈结构实现队列结构
  • 用队列结构实现栈结构

用栈实现队列

要想实现队列,我们要考虑的是怎样达到数据的先进先出

而栈是先进后出的结构,于是我们可以用两个栈来实现:push栈和pop栈。

push栈弹出依次压入到pop栈

对于我们要实现的特殊队列,入队的时候压入数据到push栈,同时观察判断pop栈是否为空。

插入一个3,add(3),此时pop栈为空,需要将push栈中的数弹出压入到pop栈,直到push栈为空:

add(3)

插入一个2,add(2),此时pop栈不为空,无需弹出push栈和压入pop栈:

add(2)

同理,依次add(5)和add(7):

依次add(5)和add(7))

此时,我要从队列中取出数据,poll,弹出pop栈,此时判断一下pop栈是否为空,若为空,则需要将push栈数据全部倒出压入到pop栈:

队列poll

继续从队列取数:

队列poll

从上述add和poll的过程我们可以得出一个结论:

无论队列add还是poll都要看一下pop栈是否为空,如果pop栈为空了,则需要弹出push栈的数据压入到pop栈,直到push栈为空。

即:

  • push栈数倒入到pop栈时要一次性倒完
  • 当pop栈不为空时,不需要压入push栈的数据

这样就能保证先进先出了。

因此我可以抽象出一个弹出push栈数据压入pop栈的方法:

public void pushToPop() {
    if (popStack.isEmpty()) {
        while (!pushStack.isEmpty()) {
            popStack.push(pushStack.pop());
        }
    }
}

用栈实现队列的完整代码:

public class MyQueueWithStack {
    private Stack<Integer> pushStack;
    private Stack<Integer> popStack;
    
    public MyQueueWithStack() {
        this.pushStack = new Stack<>();
        this.popStack = new Stack<>();
    }
    
    public void pushToPop() {
        if (popStack.isEmpty()) {
            while (!pushStack.isEmpty()) {
                popStack.push(pushStack.pop());
            }
        }
    }
    
    public void add(int value) {
        pushStack.push(value);
        pushToPop();
    }
    
    public int poll() {
        if (popStack.isEmpty() && pushStack.isEmpty()) {
            throw new RuntimeException("队列空了!");
        }
        pushToPop();
        return popStack.pop();
    }
}

用队列实现栈

有了用两个栈实现队列的经验,我们可以再来试一下如何用两个队列实现栈。

终极目的是实现数据的先进先出,也就是先添加的数据,在取数的时候先取出。

下面先用图来演示一遍过程:

用两个队列实现栈的后进先出结构

上图演示的数据入栈出栈过程:

入栈:1,2,出栈:2

入栈:3,4,5,出栈:5

入栈:无,出栈:4

...

所以,这一过程实现了栈的后进先出达到了用队列实现栈的目的(用两个队列来回倒数据)。

要点:定义两个队列,实现的这种栈在push时往非空的那个队列(如果都为空,则选择其中一个)插入数据,pop时将非空的队列数据取出并依次插入到原来空的那个队列,只留下最后一个元素,将这个元素取出返回,这样原来非空的就变成了空队列了。---每次操作无论push还是pop均有一个队列是空的。

把上面我分析的思路翻译成代码就是这样的:

public class MyStackWithQueue<T> {
    private Queue<T> queue;
    private Queue<T> help;
    
    public MyStackWithQueue() {
        this.queue = new LinkedList<>();
        this.help = new LinkedList<>();
    }
    
    public void push(T value) {
        if (queue.isEmpty() && help.isEmpty()) {
            queue.add(value);
        }
        if (!queue.isEmpty()) {
            queue.add(value);
        }
        if (!help.isEmpty()) {
            help.add(value);
        }
    }

    public T pop() {
        Queue<T> temp = new LinkedList<>();
        if (!queue.isEmpty()) {
            temp = queue;
            while (queue.size() > 1) {
                help.add(queue.poll());
            }
        } else if (!help.isEmpty()) {
            temp = help;
            while (help.size() > 1) {
                queue.add(help.poll());
            }
        }
        return temp.poll();
    }
}

延伸:Java中的List和Queue

Java集合框架图(无Map)

List集合

List集合元素有明确的 上一个下一个 元素,也存在明确的第一个和最后一个元素。

List集合最常用的是 ArrayListLinkedList 两个集合类。

ArrayList

ArrayList的容量可以改变,非线程安全集合。其内部实现用数组进行存储,集合扩容时会创建一个更大的数组控件,把原有数据复制到新数组中。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access
    
    //......
}

ArrayList支持对元素的快速随机访问,但是插入和删除的速度较慢,因为插入和删除的过程需要移动元素。

LinkedList

LinkedList本质上是一个双向链表。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;
    
    //...
}

它和ArrayList很明显的区别就是,LinkedList的插入和删除速度快,而随机访问速度则很慢。

另外,LinkedList还实现了 Deque 接口(double-ended queue,双端队列),Deque 同时具有队列和栈的性质,因为它可以先进先出,也可以先进后出。

LinkedList将零散的内存单元通过附加引用(其内部定义了指向前一个和后一个元素的first和last指针)的方式关联起来,形成按链路顺序查找的线性结构,内存利用率较高。

Queue集合

前面几篇文章一直在探讨队列、栈这些数据结构,队列的**先进先出(FIFO)**应该深入我们的脑海中---队列只允许从一端进行取数,在另一端进行插入数据。

从棣属于juc包下的 BlockingQueue 出现以来,队列就应用于各种高并发场景中,鉴于其先进先出的特性记忆阻塞操作的特点,它经常被用作数据缓冲区

BlockingQueue

小结

本文介绍了栈和队列的互转,这两个算法技巧可以帮助解决一些奇怪的算法题~

Java中常用的List和Queue集合多和队列和栈数据结构有关系,建议手绘一张集合框架图,时不时的想一下他们的实现,这将对我们很有帮助。

文章分享自微信公众号:
行百里er

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

作者:行百里er
原始发表时间:2021-06-21
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • JS数据结构与算法 — 栈与队列

    栈与队列分别是两种数据结构,不同语言对于栈和队列有着不同的声明 栈数据结构的特点是 FILO(first in last out) 即先进后出,队列则是 FIF...

    用户9914333
  • 数据结构与算法(三)栈与队列

    一、栈   栈(stack)是限定仅在表尾进行插入和删除操作的线性表,我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数...

    matinal
  • 数据结构与算法(四)栈

    栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作...

    老沙
  • 集合中篇—栈与队列

    Java的集合实现了栈与队列,我们直接调用就可以实现功能,可是平时就见过Queue、Stack、Deque这些字眼,完全不知道怎么回事,下面就来梳理一下他们的关...

    晚上没宵夜
  • 数据结构:栈与队列

    工程代码 Github: Data_Structures_C_Implemention -- Stack & Queue

    半纸渊
  • 数据结构与算法(六)-背包、栈和队列

      前言:许多基础数据类型都和对象的集合有关。具体来说,数据类型的值就是一组对象的集合,所有操作都是关于添加、删除或是访问集合中的对象。而且有很多高级数据结构都...

  • 浅谈集合数据结构之栈与队列的区别

    吾爱乐享
  • 数据结构(三):栈与队列

    3.1❶若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度(注意:两侧铁道均为单向行驶道),则请回答: ? (1) 如果进站的车厢序列为123,则可能...

    云时之间
  • 数据结构(二)| 队列与栈

    数据结构(一)| 链表 一节中,我们已经知道,双向链表由数据域和节点指针组成,有指向前一个节点的指针(last)和指向后一个节点的指针(next),头结点的la...

    行百里er
  • Java数据结构与算法解析(三)——队列与背包

    关联文章: Java数据结构与算法解析(一)——表 Java数据结构与算法解析(二)——栈

    老马的编程之旅
  • Java双向队列Deque栈与队列

    Java中实际上提供了java.util.Stack来实现栈结构,但官方目前已不推荐使用,而是使用java.util.Deque双端队列来实现队列与栈的各种需求...

    全栈程序员站长
  • Java数据结构与算法解析(二)——栈

    栈是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫做栈顶。对栈的基本操作有push(进栈)和pop(出栈),对空栈进行push和pop,一般被认为...

    老马的编程之旅
  • Java集合与数据结构——优先级队列(堆)

      我们在说 大小根堆 时,只说了 根节点比孩子节点大,没有说 左右孩子节点谁比谁大、谁比谁小.

    RAIN7
  • 数据结构与算法——队列

    队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线...

    C you again 的博客
  • 数据结构与算法-队列

    cwl_java
  • 数据结构之栈与队列(优先队列/堆)

    栈与队列是两种重要的特殊线性表,从结构上讲,两者都是线性表,但从操作上讲,两者支持的基本操作却只是线性表操作的子集,是操作受限制的线性表。栈与队列两者最大的区别...

    我是东东东
  • (转)Java--栈与队列

    Java中栈与队列相比集合来说不是很常用的数据结构,因此经常被忽略.个人觉得还是有必要掌握下,以备不时之需. Java中实际上提供了java.util.Stac...

    屈定
  • Java数据结构和算法(四)——栈

      前面我们讲解了数组,数组更多的是用来进行数据的存储,纯粹用来存储数据的数据结构,我们期望的是插入、删除和查找性能都比较好。对于无序数组,插入快,但是删除和查...

    IT可乐

扫码关注腾讯云开发者

领取腾讯云代金券