JAVA

抽象数据类型（ADT）是具有一组操作的对象的集合. 这是数学上的抽象.

由表，图形，集合及其各自的操作（添加，删除等）形成的对象.

恒定时间运行恒定时间运行

*删除最后一项时:

找到指向最后一个节点的项目，并将其下一个链修改为空以更新包含最后一个节点的链

public interface Collection<T> extends Iterable<T> {
    int size();
    boolean isEmpty();
    void clear();
    boolean contains(T x);
    boolean add(T x);
    boolean remove(T x);
    java.util.Iterator<T> iterator();    
}

The

Collection接口扩展了Iterable接口，并且实现此接口的类可以增强应用于这些类的循环，以观察其所有项.

public static <T> void print(Collection<T> coll) {
    for ( T item : coll ) {
        System.out.println(item);
    }
}

实现Iterator接口的集合需要提供一个iterator方法，通过该方法，每个集合都可以创建并向用户返回一个实现Iterator接口的对象，并将该对象内部当前位置的概念存储起来.

public interface Iterator <T> {
    boolean hasNext();	// 判断下一项是否存在
	T next();			// 调用集合的下一项
    void remove();		// 删除由 next() 最新返回的项
}

public static <T> void print(Collection<T> coll) {
    Iterator<T> itr = coll.iterator();
    while ( itr.hasNext() ) {
        T item = itr.next();
        System.out.println(item);
    }
}

public interface List<T> extends Collection<T> {
    T get(int index);
    T set(int index, T newVal);
    void add(int index, T x);
    void remove(int index);
    ListIterator<T> listIterator(int pos);
}

提供了可增长数组的List ADT实现，该实现可在需要时自动增加基础数组的容量.

提供了List ADT的双链表实现

对于搜索，Collection的contains（）和remove（）方法花费线性时间，并且对于这两种实现方式都是无效的.

public interface ListIterator<T> extends Iterator<T> {
	boolean hasPrevious();
    T previous();
    void add(T x);
    void set(T newVal);
}

堆栈是将插入和删除限制在一个位置的表. 这个位置是桌子的尽头. 它被称为堆栈的顶部，也称为后进先出（LIFO）.

顶部元素是整个模型中唯一可见的元素.

基本操作

任何实现表的方法都可以实现使用ArrayList和LinkedList的堆栈.

基于上述实现的操作可以非常快速且恒定地运行

平衡符号（开括号和右括号），后缀表达式，从中缀到后缀的转换，方法调用（方法调用和方法返回基本上类似于开括号和闭括号）

队列也是一个表. 使用时，在一端执行插入操作，而在另一端执行删除操作. 先进先出（FIFO）.

基本操作

类似于堆栈的情况.

可能的问题: 数组的前面可能有元素出队，并且数据未满. 此时，后向标识符可能会移动到数组的最后一个索引位置，并且下一个排队的元素将无法存储.

解决方案: 循环数组的实现，只要前端或后端到达数组的末尾，它将返回到开头.

根据元素的优先级值确定其弹出顺序. 实质结构是堆结构，而不是线性结构.

定义堆栈的数据结构. 请以这种类型实现一个min函数，该函数可以获取堆栈中的最小元素.

（时间复杂度应为O（1））

应用辅助堆栈

推送规则:

将数据堆栈直接推入辅助堆栈以增加判断力. 如果堆栈为空，则将其直接推入；否则，如果要推送的元素小于顶部元素，则将其推送

弹出规则:

在弹出数据堆栈时判断辅助堆栈的顶部，如果顶部元素与要从数据堆栈中弹出的元素相同，则一起弹出. 否则，仅弹出数据堆栈的顶部. 为了确保两个堆栈的一致性.

public class GetMinDemo {
    Stack<Integer> dataStack = new Stack();
    Stack<Integer> minStack = new Stack();
    public void push(int node) {
        dataStack.push(node);
        if (minStack.isEmpty() || minStack.peek() > node)
            minStack.push(node);
    }
    public void pop() {
        if (minStack.peek() == dataStack.peek())
            minStack.pop();
        dataStack.pop();
    }
    public int top() {
        return dataStack.peek();
    }
    public int min() {
        return minStack.peek();
    }
}

写一个类，该类只能实现具有两个堆栈结构的队列，从而支持队列的基本操作（推，弹出）.

给出操作序列ope的长度n，其中正数表示推送操作，0表示弹出操作，

确保操作顺序合法，并且必须包含弹出操作. 请返回pop的结果序列.

测试样例: [1,2,3,0,4,0], 6
返回：    [1,2]

要点:

如果stackPush想要将数据倒入stackPop中，则必须一次将所有数据倒入stackPush中. 如果stackPop中有数据（非空），则不会发生数据分页行为.

public class Stack2Queue {
    Stack<Integer> stackPush = new Stack<>();
    Stack<Integer> stackPop = new Stack<>();
    public void push(int node) {
        if (stackPop.isEmpty()) {
            stackPop.push(node);
        } else {
            while (!stackPop.isEmpty()) {
                int tmp = stackPop.pop();
                stackPush.push(tmp);
            }
            stackPop.push(node);
            while (!stackPush.isEmpty()) {
                int tmp = stackPush.pop();
                stackPop.push(tmp);
            }
        }
    }
    public int pop() {
        if (stackPop != null)
            return stackPop.pop();
        else return -1;
    }
    public int[] twoStack(int[] ope, int n) {
        int count = 0;
        for(int i = 0; i < n; i++) {
            if (ope[i] == 0)
                count++;
        }
        int[] res = new int[count];
        int j = 0;
        for(int i = 0; i < n; i++) {
            if (ope[i] > 0) {
                push(ope[i]);
            } else res[j++] = pop();
        }
        return res;
    }
}

执行堆栈的相反顺序，但仅使用递归函数和堆栈本身的弹出操作栈和队列，

您不能自己申请其他数据结构.

给定一个整数数组A是给定的堆栈，并给定其大小n，请以相反的顺序返回该堆栈.

通过递归函数传递值

弹出获取堆栈底部元素的功能，并保存堆栈顶部元素，以确定此时堆栈是否为空. 如果为空: 直接返回已保存的堆栈顶部元素. 如果它不为空: 那么将递归调用此函数，并调用在步骤1中获得的堆栈的顶部元素. 将其推回堆栈中并返回到步骤2.2. 递归返回值反转堆栈函数以获取堆栈的底部元素，然后递归调用自身. 除底部元素之外的堆栈以相反的顺序从底部将元素从步骤1再次推到堆栈的顶部.

// 解法 1
// 移除栈底元素并返回
public int getBottom(Stack<Integer> myStack) {
    int res = myStack.pop();
    if (myStack.isEmpty()) {
        return res;
    } else {
        int last = getBottom(myStack);
        // 压入上一个值
        myStack.push(res);
        return last;
    }
}
// 将栈中元素逆序
public void reverse(Stack<Integer> myStack) {
    if (myStack.isEmpty()) return;
    int i = getBottom(myStack);
    reverse(myStack);
    myStack.push(i);
}
// 主调用函数
public int[] reverseStack(int[] A, int n) {
    Stack<Integer> myStack = new Stack<>();
    for (int i = 0; i < n; i++) {
        myStack.push(A[i]);
    }
    reverse(myStack);
    for (int i = 0; i < n; i++) {
        A[i] = getBottom(myStack);
    }
    return A;
}
// 解法 2
public int[] reverseStack1(int[] A, int n) {
    if (n == 0)
        return null;
    int node = A[n - 1];
    reverseStack1(A, n - 1);
    A[A.length - n] = node;
    return A;
}

请编写一个程序以对堆栈进行升序排序（即，最大的元素在堆栈的顶部），

要求临时数据最多使用一个额外的堆栈，但不得将元素复制到其他数据结构中.

给出一个int []数字（其中第一个元素是堆栈的顶部），返回排序后的堆栈.

请注意，这是一个堆栈，这意味着您只能在排序过程中访问第一个元素.

使用辅助堆栈来实现:

辅助堆栈推送规则:

如果辅助堆栈为空，则直接弹出数据堆栈的顶部元素，然后将其推入辅助堆栈. 如果辅助堆栈不为空，则比较辅助堆栈的顶部元素和数据堆栈的顶部元素的大小. 弹出数据堆栈的顶部元素，并将其推入辅助堆栈. 否则，将弹出数据堆栈的顶部元素并将其另存为临时变量. 辅助堆栈中的元素会反复弹出并推入数据堆栈，直到满足为止. 2.1条件下，此时将临时变量推入辅助堆栈中

当数据栈为空时，辅助栈中的所有元素都被推入数据栈以实现排序.

// 解法 1： 利用栈实现
public ArrayList<Integer> twoStacksSort1(int[] numbers) {
    Stack<Integer> helpStack = new Stack<>();
    Stack<Integer> dataStack = new Stack();
    for (int i = 0; i < numbers.length; i++) {
        dataStack.push(numbers[i]);
    }
    while (!dataStack.empty()) {
        if (helpStack.empty() || dataStack.peek() > helpStack.peek()) {
            helpStack.push(dataStack.pop());
        }
        else {
            int temp = dataStack.pop();
            while (!helpStack.empty() && helpStack.peek() > temp) {
                dataStack.push(helpStack.pop());
            }
            helpStack.push(temp);
        }
    }
    for (Integer integer : helpStack) {
        dataStack.push(integer);
    }
    ArrayList<Integer> res = new ArrayList<>();
    while (!dataStack.isEmpty()) res.add(dataStack.pop());
    return res;
}
// 解法 2：利用数组实现
public ArrayList<Integer> twoStacksSort(int[] numbers) {
    int len = numbers.length;
    // 辅助
    int[] help = new int[len];
    int i = 0, j = len, current;
    while (i < len) {
        current = numbers[i++];
        if (j == len || current <= help[j]) {
            help[--j] = current;
        } else if (current > help[j]) {
            while (j < len && current > help[j]) {
                numbers[--i] = help[j++];
            }
            help[--j] = current;
        }
    }
    ArrayList<Integer> res = new ArrayList<>();
    int k = 0;
    while (k < len) res.add(help[len - k++ - 1]);
    return res;
}

有一个整数数组arr，大小为w的窗口从该数组的最左侧滑动到最右侧，

窗口一次向右滑动一个位置. 返回长度为n-w + 1的数组res，

res [i]表示每个窗口状态下的最大值. 以数组[4,3,5,4,3,3,6,7]和w = 3为例.

因为第一个窗口[4,3,5]的最大值是5，所以第二个窗口[3,5,4]的最大值是5，而第三个窗口[5,4]的最大值，3]最大值为5. 第四个窗口[4,3,3]的最大值为4. 第五个窗口[3,3,6]的最大值为6. 第六个窗口[3,6] ，7]的最大值为7.

所以它最终返回[5,5,5,4,6,7].

给出一个整数数组arr及其大小n，并给定w，返回res数组.

确保w小于或等于n，并且数组大小小于或等于500.

使用辅助队列（存储数组索引）:

参赛规则:

如果队列为空或行尾的相应元素大于当前元素，则直接将其插入. 如果行尾的元素小于当前元素，请重复队列直到行尾的相应元素大于当前元素，或在团队为空时插入当前元素以确保头部为Is最大

出发规则:

如果团队负责人的下标超过了窗口，团队将退出团队

保存结果: 团队负责人最多栈和队列，每个窗口保存一个结果

public int[] slide(int[] arr, int n, int w) {
    // 存放数组下标
    ArrayList<Integer> queue = new ArrayList<>();
    int[] res = new int[n - w + 1];
    int count = 0, j = 0;
    for (int i = 0; i < n; i++, count++) {
        // 若队列为空或队尾对应元素大于当前元素直接插入
        if (queue.isEmpty() || arr[queue.get(queue.size() - 1)] > arr[i]) {
            queue.add(i);
        } else {
            // 反复出队直到队尾对应元素大于当前元素或队为空时插入当前元素
            while (!queue.isEmpty() && arr[queue.get(queue.size() - 1)] <= arr[i])
                queue.remove(queue.size() - 1);
            queue.add(i);
        }
        // 若队头元素下标超出窗口范围则移出
        if (queue.get(0) == i - w)
            queue.remove(0);
        // 队头为最大值，每个窗口存一个结果
        if (count == w - 1) {
            res[j++] = arr[queue.get(0)];
            count = w - 2;
        }
    }
    return res;
}

对于没有重复元素的整数数组，请构造一个包含其中元素的MaxTree，

MaxTree被定义为二叉树，其中节点与数组元素一一对应，

同时，对于MaxTree的每个子树，其根元素值都是该子树的最大值.

对于数组中的每个元素，现有的树构建方法

树中的父级是数组中左数大于它的第一个数字，而第一个数大于它的小数字.

如果任一侧都没有大于它的数字，则它是树的根. 请设计一个O（n）算法来实现此方法.

给出一个没有重复元素且大小为n的数组A，请返回一个数组，

其中每个元素是树的原始数组中相应位置处元素的父节点的编号（如果根为-1）.

测试样例： [3,1,4,2], 4  |   返回：[2,0,-1,2]

使用辅助堆栈（存储数组下标）:

如果当前元素小于堆栈的顶部元素，则当前元素的父节点是堆栈的顶部元素. 如果当前元素大于堆栈的顶部元素，则将堆栈的顶部元素从堆栈中移除. 堆栈为空（当前元素没有父节点），当前元素被压入堆栈； b）当前元素小于堆栈的顶部元素，并且与（1）相同的操作.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-148431-1.html