001 什么是链表?

链表是一种动态的数据结构,因为在创建链表时,我们不需要知道链表的长度,当插入一个结点时,只需要为该结点分配内存,然后调整指针的指向来确保新结点被连接到链表中。所以,它不像数组,内存是一次性分配完毕的,而是每添加一个结点分配一次内存。正是因为这点,所以它没有闲置的内存,比起数组,空间效率更高。

002 链表的分类?

1)单向链表,双向链表
单向:每个节点只有一个后继指针next指向后面的节点,结尾通常指向null
双向:包含两个指针,prev指向前一节点,next指向后一节点
2)带头链表,不带头链表
3)循环的,非循环的
循环:特殊的单链表,尾结点指向头节点

003 枚举法创建链表?

首先创建节点类:单链表中的节点应该具有两个属性:val 和 next。val存储的该节点的数据值,next存储下一个节点的地址。下面提供两种创建链表的方式:分别是枚举法和尾插法。

class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
}

枚举法:直接进行val的赋值以及对next的初始化。

public ListNode head;//链表的头
public void creatList(){
    ListNode listNode1 = new ListNode(11);
    ListNode listNode2 = new ListNode(22);
    ListNode listNode3 = new ListNode(33);
    ListNode listNode4 = new ListNode(44);

    this.head=listNode1;
    listNode1.next = listNode2;
    listNode2.next = listNode3;
    listNode3.next = listNode4;
}

004 尾插法创建链表

class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
}

尾插法:插入第一个节点时,直接将该节点赋值给head,之后每次插入新节点都会通过head.next移动到最后一个节点cur,然后将新节点赋值给cur.next

public ListNode head;//链表的头    
public void add(int data){
    ListNode node = new ListNode(data);
    if(this.head == null){
        this.head = node;
    }else {
        ListNode cur = this.head;
        while(cur.next != null){
            cur = cur.next;
        }
        cur.next = node;
    }
}

005 如何打印链表?

头结点head是不动的,通过head.next不断移动,在移动的过程中输出链表的内容。

public void display(){
    ListNode cur = this.head;
    while(cur != null){
        System.out.print(cur.val+" ");
        cur = cur.next;
    }
    System.out.println();
}

006 通过栈将链表逆序输出,如链表为1->2->3,打印出3 2 1

思路:根据栈先进后出的特点,在遍历链表时,把值按顺序放入栈中,最后出栈就是逆序了。

/**
* 栈
*/
public List<Integer> printListFromQueue(ListNode listNode) {
    Stack<Integer> stack = new Stack<>();
    while (listNode != null) {
        stack.add(listNode.value);
        listNode = listNode.next;
    }
    List<Integer> list = new ArrayList<>();
    while (!stack.isEmpty()) {
        list.add(stack.pop());
    }
    return list;
}

007 通过递归将链表逆序输出,如链表为1->2->3,打印出3 2 1。

思路:因为递归的本质也是用的栈,所以先递归输出它的后面节点,再输出自己,这样链表就反过来了。

/**
* 递归
*/
public List<Integer> printListFromDG(ListNode listNode) {
    List<Integer> list = new ArrayList<>();
    if (listNode != null) {
        list.addAll(printListFromDG(listNode.next));
        list.add(listNode.value);
    }
    return list;
}

008 用数组法判断链表是否为回文结构

将链表元素都赋值到数组中,然后可以从数组两端向中间对比。

009 用全部压栈法判断链表是否为回文结构。

将链表元素全部压栈,然后一边出栈,一边重新遍历链表,一边比较,只要有一个不相等,那就不是回文链表了。

public boolean isPalindrome(ListNode head) {
    ListNode temp = head;
    Stack<Integer> stack = new Stack();
    //把链表节点的值存放到栈中
    while (temp != null) {
        stack.push(temp.val);
        temp = temp.next;
    }
    //然后再出栈
    while (head != null) {
        if (head.val != stack.pop()) {
            return false;
        }
        head = head.next;
    }
    return true;
}

010 用部分压栈法判断链表是否为回文结构。

上面方法的改造,先遍历第一遍,得到总长度。之后一遍历链表,一遍压栈。当到达链表长度一半的位置之后,就不再压栈,而是一边出栈,一遍遍历,一遍比较,只要有一个不相等,就不是回文链表。

public boolean isPalindrome(ListNode head) {
    if (head == null)
        return true;
    ListNode temp = head;
    Stack<Integer> stack = new Stack();
    //链表的长度
    int len = 0;
    //把链表节点的值存放到栈中
    while (temp != null) {
        stack.push(temp.val);
        temp = temp.next;
        len++;
    }
    //len长度除以2
    len >>= 1;
    //然后再出栈
    while (len-- >= 0) {
        if (head.val != stack.pop())
            return false;
        head = head.next;
    }
    return true;
}

011 用快慢指针法法判断链表是否为回文结构。

我们使用快慢指针 ,fast一次走两步,slow一次走一步。当fast到达表尾的时候,slow正好到达一半的位置,那么接下来可以从头开始逆序一半的元素,或者从slow开始逆序一半的元素,都可以。

public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        ListNode slow = head, fast = head;
        ListNode pre = head, prepre = null;
        while(fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
            //将前半部分链表反转
            pre.next = prepre;
            prepre = pre;
        }
        if(fast != null) {
            slow = slow.next;
        }
        while(pre != null && slow != null) {
            if(pre.val != slow.val) {
                return false;
            }
            pre = pre.next;
            slow = slow.next;
        }
        return true;
 }

012 利用HashSet判断链表是否有环?

思路:循环链表将链表节点(注意是节点,不是节点里的值)存入到hashset中,如果元素添加不进去则证明有环。

public static boolean hasCycle1(ListNode head){
	//存入的是ListNode类型而不是值
    HashSet<ListNode> hashSet = new HashSet<>();
    while (head!=null){
        if (!hashSet.add(head)){
            return true;
        }
        head=head.next;
    }
    return false;
}

复杂度分析:
时间复杂度:O(N),其中 N 是链表中的节点数。最坏情况下我们需要遍历每个节点一次。
空间复杂度:O(N),其中 N 是链表中的节点数。主要为哈希表的开销,最坏情况下我们需要将每个节点插入到哈希表中一次。

013 利用快慢指针判断链表是否有环?

解决思路:定义两个指针,一个指针每次移动一个位置为慢指针,一个指针每次移动两个位置为快指针。当两个指针相遇时就证明有环,如果快指针或者慢指针下一个节点为null,则证明无环。
为什么两个指针一定会相遇呢?
两个指针一旦进入环,遍历的时候相当于无限循环因为出不出来环啊。想象一下时钟,时针分针秒针在不同速度遍历时是不是会相遇呢?

public static boolean hasCycle2(ListNode head){
    if (head==null || head.next==null){
        return false;
    }
    //定义两个指针,快指针比慢指针多一步
    ListNode slow = head;
    ListNode fast = head.next;

    while (slow!=fast){
        if (fast==null||fast.next==null){
            return false;
        }
        //快指针比慢指针多一步
        slow=slow.next;
        fast=fast.next.next;
    }
    return true;
}

复杂度分析
时间复杂度O(N) : 当链表中存在环时,每一轮移动后,快慢指针的距离将减小一。而初始距离为环的长度,因此至多移动 N 轮。
空间复杂度O(1) : 只使用了两个指针额外的空间

014 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 

思路;双指针思想

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {     
    if(l1 == null) return l2;     
    if(l2 == null) return l1;     
    if(l1.val < l2.val){         
        l1.next = mergeTwoLists(l1.next,l2);         
        return l1;     
    }else{         
        l2.next = mergeTwoLists(l1,l2.next);         
        return l2;     
    }
} 

015 删除排序链表中的重复元素。

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
示例 1:输入: 1->1->2 输出: 1->2 
示例 2:输入: 1->1->2->3->3 输出: 1->2->3 

//一次遍历,注意边界条件。
public ListNode deleteDuplicates(ListNode head) {     
    ListNode cur = head;     
    while(cur != null && cur.next != null){         
        if(cur.val == cur.next.val)             
            cur.next = cur.next.next;         
        else             
            cur = cur.next;     
    }     
    return head; 
} 

016 删除链表的倒数第N个节点。

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后,链表变为 1->2->3->5. 
说明:给定的 n 保证是有效的。

//设置哑节点1,让它走 n+1 步,再设置哑节点2,然后哑节点1和哑节点2一起移动,
//直到哑节点1走完链表,此时哑节点1和哑节点2之间正好隔着 n 个节点,再通过哑节点2删除倒数第 n 个节点。
public ListNode removeNthFromEnd(ListNode head, int n) {     
    ListNode dummy = new ListNode(0);     
    dummy.next = head;     
    ListNode first = dummy;     
    for (int i = 1; i <= n + 1;i++){         
        first = first.next;     
    }     
    ListNode second = dummy;     
    while(first != null){         
        first = first.next;         
        second = second.next;     
    }     
    second.next = second.next.next;     
    return dummy.next; 
} 

017 两两交换链表中的节点.

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例:给定 1->2->3->4, 你应该返回 2->1->4->3. 

//设置哑节点,注意循环条件,指针移动的速度是2(因为需要两两交换节点)。
public ListNode swapPairs (ListNode head) {     
    ListNode dummy = new ListNode(-1);     
    dummy.next = head;     
    ListNode pre = dummy;     
    while (pre.next != null && pre.next.next != null) {         
        ListNode l1 = pre.next;         
        ListNode l2 = pre.next.next;         
        l1.next = l2.next;         
        l2.next = l1;         
        pre.next = l2;         
        pre = l1;
    }     
    return dummy.next; 
} 

018 两数相加

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
示例:输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出: 7 -> 8 -> 0 -> 7 

//既然不能改变链表的结构(翻转链表),那就用一个栈来保存链表中的值,可以做到逆向输出。
//相加部分的代码逻辑就按常规思路写。
public ListNode addTwoNumbers (ListNode l1, ListNode l2) {     
    Stack<Integer> l1Stack = listNodetoStack(l1);     
    Stack<Integer> l2Stack = listNodetoStack(l2);     
    int carry = 0;     
    ListNode head = new ListNode(-1);     
    while (!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0) {         
        int x = l1Stack.isEmpty() ? 0 : l1Stack.pop();         
        int y = l2Stack.isEmpty() ? 0 : l2Stack.pop();         
        int sum = x + y + carry;         
        ListNode node = new ListNode(sum % 10);         
        carry = sum / 10;         
        node.next = head.next;         
        head.next = node;     
    }     
    return head.next; 
} 
private Stack<Integer> listNodetoStack (ListNode head) {     
    Stack<Integer> stack = new Stack<>();     
    while (head != null) {         
        stack.push(head.val);         
        head = head.next;     
    }     
    return stack; 
} 

019 分隔链表

给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。
每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1,也就是说可能有些部分为 null。
这k个部分应该按照在链表中出现的顺序进行输出,并且排在前面的部分的长度应该大于或等于后面的长度。
返回一个符合上述规则的链表的列表。
举例: 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]
示例 1:
输入:  root = [1, 2, 3], k = 5 输出: 1],[2],[3],[],[ 解释: 输入输出各部分都应该是链表,而不是数组。 例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。 第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。 最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。 
示例 2:
输入:  root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3 输出: 1, 2, 3, 4], [5, 6, 7], [8, 9, 10 解释: 输入被分成了几个连续的部分,并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。 
提示:
● root 的长度范围: [0, 1000].
● 输入的每个节点的大小范围:[0, 999].
● k 的取值范围: [1, 50].

/*思路:先统计出链表长度,除以 k, 求商和余数,其中:
● 余数代表最后结果中有多少个长链表
● 商代表每个短链表的长度(结果集中后部的链表)
● 长链表比短链表多一个节点*/
public ListNode[] splitListToParts (ListNode root, int k) {     
    ListNode cur = root;     
    int len = 0;     
    while (cur != null) {         
        cur = cur.next;         
        len++;     
    }     
    int mod = len % k;     
    int size = len / k;     
    cur = root;     
    ListNode[] ans = new ListNode[k];     
    for (int i = 0; cur != null && i < k; i++) {         
        ans[i] = cur;         
        int curSize = size + (mod-- > 0 ? 1 : 0);         
        for (int j = 0; j < curSize - 1; j++) {             
            cur = cur.next;         
        }         
        ListNode next = cur.next;         
        cur.next = null;         
        cur = next;     
    }     
    return ans; 
} 

020 奇偶链表

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。
示例 1:输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL 
示例 2:输入: 2->1->3->5->6->4->7->NULL  输出: 2->3->6->7->1->5->4->NULL 
说明:
● 应当保持奇数节点和偶数节点的相对顺序。
● 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。

设置三个指针,其中奇指针和偶指针是很自然能想到的,evenHead起辅助作用,用于将奇链表和偶链表结合起来。

public ListNode oddEvenList (ListNode head) {     
    ListNode odd = head;     
    ListNode even = head.next;     
    ListNode evenHead = even;     
    while (even != null && even.next != null) {         
        odd.next = even.next;         
        odd = odd.next; 
        even.next = odd.next; 
        even = even.next; 
    } 
    odd.next = evenHead; 
    return head; 
}

021 什么是栈?

栈是一种后进先出(Last in First Out)的数据结构,简称 LIFO。栈是一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。

022 栈的基本使用

public static void main(String[] args) {
    Stack < Integer > stack = new Stack < Integer > ();
    //入栈
    stack.push(3); //栈底
    stack.push(4);
    stack.push(5);
    stack.push(7); //栈顶
    //出栈:弹出栈顶元素
    System.out.println(stack.pop()); //7
    //再弹一次,此时栈顶元素为5了,如下。
    System.out.println(stack.pop());
    //获取栈顶元素但不删除,这时的栈顶元素以及是4了
    System.out.println(stack.peek());
    //判断栈顶元素是否为空
    System.out.println(stack.empty());
    Stack < Integer > stack1 = new Stack < > ();
    System.out.println(stack1.empty());
    //获取栈中的元素的位置,栈顶为1号,此时stack中有3,4两个元素,所以4元素的位置为1号
    System.out.println(stack.search(4));
    //使用父类的方法,stack继承自Vector
    System.out.println(stack.isEmpty());
}

023 下列关于栈叙述正确的是( )。

A. 栈顶元素最先能被删除
B. 栈顶元素最后才能被删除
C. 栈底元素永远不能被删除
D. 栈底元素最先被删除
答案: A    
解析:栈里面的元素都有被删除的机会,只不过栈顶的元素最先删除,栈底的元素最后删除。

024 一个栈的输入序列为1 2 3 4 5,则下列序列中不可能是栈的输出序列的是 ( )。

A. 2 3 4 1 5
B. 5 4 1 3 2
C. 2 3 1 4 5
D. 1 5 4 3 2
答案: B   
解析:B中1比3先进入,所以1在3之后出来。

025 在栈中,( )保持不变。

A. 栈的顶
B. 栈的底
C. 栈指针
D. 栈中的数据
答案: B   
解析:暂无解析。

026 new 创建对象时,对象的内存和指向对象的指针分别分配在( ).

A. 堆区,栈区
B. 常量区,堆区
C. 全局区,栈区
D. 栈区,堆区
答案: A   
解析:对象放在堆去,引用放在栈区。

027 假设用S表示进栈操作,用X表示出栈操作。如果元素的进栈顺序是abcd,为了得到出栈序列abcd,则相应的S和X的操作序列为( )?

A. SSSSXXXX
B. SSSXXSXX
C. SXSSXXSX
D. SXSXSXSX
答案:D
解析:按照选项中的操作会得到的出栈顺序如下
选项A中,abcd进栈,依次出栈,得到出栈顺序是dcba;
选项B中,abc进栈,cb出栈,d进栈,da出栈,得到出栈顺序是cbda;
选项C中,a进栈,a出栈,bc进栈,cb出栈,d进栈,d出栈,中得到出栈顺序是acbd;
选项D中,a进栈,a出栈,b进栈,b出栈,c进栈,c出栈,d进栈,d出栈,中得到出栈顺序是abcd;所以正确选项为D。

028 设若入栈序列的元素顺序为X,Y,Z,判断下列哪一个出栈序列是不可能的( )。

A. XYZ
B. YZX
C. ZXY
D. ZYX
答案: C   
解析:因为栈是先进后出,X在Y之前进入,所以X肯定在Y之后出来,所以ZXY不可能。

029 设计一个获取栈中最小元素的栈

class MinStack {
    private Stack < Integer > stack;
    private Stack < Integer > minStack;

    public MinStack() {
        stack = new Stack < > ();
        minStack = new Stack < > ();
    }

    public void push(int val) {
        stack.push(val);
        if (!minStack.empty()) {
            int top = minStack.peek();
            if (val <= top) {
                minStack.push(val);
            }
        } else {
            minStack.push(val);
        }
    }

    public void pop() {
        int popVal = stack.pop();
        if (!minStack.empty()) {
            int top = minStack.peek();
            if (top == popVal) {
                minStack.pop();
            }
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}

030 判断某个数组是否是正确的出栈顺序。

public class Demo5 {
    public static void main(String[] args) {
        int[] A = {
            1, 2, 3, 4, 5
        };
        int[] B = {
            4, 5, 3, 2, 1
        };
        System.out.println(IsPopOrder(A, B));
    }
    public static boolean IsPopOrder(int[] pushA, int[] popA) {
        Stack < Integer > stack = new Stack < > ();
        int j = 0;
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);
            while (j < popA.length && !stack.empty() && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }
}

031 什么是队列?

队列是一种先进先出的数据结构,这和栈有所不同,但又更容易理解。类似于食堂排队打饭,车站排队买票。后来的人排在队伍最后边,先来的人先打饭或者买票走。

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头

032 一个队列的进队顺序是1,2,....n,若进队和出队可以交替进行,则出队顺序可能是( )。

A. 1,2,........,n
B. 1,2,4,3,5,6,.....,n
C. n,n-1,....,1
D. 以上均有可能
答案:A
解析:队列是先进先出,所以B选项中3比4先入队,所以3比4先出队;C选项同理。

033 队列的“先进先出”特性是指( )。

A. 最早插入队列中的元素总是最后被删除
B. 当同时进行插入、删除操作时,总是插入操作优先
C. 每当有删除操作时,总是要先做一次插入操作
D. 每次从队列中删除的总是最早插入的元素
答案:D
解析:A选项中队列中的元素不一定非得删除;
B选项中,插入和删除的操作看谁先执行就就优先操作;
C选项中,删除操作时和插入没有关系;

034 循环队列的出队操作为()。

A.sq.front=(sq.front+1)% maxsize;
B.sq.front=sq.front+1;
C.sq.rear=(sq.rear+1)% maxsize;
D.sq.rear=sq.rear+1;
答案:A
解析:考察的是循环队列的特性和定义以及操作。 循环队列:最后一个单元的后继是第一个单元的队列。

035 队列是一种运算受限的线性表,以下说法准确的是?

A.单向队列在允许删除的一端叫队头,在允许插入的一端叫队尾。
B.单向队列在允许删除的一端叫队尾,在允许插入的一端叫队头。
C.队列可以用数组实现,也可以用链表实现
D.队列是先进先出的,栈是后进先出的
正确答案:ACD
解析:暂无解析

036 下述有关栈和队列的区别,说法错误的是?

A.栈是限定只能在表的一端进行插入和删除操作。
B.队列是限定只能在表的一端进行插入和在另一端进行删除操作。
C.栈和队列都属于线性表
D.栈的插入操作时间复杂度都是o(1),队列的插入操作时间复杂度是o(n)
正确答案:D
解析:暂无解析

037 数组实现队列?

队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的声明如下图 , 其中 maxSize 是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理,因此需要两个变量 front 及 rear 分别记录队列前后端的下标,front 会随着数据输出而改变,而 rear 则是随着数据输入而改变,如图所示

当我们将数据存入队列时称为” addQueue ”, addQueue 的处理需要有两个步骤:思路分析
1)将尾指针往后移: rear+1 , 当 front rear 【空】
2)若尾指针 rear 小于队列的最大下标 maxSize-1 ,则将数据存入 rear 所指的数组元素中,否则无法存入数据。rear
maxSize - 1[ 队列满 ]

038 数组实现队列的代码实现。

import java.util.Scanner;
public class ArrayQueueDemo {
    public static void main(String[] args) {
        //测试一把
        // 创建一个队列
        ArrayQueue queue = new ArrayQueue(3);
        char key = ' '; //接收用户输入
        Scanner scanner = new Scanner(System.in); //
        boolean loop = true;
        //输出一个菜单
        while (loop) {
            System.out.println("s(show): 显示队列");
            System.out.println("e(exit): 退出程序");
            System.out.println("a(add): 添加数据到队列");
            System.out.println("g(get): 从队列取出数据");
            System.out.println("h(head): 查看队列头的数据");
            key = scanner.next().charAt(0); //接收一个字符
            switch (key) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("输出一个数");
                    int value = scanner.nextInt();
                    queue.addQueue(value);
                    break;
                case 'g': //取出数据
                    try {
                        int res = queue.getQueue();
                        System.out.printf("取出的数据是%d\n", res);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h': //查看队列头的数据
                    try {
                        int res = queue.headQueue();
                        System.out.printf("队列头的数据是%d\n", res);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e': //退出
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出~~");
    }
}
class ArrayQueue {
    private int maxSize; //表示数组的最大容量
    private int front; //表示队列头
    private int rear; //表示队列尾
    private int[] arr; //该数组用于存放数据,模拟队列

    //创建队列的构造器
    public ArrayQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1; // 指向队列头部前一个位置
        rear = -1; // 指向队列尾,指向队列尾的数据(即就是队列最后一个数据)
    }

   //判断队列是否满
    public boolean isFull() {
        return rear == maxSize - 1;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return rear == front;
    }

    // 添加数据到队列
    public void addQueue(int n) {
        // 判断队列是否满
        if (isFull()) {
            System.out.println("队列满,不能加入数据~");
            return;
        }

        rear++; // 让 rear 后移
        arr[rear] = n;
    }

    // 获取队列的数据, 出队列
    public int getQueue() {
        // 判断队列是否空
        if (isEmpty()) {
            // 通过抛出异常
            throw new RuntimeException("队列空,不能取数据");
        }
        front++; // front 后移
        return arr[front];
    }

    // 显示队列的所有数据
    public void showQueue() {
        // 遍历
        if (isEmpty()) {
            System.out.println("队列空的,没有数据~~");
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d\n", i, arr[i]);
        }
    }

    // 显示队列的头数据, 注意不是取出数据
    public int headQueue() {
        // 判断
        if (isEmpty()) {
            throw new RuntimeException("队列空的,没有数据~~");
        }
        return arr[front + 1];
    }
}

039 打印数组

创建一个长度为6的整数数组,数组中有六个整数(直接赋值即可)。遍历数组中的每个元素,元素之间用空格隔开。比如:

数组为:{1,2,3,4,5}
打印结果:1 2 3 4 5 
package com.bjpowernode.array;
/*创建一个长度为6的整数数组,数组中有六个整数(直接赋值即可)。遍历数组中的每个元素,元素之间用空格隔开。
  比如数组为:{1,2,3,4,5}
  打印结果:1 2 3 4 5*/
public class Test1 {
    public static void main(String[] args) {
        int [] arr={1,2,3,4,5};//定义整数类型数组
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+"\t");
        }
    }
}

040 打印数组最小值

现有一个小数数组{12.9,53.54,75.0,99.1,3.14}。请编写代码,找出数组中的最小值并打印。

操作步骤
定义小数类型数组并存入元素。
定义小数变量min代表最小值。
遍历数组,用每个元素依次和变量min对比。
如果元素小于min,则把元素赋值给min。
遍历结束之后打印最小值。

package com.bjpowernode.array;
/*
现有一个小数数组{12.9,53.54,75.0,99.1,3.14}。请编写代码,找出数组中的最小值并打印。
    #### 训练提示
    1. 数组的元素是小数,需要定义小数类型数组。
    2. 找最小值和找最大值的思路是一样的。*/
public class Test2 {
    public static void main(String[] args) {
        double[] arr={12.9,53.54,75.0,99.1,3.14};//定义一个double数组
        double min=arr[0];
        for(int i=1;i< arr.length;i++){
            if(min>arr[i]){
                min=arr[i];
            }
        }
        System.out.println("最小值是"+min);
    }
}

041 已知二维数组A10×10中,元素a[2][0]的地址为560,每个元素占4个字节,则元素a[1][0]的地址为( )。

A. 520
B. 522
C. 524
D. 518
答案:A
解析:a[2][0]和a[1][0]相距10个元素,所以相差4*10=40个字节;

042 将数据元素2,4,6,8, 10, 12, 14, 16, 18,20, 22依次存放于一个一维数组中,然后采用折半查找方法查找数组元素16,被比较过的数组元素的轨迹依次为( )。

A. 12,18,14,16
B. 12,14, 18,16
C. 6,9,7,8
D. 6,7,9,8
答案:A
解析:这个一维数组A的长度是11。
因此,第一个比较的元素是A[11/2]=A[5]=12;第二个比较的元素是A[(6+11)/2]=A[8]=18;第三个比较的元素是A[(6+7)/2]=A[6]=14;第四个比较的元素是A[(7+7)/2]=A[7]=16。

043 若有说明:int a[3][4];则对 a 数组元素的非法引用是( )?

A. a[0][2*1]
B. a[1][3]
C. a[4-2][0]
D. a[0][2+2]
答案:D
解析:引用的时候是从0下标开始,不能越界。