一. 数据结构

image.png

1.1 指针的原理

image.png

1.2 链表

image.png

链表的基本操作:

image.png

链表 VS 数组:
数组的长度是固定的，而且存储二项式很麻烦，所以底层用链表比较多。

image.png

栈和队列 都是通过 链表或数组来实现的

二. 栈

image.png

栈的应用:

1. 函数或子程序调用
2. 博弈树遍历
3. 编辑器undo实现

三. 队列

image.png

四. 栈和栈实战

4.1 栈实战

http://poj.org/problem?id=2559

image.png

package com.suanfa.栈;

import java.util.Stack;

public class 最大矩形面积 {
    public static void main(String[] args) {
        int[] arr1 = {8,7,6,5,4,3,2};
        int rst = 0;
        rst = largestRectangleArea(arr1);
        System.out.println(rst);
        //bubbleSort2(arr1);
    }

    /**
     * 遍历数组
     * 1.栈为空则入栈
     * 2.若h[i]>=栈顶元素,入栈
     * 3.若h[i]<栈顶元素,则开始出栈计算面积,并将最后出栈的h[x]值改为h[i]再重新入栈
     *
     * @param heights 数组,本例会创建个新数组,在数组最后一个位置补个高度为0的图
     * @return 最大面积值
     */
    public static int largestRectangleArea(int[] heights) {
        int max = 0;
        Stack<Integer> s = new Stack<>();
        int [] h = new int[heights.length + 1];
        for (int i =0; i < h.length; i++) {
            h[i] = i == heights.length ? 0 : heights[i];
            //System.out.println("i="+i);
            //System.out.println("h[i]=" + h[i]);
            if (s.empty()) {
                //空栈直接入栈
                s.push( i );
                continue;
            }

            //System.out.println("h[s.peek()]:"+h[s.peek()]);
            if (h[i] < h[s.peek()]) {
                //遇到小于栈顶的值，开始出栈，查找最大面积
                int top = 0;
                while (!s.empty() && h[s.peek()] > h[i]) {
                    //top等于栈移出的元素的值
                    top = s.pop();
                    max = Math.max(( i - top ) * h[top], max);
                    //System.out.println("top="+top);
                    //System.out.println("h[top]="+h[top]);
                    //System.out.println("max="+max);

                }
                //将最后出栈的高度改为h[i]重新入栈
                h[top] = h[i];
                System.out.println("top=" + top + ",");
                s.push( top );
                s.push( i );
            } else {
                s.push( i );
            }

            /*for (Integer s1 : s) {
                System.out.print("栈:"+s1+",");
                System.out.println();
            }*/
            //System.out.println("===================================");

        }
        return max;
    }
}

4.2 队列实战

http://poj.org/problem?id=2259

题意：
维护一个team queue，每次入队列，如果跟这个元素在一个队里的元素已经在这个大队里，那么这个元素可以插到他们队友的后面。给出有几个队以及这些队里面包含的元素，输出要求出队的时候的元素。

分析:
按照题目输入的顺序，给队编号。因为属于同一个队的可以插队，所以在队列中，同一个队的必然在一起。所以一个总的队列，只用记录下来队伍的编号就可以了，再记录下来每个队伍中的顺序。

代码:

package com.suanfa.队列;

import java.util.*;

public class TeamQueue {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        TeamQueue tq = new TeamQueue();
        int count = 1;
        while (true) {
            List<Set<String>> listSet = new ArrayList<Set<String>>();
            List<Queue<String>> listQueue = new ArrayList<Queue<String>>();
            Queue<Integer> indexs = new LinkedList<Integer>();

            int n = sc.nextInt();
            if (n == 0) {
                break;
            }
            for (int i = 0; i < n; i++) {
                int m = sc.nextInt();
                Queue queue = new LinkedList();
                listQueue.add(queue);
                Set<String> set = new HashSet<String>();
                listSet.add(set);
                for (int j = 0; j < m; j++) {
                    listSet.get(i).add(sc.next());
                }
            }
            System.out.println("Scenario #" + count);
            count++;
            while (true) {
                String str = sc.next();
                if (str.equals("ENQUEUE")) {//入队
                    String num = sc.next();
                    tq.add(num, listQueue, listSet, indexs);
                } else if (str.equals("DEQUEUE")) {//出队
                    System.out.println(tq.remove(listQueue, indexs));
                } else if (str.equals("STOP")) {//结束
                    break;
                }
            }
            System.out.println();
        }
    }

    public void add(String num, List<Queue<String>> listQueue, List<Set<String>> listSet, Queue<Integer> indexs) {//入队
        int index = select(listSet, num);
        if (listQueue.get(index).isEmpty()) {
            indexs.add(index);
            listQueue.get(index).add(num);
        } else {
            listQueue.get(index).add(num);
        }

    }

    public String remove(List<Queue<String>> listQueue, Queue<Integer> indexs) {//出队
        while (true) {
            int index = indexs.peek();
            String str = listQueue.get(index).poll();
            if (listQueue.get(index).isEmpty()) {
                indexs.remove();
            }
            return str;
        }
    }


    public int select(List<Set<String>> listSet, String num) {//选队
        for (int i = 0; i < listSet.size(); i++) {
            if (listSet.get(i).contains(num)) {
                return i;
            }
        }
        return -1;
    }
}

参考:

1. http://www.dataguru.cn/article-5747-1.html