3-玩转数据结构-栈和队列

我们会介绍两个全新的线性数据结构,栈与队列。

栈Stack

栈也是一种线性结构;相比数组,栈对应的操作是数组的子集;只能从一端添加元素,也只能从一端取出元素(这一端称之为栈顶)

添加元素和取出元素都只能从栈顶位置开始存取。栈是一种后进先出的数据结构。Last ln First Out (LIFO); 在计算机的世界里,栈拥有着不可思议的作用

栈的应用: 无处不在的Undo操作(撤销)

  • 比如你打字: 沉迷学习无法自拔,然后将无法打成不法。

撤销就是将这个不法出栈,然后将后续的正确字都入栈。

  • 程序调用的系统栈(对于理解递归有作用)

函数A运行到一半,调用函数B; B运行到一半,调用函数C;

A2指函数A运行到了第二行,B2指函数B运行到了第二行。当函数C顺序执行完毕之后,该执行哪一个函数呢,拿出栈顶B2继续执行。 当B函数执行完毕之后,拿出栈顶A2,执行A函数,执行完之后,发现栈为空,整个程序执行完毕。

子过程,子逻辑的调用,对于理解递归有作用。

栈的实现

Stack<E>
void push(E e);      // 向栈中加入元素
E pop();           // 弹出栈顶元素
E peek( );         // 查看栈顶元素
int getSize();     // 获取栈中元素个数
boolean isEmpty(); // 判断栈是否为空

从用户的角度看,支持这些操作就好。具体底层实现,用户不关心,实际底层有多种实现方式。

    Interface Stack<E> implement ArrayStack<E>
    int getSize();
    boolean isEmpty();
    void push(E e);
    E pop();
    E peek();

将我们栈中的常用方法作为一个接口,然后让我们上次实现的动态数组来实现这个接口。

    /**
     * 获取数组最后一个元素(方便我们的栈实现)
     * 
     * @return
     */
    public E getLast(){
        return  get(size-1);
    }

    /**
     * 获取数组第一个元素
     * 
     * @return
     */
    public E getFirst(){
        return get(0);
    }

为Array添加两个方法方便我们的栈实现。

package cn.mtianyan;

public class ArrayStack<E> implements Stack<E> {
    Array<E> array;
    public ArrayStack(int capacity){
        array = new Array<>(capacity);
    }

    public ArrayStack() {
        array = new Array<>();
    }

    public int getCapacity(){
        return array.getCapacity();
    }


    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }


    @Override
    public void push(E e) {
        array.addLast(e);
    }

    @Override
    public E pop() {
        return  array.removeLast();
    }

    @Override
    public E peek() {
        return array.getLast();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Stack :");
        res.append("[ ");
        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != array.getSize()-1){
                res.append(", ");
            }
        }
        res.append("] top");
        return  res.toString();
    }

}

栈的设计中,用户只关注栈顶元素存取和栈长度。因此不需要提供其他对外方法。

package cn.mtianyan;

public class ArrayStackTest {


    public static void main(String[] args) {
        ArrayStack<Integer> arrayStack = new ArrayStack<>();
        for (int i = 0; i < 5; i++) {
            arrayStack.push(i);
            System.out.println(arrayStack);
        }
        arrayStack.pop();
        System.out.println(arrayStack);
    }

}

运行结果:

栈的复杂度分析

ArrayStack<E>
void push(E e)      // O(1) 均摊
E pop()             // O(1) 均摊
E peek()            // O(1)
int getSize()       // O(1)
boolean isEmpty()   // O(1)

这里的push和pop操作在最后面进行,有可能触发resize,但均摊来算是O(1)的。

栈的应用

undo操作-编辑器; 系统调用栈-操作系统;

应用: 括号匹配 - 编译器 LeetCode 问题(leetcode-cn.com) 美版的功能更丰富

https://leetcode-cn.com/problems/valid-parentheses/description/

许多公司真实的面试题。

栈顶元素反映了在嵌套的层次关系中,最近的需要匹配的元素

只要是左侧的括号,就压入栈内。

如上图所示,只要是左侧就压入栈。面对字符时右括号,开始查看当前栈顶元素是否可以和该右括号匹配,匹配则出栈。

直到所有字符扫描完毕,栈为空则匹配成功。

失败的例子:

左侧括号全部入栈后,遇到的右括号无法和栈顶匹配,匹配失败。Leetcode会生成相应的语言的答题模板

class Solution {
    public boolean isValid(String s) {
        
    }
}

这一小节我们使用import java.util.Stack;,但实际我们自己编写的Stack和java中的这个接口是一致的,下节课教大家在LeetCode用我们自己编写的Stack。

package cn.mtianyan;

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i); // String中的第i个字符
            if (c == '(' || c == '[' || c == '{'){
                stack.push(c);
            }else{
                if (stack.isEmpty())
                    return false;
                char topChar = stack.pop();
                if (c ==')' && topChar !='(')
                    return false;
                if (c ==']' && topChar !='[')
                    return false;
                if (c=='}' && topChar != '{')
                    return false;
            }
        }
        return stack.isEmpty();
    }
}

注意topChar时的pop操作,完成了取出栈顶元素和保存栈顶元素两个操作。

附加Python版本实现:

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        for c in s:
            if(c=='(' or c=='[' or c=='{'):
                stack.append(c)
            else:
                if(len(stack) == 0):
                    return False
                top_c = stack.pop()
                if (c ==')' and top_c != '('):
                    return False
                if (c ==']' and top_c !='['):
                    return False
                if (c=='}' and top_c != '{'):
                    return False
        return len(stack)==0;
if __name__ == '__main__':
    s = Solution()
    print(s.isValid("(]"))

Python版实现要注意list没有push方法,应该使用append方法代替; 注意栈为空(没有待匹配字符直接return False) Python中False是大写,python中获取长度使用len()方法。pop方法还是一样的。

关于LeetCode的更多说明

本地测试,Java版直接添加main函数

public static void main(String[] args) {
        System.out.println(new Solution().isValid("()[]{}"));
        System.out.println(new Solution().isValid("([)]"));
    }

运行结果:

提交时即使添加了main函数也不会报错的。但是请注意不要将自己Package的语句也加入,会报错。

方法必须是public的,因为它会在类外创建自己的Main使用你的方法。

如果我们本地有自己的类接口等,我们可以通过内部类(可以使public也可以是private)来在LeetCode上使用。

class Stack(object):
    """栈"""

    def __init__(self):
        self.items = []

    def is_empty(self):
        """判断是否为空"""
        return self.items == []

    def push(self, item):
        """加入元素"""
        self.items.append(item)

    def pop(self):
        """弹出栈顶元素"""
        return self.items.pop()

    def peek(self):
        """返回栈顶元素"""
        return self.items[len(self.items) - 1]

    def size(self):
        """返回栈的大小"""
        return len(self.items)


class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = Stack()
        for c in s:
            if c == '(' or c == '[' or c == '{':
                stack.push(c)
            else:
                if stack.size() == 0:
                    return False
                top_c = stack.pop()
                if c == ')' and top_c != '(':
                    return False
                if c == ']' and top_c != '[':
                    return False
                if c == '}' and top_c != '{':
                    return False
        return stack.size() == 0


if __name__ == '__main__':
    s = Solution()
    print(s.isValid("(]"))
    print(s.isValid("()"))

Python中不能使用内部类,而是应该该类与class Solution并列。这种提交方式,既可以检验我们的解题,对于我们自己编写的Array Stack也进行检验,值得推荐。

可以看到LeetCode的相关话题。点击可以找到栈相关的题目,可以进行专项练习。

学习方法的疑问:

强烈推荐bobo老师的学习方法指导: https://zhuanlan.zhihu.com/p/35878826

一个课程知识学好几遍,而不是硬扛着一遍强行看完。不懂的先留着,比如我就有一个自己的胡思乱想笔记,记录自己每个阶段遗留问题,日后这些遗留问题在自己学到更深度的知识的时候自然会解决。

这39个问题看看自己感兴趣的,大概了解一下栈能解决什么问题。不是非得把问题做完,才能开始下一节。

不要完美主义。掌握好“度”;学习本着自己的目标去。

对于这个课程,大家的首要目标,是了解各个数据结构的底层实现原理,以及应用。学习到后面,再回头来看。

队列 Queue

队列也是一种线性数据结构; 相比数组,队列对应的操作是数组的子集

只能从一端 (队尾) 添加元素,只能从另一端 (队首) 取出元素

就像一个银行的柜台,从队尾进入元素,在队首有柜台处理,处理了就可以出队。

出队从队首出队,1然后2。

队列是一种先进先出的数据结构(先到先得); First In First Out (FIFO)

Queue<E>
void enqueue(E e); // 入队
E dequeue();       // 出队
E getFront();      // 获取队首元素
int getSize();      // 获取队列元素多少
boolean isEmpty();  // 是否为空
Interface Queue<E> implement ArrayQueue<E>
void enqueue(E e); // 入队
E dequeue();       // 出队
E getFront();      // 获取队首元素
int getSize();      // 获取队列元素多少
boolean isEmpty();  // 是否为空
package cn.mtianyan;

public interface Queue<E> {
    void enqueue(E e); // 入队
    E dequeue();       // 出队
    E getFront();      // 获取队首元素
    int getSize();      // 获取队列元素多少
    boolean isEmpty();  // 是否为空
}
package cn.mtianyan;

public class ArrayQueue<E> implements Queue<E> {
    private Array<E> array;

    public ArrayQueue(int capacity) {
        this.array = new Array<>(capacity);
    }

    public ArrayQueue() {
        this.array = new Array<>();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }

    @Override
    public E dequeue() {
        return array.removeFirst();
    }

    /**
     * 获取队首元素
     *
     * @return
     */
    @Override
    public E getFront() {
        return array.getFirst();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("Queue :");
        res.append("front [ ");
        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != array.getSize()-1){
                res.append(", ");
            }
        }
        res.append("] tail");
        return  res.toString();
    }

    public static void main(String[] args) {
        ArrayQueue<Integer> queue = new ArrayQueue<>();
        for (int i = 0; i < 5; i++) {
            queue.enqueue(i);
            System.out.println(queue);
        }
        queue.dequeue();
        System.out.println(queue);
    }
}

运行结果:

数组队列的复杂度分析

ArrayQueue<E>

void enqueue(E e); // 入队 O(1) 均摊
E dequeue();       // 出队 O(n)
E getFront();      // 获取队首元素 O(1)
int getSize();      // 获取队列元素多少 O(1)
boolean isEmpty();  // 是否为空 O(1)

这里入队是从队尾,有可能触发resize,因此均摊下来是O(1)。出队是在队首,数组实现每次都要挪动所有元素,O(n)。

获取队首元素,get(0),O(1)。剩下两个也是常数级别完成,O(1); 使用循环队列实现即可。

可不可以在把a删除之后,不挪动bcde呢?

剩下的元素仍然保持着先后顺序,我们可以记录一下当前的队首是谁?

(front++)就可以了,tail位置不用变。

front == tail 队列为空。只要队列不为空,front 就不可能等于 tail

入队时不需要考虑front,只需要tail++;出队时,tail不变,front++就可以了。

当tail指向队尾末,再++就会移到越界区域时,前面还有空余空间,把元素填充到前面去。

把数组看成一个环,容量是8,索引0-7。当指向7之后的位置,就变成0了,tail = (7+1)%8 即可。

此时如果再放入元素,tail往后移,front = tail 了,但此时队列为满。

front == tail 队列为空; tail+ 1==front 队列满; 此时就可以扩容了。准确的是(tail +1)%capacity == front队列满

对于整个的capacity中,故意的浪费了一个空间。循环队列类似于钟表时针转动到12.

循环队列代码的基本实现

package cn.mtianyan;

import java.util.Arrays;

public class LoopQueue<E> implements Queue<E> {

    private E[] data;
    private int front, tail; // 队首和下一个空位置索引
    private int size;        // 可以没有size,自己尝试

    public LoopQueue(int capacity) {
        data = (E[]) new Object[capacity+1]; // 因为会有一个浪费
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue() {
        this(10);
    }

    public int getCapacity(){
        return data.length-1;
    }

    @Override
    public void enqueue(E e) {
        if (isFull()){
            resize(getCapacity()*2);
        }
        data[tail] = e;
        tail = (tail+1) % data.length;
        size++;
    }

    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity +1];
        for (int i = 0; i < size; i++) {
            newData[i] = data[(i+front) % data.length]; // 此时在newData中队首对齐回来,data中就得有一个front的偏移量
        }
        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public E dequeue() {
       if (isEmpty()){
           throw new IllegalArgumentException("Cannot dequeue from an empty queue");
       }
       E ret = data[front];
       data[front] = null;
       front = (front+1) % data.length;
       size--;
       if(size == getCapacity()/4 && getCapacity()/2 != 0){
           resize(getCapacity()/2);
       }
       return ret;
    }

    @Override
    public E getFront() {
        if (isEmpty()){
            throw new IllegalArgumentException("Cannot dequeue from an empty queue");
        }
        return data[front];
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }
    public boolean isFull(){
        return (tail +1)%data.length ==front; // 下一个tail指向front
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("LoopQueue: size = %d, capacity = %d\n",size,getCapacity()));
        res.append("front [");
        for (int i = front; i != tail; i = (i+1)%data.length) {
            res.append(data[i]);
            if ((i+1)%data.length !=tail) // 最后一个元素不要加,
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }
    public static void main(String[] args) {
        LoopQueue<Integer> queue = new LoopQueue<>();
        for (int i = 0; i < 5; i++) {
            queue.enqueue(i);
            System.out.println(queue);
            if(i %3 == 2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

运行结果:

这里的resize和toString中我们使用了两种不同的遍历方式。一种是size次,元素取值时index偏移量;一种是头不等于尾,i按照循环取值规则向后++。

用户在使用数据结构时,只需要了解接口中设计的方法,其他内部实现对于用户进行了隐藏,比如内部的capacity+1等操作。

循环队列的出队复杂度也变成了O(1),具体的性能对比我们下一节来对比。

循环队列的复杂度分析

ArrayQueue<E>

void enqueue(E e); // 入队 O(1) 均摊
E dequeue();       // 出队 O(1) 均摊
E getFront();      // 获取队首元素 O(1)
int getSize();      // 获取队列元素多少 O(1)
boolean isEmpty();  // 是否为空 O(1)

出队操作可能触发缩容。具体O(n)比O(1)慢多少。

对10万个元素入队出队看时间。

package cn.mtianyan;

import java.util.Random;

public class Main {
    /**
     * 测试使用q运行optCount个enqueue和deQueue操作所需时间。单位: 秒
     *
     * @param q
     * @param opCount
     * @return
     */
    private static double testQueue(Queue<Integer> q,int opCount){
        long startTime = System.nanoTime();

        Random random = new Random();

        for (int i = 0; i < opCount; i++) {
            q.enqueue(random.nextInt(Integer.MAX_VALUE)); // 生成从0到int最大值
        }
        for (int i = 0; i < opCount; i++) {
            q.dequeue();
        }

        long endTime = System.nanoTime(); // 纳秒

        return (endTime - startTime)/ 1e9;
    }

    public static void main(String[] args) {
        int opCount = 100000;
        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue, opCount);
        System.out.println("ArrayQueue出队入队"+opCount+"次的时间: "+time1+"秒");
        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue, opCount);
        System.out.println("loopQueue出队入队"+opCount+"次的时间: "+time2+"秒");
    }
}

运行结果:

对于100万的运行结果:

两者的差距主要在出队的过程中。对于ArrayQueue来说,每出一次队,队首后面的所有元素都得挪动一次。出队操作复杂度是O(n),相应而言,对于ArrayQ,整个testQueue的复杂度就是O(n^2),因为每次O(n),for循环有n次。对于LoopQueue的testQueue: 每次都是O(1),for循环有n次,因此testQueue()为O(n)。

性能对比:

Queue类型

循环次数

时间

倍数

LoopQueue

10万

0.01

1(基准)

ArrayQueue

10万

2.85

285

LoopQueue

100万

0.06

1(基准)

ArrayQueue

100万

285.46

4758

这是对于O(n)以及O(n^2) 的性能对比,可以看出性能差异巨大。对于同一种Queue实现,我们依然可以根据(0.06/0.01)=6 数据量扩大十倍,时间复杂度扩大了6倍,验证O(n); (285.46/2.85)=100,数据量扩大10倍,时间复杂度扩大了100倍,验证O(n^2)。

更合理的测试方法是对于testQueue也进行多次,取平均值。和JVM也会有关。

同一台电脑,我改为java10运行。不知为什么比java8的运行速度慢了很多。

队列的应用: 排队,操作系统任务排队。队首的定义,存在广义队列,后面会学。此处我们学到的普通队列,在后面的广度优先遍历,二叉树时也可以学到。

下一章,我们将讲解链表。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏包子铺里聊IT

How to design and implement a deep iterator?

包子IT面试培训 助你拿到理想的offer! Question: Write a deep iterator to iterate through a li...

3285
来自专栏小狼的世界

如何向回调函数中传入其他参数

最近写JS经常会因为向回调函数中传参而头疼,今天总结一下向回调函数中传参的方法,以后的应用中就不用在到处去找了。

631
来自专栏Android知识点总结

看得见的数据结构Android版之队列篇

方法\数量|1000|次10000次|10W次|100W次|1000次 --- |---|---|---|---|---|---| enqueue|0.00...

701
来自专栏积累沉淀

【译】Java 8的新特性—终极版

声明:本文翻译自Java 8 Features Tutorial – The ULTIMATE Guide,翻译过程中发现并发编程网已经有同学翻译过了:...

23210
来自专栏搜云库

BTA 常问的 Java基础40道常见面试题及详细答案

最近看到网上流传着,各种面试经验及面试题,往往都是一大堆技术题目贴上去,而没有答案。

5706
来自专栏友弟技术工作室

awk(报告生成器),grep(文本过滤器),sed(流编辑器)使用入门

三剑客 linux下的文本三剑客 grep egrep,grep,fgrep 文本查找的需要 grep:根据模式搜索文本,并将符合模式的文本行显示出来。 pa...

35311
来自专栏小李刀刀的专栏

Unicode编解码函数

在用XMLHTTP进行远程数据传输的时候,如果涉及到不同编码,比如从oblog向我的博客发送一个trackback ping,数据中包含的中文字符就会出现乱码。...

3255
来自专栏Ryan Miao

velocity的一些用法

velocity模板其实就是java不分语法的翻译,用到的属性还是java的方法,get,set,等 1.截取部分字段substring 1 原始字符串:$!a...

35511
来自专栏进击的君君的前端之路

知识点梳理

1012
来自专栏二进制文集

JDK源码分析 异常

对于JDK源码分析的文章,仅仅记录我认为重要的地方。源码的细节实在太多,不可能面面俱到地写清每个逻辑。所以我的JDK源码分析,着重在JDK的体系架构层面,具体源...

1804

扫码关注云+社区