表、栈和队列习题

3.1 操作printLots(L,P)打印L中那些P所指定位置上的元素

1. ArrayList添加元素的方法：add。ArrayList P = new ArrayList<>(){{add(1);add(2);}};

2. 嵌套循环可以用于打印指定位置的元素

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
 * P67 习题3.1
 * 题目要求：给定表L和表P，他们包含升序排列的整数。操作printLots(L,P)打印L中那些P所指定位置上的元素。
 * 示例：如果P=1,3,4,6 那么L中位于第1，第3，第4，第6位置上的元素被打印出来
 * 注意：只可使用public型的Collections API容器操作
 */
public class _3_1 {
    public static <AnyType> void printLots(List<AnyType> L, List<Integer> P){
        long startTime = System.currentTimeMillis();
        Iterator<AnyType> iterL = L.iterator();
        Iterator<Integer> iterP = P.iterator();
        int start = 0;
        AnyType itemL = null;
        Integer itemP = 0;
        while (iterP.hasNext()){
            itemP = iterP.next();
            System.out.println("Looking for position" + itemP);
            while (start < itemP && iterL.hasNext()){
                start++;
                itemL = iterL.next();
            }
            System.out.println(itemL);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("系统运行时间为："+ (endTime-startTime) + "ms");
    }
    public static void main(String[] args) {
        ArrayList<String> L = new ArrayList<>(){{add("aa");add("bb");add("cc");}};
        ArrayList<Integer>  P = new ArrayList<>(){{add(1);add(2);}};
        printLots(L,P);
    }
}

3.2 通过调整链（而不是数据）来交换相邻的元素

1.单链表和双链表的定义与使用

2.交换链表元素时要考虑详细，最好按顺序依次更改

3.先调用单链表，再调用双链表会出现双链表调用少节点的问题，反之则没有问题。我认为是实现链表的类实现的有问题，导致先调用单链表时，对节点的后继节点造成了改变，导致节点丢失。

public class _3_2 {
    /**
     *P67 习题3.2
     * 题目描述：通过调整链（而不是数据）来交换相邻的元素
     * 注意：分别使用单链表和双链表完成
     */
    //创建一个链表的类
    static class Node {
        int val;    //数值 data
        Node next;    // 结点 node
        Node prev;
        Node(int x) {    //可以定义一个有参构造方法，也可以定义一个无参构造方法
            val = x;
        }
        public Node() {
        }
        // 添加新的结点
        public void add(int newVal) {
            Node newNode = new Node(newVal);
            if (this.next == null) {
                this.next = newNode;
                newNode.prev = this;
                newNode.next = null;
            }else{
                this.next.add(newVal);
            }
        }

        public void print() {
            System.out.print(this.val);
            if (this.next != null) {
                System.out.print("-->");
                this.next.print();
            }
        }
    }

    //单链表
    //beforeP 是需要交换的两个节点的前面的节点
    public static void swapWithNext(Node beforeP){
        Node P,afterP;

        P = beforeP.next;
        afterP = P.next;

        beforeP.next = afterP;
        P.next = afterP.next;
        afterP.next = P;
    }

    //双链表
    //同上，省略错误检查
    public static void swapWithNextDouble(Node p){
        Node beforep , afterp;

        beforep = p.prev;
        afterp = p.next;

        p.next = afterp.next;
        beforep.next = afterp;
        afterp.next = p;

        p.next.prev = p;
        p.prev = afterp;
        afterp.prev = beforep;

    }

    public static void main(String[] args) {
        Node p = new Node();
        p.val = 1;
        p.add(3);
        p.add(5);
        p.add(7);
        p.add(9);
        System.out.println("Origin : ");
        p.print();

        //p.next.next = 5 交换5和7
        swapWithNextDouble(p.next.next);
        System.out.println("\nDouble chain : ");
        p.print();

        //p.next = 3  将会交换7和5
        swapWithNext(p.next);
        System.out.println("\nSingle chain : ");
        p.print();
    }
}

3.3 实现MyLinkedList的contaqins例程

3.4 给定两个已排序的表L1和L2，只使用基本的表操作编写计算L1∩L2的过程

使用迭代器，循环比较，添加到结果列表中即可

3.5 给定两个已排序的表L1和L2，只使用基本的表操作编写计算L1∪L2的过程

使用迭代器，循环比较，添加到结果列表中即可

3.11 假设单链表使用一个头节点实现，无尾节点，只保留对该头节点的引用，编写一个链表类

3.25 提出一种数据结构支持栈的push和pop操作以及第三种操作findMin，它返回该数据结构的最小元素。所有操作均以O(1)最坏情形运行

维持两个栈，一个S，用来push和pop，另一个M用于保持最小值

3.26 用一个数组实现三个栈结构

一个自顶向下生长，一个自底向上生长，第三个从中间生长（上或者下）。一旦第三个栈碰到了其他两个栈，就将其移动。一个合理的策略是，将其中间移到上下两个栈的中间

3.31 用单链表实现栈⭐

import java.util.*;

/**
 * P68 习题3.31
 * 题目要求：单链表实现栈。
 * Attention:head本身只用来表示头节点，而与节点的后继没有联系
 */
public class SingleStack<AnyType> {
    SingleStack(){
        head = null;
    }

    void push(AnyType x){
        Node<AnyType> p = new Node<AnyType>(x, head);
        head = p;
    }

    AnyType top(){
        return head.data;
    }

    void pop(){
        head = head.next;
    }

    private static class Node<AnyType>{
        Node(){
            this(null,null);
        }
        Node(AnyType x){
            this(x,null);
        }
        Node(AnyType x , Node p){
            data = x;
            next = p;
        }
        AnyType data;
        Node next;
    }

    private Node<AnyType> head;

}