【内功修炼系列1】线性数据结构（下篇2）

承上启下

上代码

链表

「2、判断一个链表中是否有环；」

「分析」：循环遍历节点，遍历一个便标记一个，遍历过程判断是否被标记，若已被标记则表示有环。头指针移动，若到达之前到达过的位置则表示有环，若无环则会走到链表末端。

package com.demo.linklist;

import java.util.HashSet;
import java.util.Set;

/**
 * 判断链表中是否有换
 *
 * @author dongx on 2020/9/20
 */
public class LinkedListHaveCycleDemo {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static class Solution {
        public boolean hasCycle(ListNode head) {
            //声明一个set存放已遍历的节点，即为标记节点（Set中不允许重复元素）
            Set<ListNode> set = new HashSet<>();
            while(head!=null) {
                if(set.contains(head)) {
                    return true;
                }else {
                    set.add(head);
                    head = head.next;
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        ListNode tail = null;
        ListNode temp = null;
        for (int i = 1; i < 8; i++) {
            ListNode listNode = new ListNode(i);
            if (null != temp) {
                temp.next = listNode;
            } else {
                head.next = listNode;
            }
            temp = listNode;
            System.out.print(temp.val + ",");
            tail = listNode;
        }
        Solution solution = new Solution();
        System.out.println("链表是否存在环：" + solution.hasCycle(head));
        // 将尾部与头部相连
        tail.next = head;
        System.out.println("头尾相连后，链表是否存在环：" + solution.hasCycle(head));
    }
}

「结果」：

栈和队列

「1、判断一段文章中，各种括号（大、中、小）是否合法；」

「分析」：这个应该比较容易，我们可以利用栈的特性，做相应括号的匹配，如果最后栈是空的，说明所有括号都已经配对了。注意一下判断，如果第一个入栈的右括号，那么立即返回不合法；

「结果」：

「2、用栈实现一个队列；」

「分析」：栈的特点是FILO，而队列是FIFO，如果想实现这一转换，我们会想到用两个栈去实现。开始时，每次添加队尾元素到stack1中。如果需要弹出队头元素，则将stack1中的元素弹出并push到stack2中，再将stack2的栈顶元素弹出，即为弹出了队头元素。如果stack2中是非空的，再在队尾中添加元素的时候仍然加到stack1中，从stack2中弹出队头元素。只有当stack2为空的时候，弹出队头元素才需要将stack1中的元素转移到stack2中。

「结果」：

「3、设计一个循环队列；」

「分析」：循环队列即为队列的顺序表示和实现，其优点主要是入队和出队的时间复杂度均为O(1)，这要归功于“循环队列将存储结构的理解由序列型转换为环型”的思维方式。

package com.demo.stackandqueue;

/**
 * 循环队列接口
 *
 * @author dongx on 2020/9/21
 */
public interface ISequenceQueue<T> {
    public boolean push(T t);

    public T pop();

    public int length();

    public int size();

    public boolean isEmpty();

    public boolean isFull();
}

package com.demo.stackandqueue;

import java.util.Stack;

/**
 * 循环队列
 *
 * @author dongx on 2020/9/21
 */
public class CycleQueueDemo<T> implements ISequenceQueue<T> {

    Object[] datas;
    int size;
    int front = 0;
    int rear = 0;

    public CycleQueueDemo(int size) {
        this.size = size;
        this.datas = new Object[size];
    }

    @Override
    public boolean push(T t) {
        if (isFull()) {
            return false;
        }
        datas[rear] = t;
        rear = (rear + 1) % size;
        return true;
    }

    @Override
    public T pop() {
        if (isEmpty()) {
            return null;
        }
        @SuppressWarnings("unchecked")
        T t = (T) datas[front];
        datas[front] = null;
        front = (front + 1) % size;
        return t;
    }

    @Override
    public int length() {
        return (rear - front + size) % size;
    }

    @Override
    public boolean isEmpty() {
        if (rear == front) {
            return true;
        }
        return false;
    }

    @Override
    public boolean isFull() {
        if ((rear + 1) % size == front) {
            return true;
        }
        return false;
    }

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

    public static void main(String[] args) {
        CycleQueueDemo<Integer> o = new CycleQueueDemo<Integer>(10);
        for (int i = 1; i <= 30; i++) {
            boolean b = o.push(i);
            System.out.println("入队后队列长度为" + o.length());
            if (i % 2 == 0) {
                Integer out = o.pop();
                System.out.println(i + "现在的长度是" + o.length() + ", 出队值=" + out);
            }
            if (!b) {
                System.out.println("未入队" + i);
            }
        }
        for (int i = 1; i <= 10; i++) {
            Integer out = o.pop();
            System.out.println(i + "现在的长度是" + o.length() + ", 出队值=" + out);
        }
        System.out.println("");
    }
}