算法与数据结构全阶班-左程云版(二)基础阶段之2.链表、栈、队列、递归行为、哈希表和有序表(下)

简介: 本文主要介绍了一些常用的数据结构,包括链表、栈、队列、递归、哈希表和有序表。

用栈实现队列:

也是用两个栈来实现,包括push栈和pop栈,如下:

2345_image_file_copy_109.jpg

遵循的原则:

pop栈为空时,才能将数据导入到pop栈中;

push栈导数据到pop栈时,一次导完。

实现如下:

static class TwoStackQueue {
    private final Stack<Integer> stackPush;
    private final Stack<Integer> stackPop;
    public TwoStackQueue() {
        stackPush = new Stack<>();
        stackPop = new Stack<>();
    }
    // push栈向pop栈导入数据
    private void pushToPop() {
        if (stackPop.isEmpty()) {
            while (!stackPush.isEmpty()) {
                stackPop.push(stackPush.pop());
            }
        }
    }
    public void add(int num) {
        stackPush.push(num);
        pushToPop();
    }
    public int poll() {
        if (stackPush.isEmpty() && stackPop.isEmpty()) {
            throw new RuntimeException("Queue is empty!");
        }
        pushToPop();
        return stackPop.pop();
    }
    public int peek() {
        if (stackPush.isEmpty() && stackPop.isEmpty()) {
            throw new RuntimeException("Queue is empty!");
        }
        pushToPop();
        return stackPop.peek();
    }
}

面试:

一般情况下,图的宽度优先遍历使用的是队列,深度优先遍历使用的是栈;

如果要让用栈实现宽度优先遍历、队列实现深度优先遍历,则需要用两个栈实现队列、两个队列实现栈。

3.递归

怎么从思想上理解递归;

怎么从实际实现的角度出发理解递归。

递归的思想是将一个大的任务分解成小的任务,小的任务再进一步拆解,直到达到某一个边界,最后经过某种逻辑进行整合,得到整个问题的求解。

递归调用时,使用了系统栈,调用的函数放入栈,执行完返回时就会从栈顶pop出;

任何递归都可以改为迭代。

有一类递归的时间复杂度可以确定,时间复杂度原始形式如下:

2345_image_file_copy_111.jpg

即条件为:子问题的规模是一致的

时间复杂度公式如下:

2345_image_file_copy_112.jpg

2345_image_file_copy_113.jpg

例题:求数组arr[L…R]中的最大值,怎么用递归方法实现。

分析思路:

1)将[L…R]范围分成左右两半。左:[L…Mid]右[Mid+1…R];

2)左部分求最大值,右部分求最大值;

3)[L…R]范围上的最大值,是max{左部分最大值,右部分最大值}。

注意:2)是个递归过程,当范围上只有一个数,就可以不用再递归了。

思路如下:

2345_image_file_copy_114.jpg

这里的子问题规模是原问题的一半,所以可以求出时间复杂度,时间复杂度如下:

2345_image_file_copy_115.jpg2345_image_file_copy_116.jpg

实现如下:

public class MaxWithRecursion {
    public static int getMax(int[] arr) {
        return process(arr, 0, arr.length - 1);
    }
    // arr[L..R]范围上求最大值
    public static int process(int[] arr, int L, int R) {
        // arr[L..R]范围上只有1个数,直接返回
        if (L == R) {
            return arr[L];
        }
        int mid = L + ((R - L) >> 1);           // 中点
        int leftMax = process(arr, L, mid);
        int rightMax = process(arr, mid + 1, R);
        return Math.max(leftMax, rightMax);
    }
}

4.哈希表和有序表

哈希表

1)哈希表在使用层面上可以理解为—种集合结构;

2)如果只有key、没有伴随数据value,可以使用HashSet结构;

3)如果既有key,又有伴随数据value,可以使用HashMap结构;

4)有无伴随数据,是HashMap和HashSet唯一的区别,实际结构是一回事;

5)使用哈希表增(put)、删(remove)、改(put)和查(get)的操作,可以认为时间复杂度为O(1),但是常数时间比较大;

6)放入哈希表的元素,如果是基础类型,内部按值传递,内存占用是这个元素的大小;

7)放入哈希表的元素,如果不是基础类型(是自定义类型),内部按引用传递,内存占用是8字节(也就是引用地址的大小)。

使用如下:

static class Node {
    public int value;
    public LinkedList.Node next;
    public Node(int data) {
        value = data;
    }
}
public static void testHashMap() {
    // 键值对
    HashMap<Integer, String> map = new HashMap<>();
    // 新增
    map.put(1, "one");
    map.put(2, "two");
    map.put(3, "three");
    map.put(4, "four");
    map.put(5, "five");
    System.out.println(map.containsKey(1));
    System.out.println(map.containsKey(10));
    System.out.println(map.containsValue("one"));
    System.out.println(map.containsValue("one"));
    System.out.println(map.get(1));
    System.out.println(map.get(10));
    // 修改
    map.put(1, "一");
    System.out.println(map.get(1));
    map.remove(5);
    System.out.println(map.get(5));
    System.out.println("--------------------");
    // 集合元素
    HashSet<String> set = new HashSet<>();
    set.add("one");
    System.out.println(set.contains("one"));
    set.remove("one");
    System.out.println(set.contains("one"));
    System.out.println("--------------------");
    // 引用传递和值传递
    int a = 10000000;
    int b = 10000000;
    System.out.println(a == b);         // int属于基本数据类型,使用值传递,所以比较时只比较值,不比较地址
    Integer c = 10000000;
    Integer d = 10000000;
    System.out.println(c == d);         // Integer属于引用数据类型,使用引用传递,所以比较时比较地址,不比较值,要比较值使用equals方法
    System.out.println(c.equals(d));
    Integer e = 128;
    Integer f = 128;
    System.out.println(e == f);
    e = 127;
    f = 127;
    System.out.println(e == f);         // -128到127之间,使用常量池,转化为值传递,不在这个区间才使用引用传递
    // 新增
    map.put(10000, "10000");
    System.out.println(map.get(10000));
    // 修改
    map.put(10000, "一万");
    System.out.println(map.get(10000)); // 放入哈希表的元素,如果是基础类型,内部按值传递
    HashMap<Node, String> map2 = new HashMap<>();
    Node node1 = new Node(1);
    Node node2 = new Node(1);
    map2.put(node1, "node1");
    map2.put(node2, "node1 too");
    System.out.println(map2.get(node1));
    System.out.println(map2.get(node2));
    node2 = node1;
    System.out.println(map2.get(node2));
}

输出:

true
false
true
true
one
null
null
--------------------
true
false
--------------------
true
false
true
false
true
10000
一万
node1
node1 too
node1

有序表:

有序表指集合内的元素按照某种规则进行排序;

使用哈希表增(put)、删(remove)、改(put)和查(get)的操作,时间复杂度为O(logN)

AVL、SB树、红黑树和跳表都可以实现有序表,通过调整实现平衡。

使用有序表TreeMap如下:

public static void testTreeMap() {
    TreeMap<Integer, String> map = new TreeMap<>();
    map.put(3, "three");
    map.put(7, "seven");
    map.put(2, "two");
    map.put(1, "one");
    map.put(5, "five");
    map.put(9, "nine");
    map.put(6, "six");
    System.out.println(map.containsKey(1));
    System.out.println(map.containsKey(10));
    System.out.println(map.get(1));
    System.out.println(map.get(10));
    // 修改
    map.put(5, "五");
    System.out.println(map.get(5));
    // 删除
    map.remove(5);
    System.out.println(map.get(5));
    // 查看顺序
    System.out.println(map.firstKey());
    System.out.println(map.lastKey());
    System.out.println(map);
    // 小于等于5的最近的值
    System.out.println(map.floorKey(5));
    // 大于等于5的最近的值
    System.out.println(map.ceilingKey(5));
}

输出:

true
false
one
null
null
1
9
{1=one, 2=two, 3=three, 6=six, 7=seven, 9=nine}
3
6

总结

有很多常用的数据结构,每种数据结构都有适用的场景,可以根据自己的需要进行选择。

相关文章
|
3天前
|
算法 索引
【数据结构与算法】5、循环链表、约瑟夫问题、静态链表
【数据结构与算法】5、循环链表、约瑟夫问题、静态链表
22 0
|
3天前
数据结构界的三大幻神----栈
数据结构界的三大幻神----栈
|
3天前
|
索引
数据结构界的幻神(First)----链表
数据结构界的幻神(First)----链表
|
2天前
|
Python
Python实现数据结构(如:链表、栈、队列等)。
Python实现数据结构(如:链表、栈、队列等)。
17 0
|
3天前
|
存储 算法 Java
【数据结构与算法】7、队列(Queue)的实现【用栈实现队列】
【数据结构与算法】7、队列(Queue)的实现【用栈实现队列】
23 0
|
3天前
|
算法 安全 Java
【数据结构与算法】6、栈(Stack)的实现、LeetCode:有效的括号
【数据结构与算法】6、栈(Stack)的实现、LeetCode:有效的括号
13 0
|
3天前
|
算法 Java 索引
【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码)
【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码)
16 0
|
3天前
|
存储 算法
【数据结构与算法】3、虚拟头节点、动态数组的缩容、动态数组和单链表的复杂度、数组的随机访问
【数据结构与算法】3、虚拟头节点、动态数组的缩容、动态数组和单链表的复杂度、数组的随机访问
10 0
|
3天前
|
存储 算法 Java
【数据结构与算法】2、链表(简单模拟 Java 中的 LinkedList 集合,反转链表面试题)
【数据结构与算法】2、链表(简单模拟 Java 中的 LinkedList 集合,反转链表面试题)
22 0
|
7天前
|
存储
栈和队列OJ题
栈和队列OJ题
17 0

相关产品