Java之栈与队列(双端队列,优先级队列)及相关API

雨点打透心脏的1/2处 2024-03-27 14:23 0阅读 0赞

**目录**

一.栈

1.Java中关于栈的API

二.队列

三.双端队列

1.ArrayDeque

2.LinkedList

四.优先队列

1.大顶堆小顶堆

2.堆的基本操作

上浮+添加元素

下沉+删除

3.常见的方法

--------------------

## 一.栈 ##

### 1.Java中关于栈的API ###

> Stack<Object> stack = new Stack<>();

入栈 stack.push(1)

出栈 stack.pop();

栈顶元素 stack.peek()

栈的元素个数 stack.size()

栈是否为空 stack.empty()

## 二.队列 ##

可以使用双端队列实现,因为Queue是一个接口,无法直接实现

## 三.双端队列 ##

双端队列,既可以实现栈的功能,也可以实现队列的功能

### 1.ArrayDeque ###

ArrayDeque是基于动态数组实现的

**作为栈使用的常用的操作**

入栈操作:

> deque.push(1) deque.addFirst(1) deque.offerFirst(1)

出栈操作

> deque.removeFirst() deque.remove() deque.pop()

查看栈顶元素

> deque.peek() deque.peekFirst()

**作为队列使用的常用的操作**

入队列操作:

> deque.add(1) deque.addLast(1) deque.offerLast(1) deque.offer(1)

出队列操作:

> deque.poll() deque.removeLast()

查看队列末端操作:

> deque.peekLast()

**查看双端队列的长度**

> int size = deque.size();

**判断队列是否为空**

> boolean empty = deque.isEmpty();

### 2.LinkedList ###

LinkedList是基于链表实现的

**与ArrayDeque几乎一样**

## 四.优先队列 ##

### 1.大顶堆小顶堆 ###

堆:堆是一种非线性结构，可以把堆看作一棵**二叉树**，也可以看作一个**数组**

**大顶堆**:每个节点的值都**大于**或等于其左右孩子的值

arr\[i\] >= arr\[2i+1\] && arr\[i\] >= arr\[2i+2\]

**小顶堆**:每个节点的值都**小于**或等于其左右孩子的值

arr\[i\] <= arr\[2i+1\] && arr\[i\] <= arr\[2i+2\].

### 2.堆的基本操作 ###

这里拿小顶堆举例

#### 上浮+添加元素 ####

**上浮**是往二叉堆添加元素用到的操作，它其实是**不断的调整k的位置为父元素的位置**直到满足条件为止

// 用数组表示堆
    Object []objs = new Object[10];
    /**
     * 上浮：
     * k表示堆的最后一个位置；
     * obj表示将要插入的元素。
     */
    private void siftUp(int k, Object obj) {
        // 1. 判断k是否为根元素的位置0，如果是则直接赋值
        while(k>0) {
             // 2. 获取父元素的位置,parent = (k-1)/2
             int parent = (k-1) >>> 1;
             // 3. 如果父元素的优先级大于等于obj，跳出循环并插入obj
             if(objs[parent] >= obj) {
                 break;
    		 }
    		 // 4. 如果父元素的优先级小于obj，将父元素赋值到k的位置，更改k为父元素的位置，继续循环
    		 objs[k] = objs[parent];
    		 k = parent;
        }
        // 5. 为obj赋值
        objs[k] = obj;
    }
    /**
     * 添加元素，不考虑数组扩容的情况。
     * 假设size表示当前堆包含的元素个数（注意不一定等于上面定义的10）
     */
    public void add(Object obj) {
        if(size==0) {
            objs[0] = obj;
        } else {
            siftUp(size, obj);
            size++;
    	}
    }

#### 下沉+删除 ####

// 用数组表示堆
    Object []objs = new Object[10];
    /**
     * k被删除元素的位置；
     * obj堆的最后一个元素；
     *  假设size为当前堆包含元素的个数（不一定是上面定义的10）
     */
    private void siftDown(int k, Object obj) {
        // 1. 找到最后一个元素的父节点的位置, (最后一个元素位置-1) / 2
        int parent = (size-1-1) >>> 1;
        // 2. 判断k是否在父节点位置之后，如果在之前则需要下沉操作
        while(k <= parent) {
        	// 3.获取k的左右子节点的位置
        	int left = k<<<2 +1;
        	int right = left+1;
        	// 4.选择左右子节点中优先级最高的一个
        	int best;
        	if (objs[left] > objs[right]) {
    			best = left;
    		} else {
    			best = right;
    		}
    		// 5.判断obj和best的优先级谁高。如果obj优先级高，则跳出循环直接赋值，否则继续下沉
    		if (obj >= objs[best]) {
    			break;
    		}
    		objs[k] = objs[best];
    		k = best;
        }
        // 6.赋值
        objs[k] = obj;
    }
    
    /**
     * 删除第p个元素。
     */
    public void remove(int p) {
        // 1.获取最后一个元素
        Object obj = objs[size-1];
        // 2.如果p不等于最后一个元素
        if (p != size-1) {
    		// 3.把最后一个元素和p进行下沉操作
        	siftDown(p, obj);
        	if(objs[p] == obj) {
    			// 4. 上浮
    			siftUp(p, obj);
    		}
    	}
    	size--;
    }

### 3.常见的方法 ###

初始化

> //小顶堆
> 
> PriorityQueue<Integer> queue = new PriorityQueue<>();
> 
> //大顶堆
> 
> PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)->b-a);

入队列

> queue.add(1) queue.offer(1)

出队列

> queue.remove() queue.poll()

其他基本和上面的一样

**注意:如果遍历整个队列的话,这个队列的元素并不是(小顶堆来说)按从小到大的顺序排列的,只不过是队列首的元素一定是最小的,每次出队列的时候,它其中的元素都会进行一个上浮和下沉的操作,但是如果你每次都出队列,出队列的元素顺序一定是按顺序进行出来的**