当前位置：首页 > article >正文

【算法】---栈与队列基础

article 2024/10/22 8:26:32

前置准备

数据结构篇：学习过栈与队列这两种基本数据结构
前面会迅速回顾栈与队列的使用

本篇以Java为主，其它语言可自行对应内置的栈与队列容器。

栈

栈是一种后进先出的容器。
如下图，栈只有一个开口。

栈顶：栈的开口处，所有的插入（push）和删除（pop）操作都只能在栈顶进行。
栈底：栈的最底部，没有办法直接访问栈底的数据，必须通过逐步“弹出”栈顶元素才能到达栈底。
后进先出（LIFO）：最后放入栈中的元素会最先被取出，像叠盘子一样，最新放上去的盘子最先被拿走。
增删查询操作只允许在栈顶进行。
由于必定操作最近进入栈的数，因此栈的特性是后进先出。
Java中的Stack：Java—Stack
全局静态数组实现:解算法题常用，因为其常数时间快且可以空间复用算法题效率由于语言自带的栈，比如纯C选手就可以用这个迅速手搓一个栈不需要封装直接用。

class Stack {
	public  int[] stack;
	public int r;
	public Stack(int n) {
		stack = new int[n];
		r = 0;
	}
	public void push(int val) {
		stack[r++] = val;
	}
	public int pop() {
		return stack[--r];
	}
	public int peek() {
		return stack[r-1];
	}
	public boolean isEmpty() {
		return r==0;
	}
	
	public int size() {
		return r;
	}
}

Java中的LinkedList(双向链表)和ArrayDeque(双端队列）：两者也支持栈操作，具体查看手册。

队列

队列是一种先进先出的容器
在这里插入图片描述

Java中的Queue接口位于java.util包中，它有两个常见实现类可以充当队列。
LinkedList,ArrayDeque.

offer(E e)：将指定元素插入队列尾部，如果插入成功返回true。
poll()：移除并返回队首元素，如果队列为空则返回null。
peek()：获取队首元素但不移除，如果队列为空返回null。
isEmpty()：判断队列是否为空。
size():获取队列的长度

1. `LinkedList`使用

LinkedList类可以用来实现队列。支持队列操作。

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        // 使用LinkedList实现队列
        Queue<Integer> queue = new LinkedList<>();
		// 队列是否为空·
		System.out.println(queue.isEmpty());
        // 入队操作
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
		
        // 查看队首元素（不移除）
        System.out.println("队首元素: " + queue.peek());

        // 出队操作
        System.out.println("移除的元素: " + queue.poll());
		// 队列长度·
		System.out.println(queue.size());
        // 查看出队后的队列
        System.out.println("队首元素: " + queue.peek());
    }
}

2. `ArrayDeque`

ArrayDeque 是一个基于数组的双端队列，它可以高效地作为队列或栈使用。

import java.util.ArrayDeque;
import java.util.Queue;

public class ArrayDequeExample {
    public static void main(String[] args) {
        // 使用ArrayDeque实现队列
        Queue<String> arrayDeque = new ArrayDeque<>();
		// 队列是否为空·
		System.out.println(arrayDueue.isEmpty());
        // 入队操作
        arrayDeque.offer("A");
        arrayDeque.offer("B");
        arrayDeque.offer("C");

        // 查看队首元素
        System.out.println("队首元素: " + arrayDeque.peek());

        // 出队操作
        System.out.println("移除的元素: " + arrayDeque.poll());
		// 队列长度
		System.out.println(arrayDueue.size());
        // 查看出队后的队列
        System.out.println("队首元素: " + arrayDeque.peek());
    }
}

3. 常数时间快的数组实现

如果题目确定最大数据量是5000，那么意味着这个队列最多进入5000个元素。

public class MyQueue {
	public static int MAX = 5000;
	public int[] queue = new int[MAX];
	public int l,r,size;
	public MyQueue() {
		l = r = size = 0;
	}
	//[l,r)是有效数据， l==r意味队列为空
	public void offer(int val) {
		queue[r++] = val;
		size++;
	}
	
	public int poll() {
		size--;
		return queue[l++];
	}
	public int peek() {
		return queue[l];
	}
	public int size() {
		return size;
	}
	
	public boolean isEmpty() {
		return l==r;//或者size==0
	}
	public static void main(String[] args) {
		MyQueue queue = new MyQueue();
		System.out.println(queue.isEmpty());
		queue.offer(1);
		queue.offer(2);
		queue.offer(3);
		System.out.println("queue.size():"+queue.size());
		System.out.println(queue.poll());
		System.out.println("queue.size():"+queue.size());
		System.out.println(queue.poll());
		
	}
}

MAX取决于算法题的测试数据量。
这里没有引入多余的检查可自行补充。
事实上，这个类都不用封装，只需要MAX,queue数组，l,r这3个字段就可以直接充当队列解题，而且常数时间也优于Java自带的Queue的两个实现类。
C语言选手采用这种写法，时间性能最佳。

环形队列实现

设计循环队列
测试链接

//本题接口
/
class MyCircularDeque {

    public MyCircularDeque(int k) {

    }
    
    public boolean insertFront(int value) {

    }
    
    public boolean insertLast(int value) {

    }
    
    public boolean deleteFront() {

    }
    
    public boolean deleteLast() {

    }
    
    public int getFront() {

    }
    
    public int getRear() {

    }
    
    public boolean isEmpty() {

    }
    
    public boolean isFull() {

    }
}

解决方案
阅读题目。
1. 引入size,limit字段，方便维护。
1. 先实现isEmpty(),isFull()方法。
1. 设计[l,r)区间，l指向当前有效数据，r当前第一个无效数据。，插入，先左移动后插入，r先插入再往后移动。注意数组边界处理，使得整个数组循环起来。
1. 删除同3，但只需要挪动l或者r，注意边界。
1. getFront(),getRear()方法中，如果队列为空要返回-1，否则返回队列中对应的值。再次强调l指向当前有效数据，r当前第一个无效数据.

public int[] queue;
	private int l,r,limit,size;
	//limit:队列的最大容量
	//size：队列的长度
	//[l,r) 队列区间。

    public MyCircularDeque(int k) {
    	queue = new int[k];
    	l = r = size = 0;
    	limit = k;
    }
    
    public boolean insertFront(int value) {
    	if(isFull()) {
    		return false;
    	}
    	queue[l = l==0?limit-1:l-1] = value;
    	size++;
    	return true;
    }
    
    public boolean insertLast(int value) {
    	if(isFull()) {
    		return false;
    	}
    	queue[r] = value;
    	r = r==limit-1?0:r+1;
    	size++;
    	return true;
    }
    
    public boolean deleteFront() {
    	if(isEmpty()) {
    		return false;
    	}
    	l = l==limit-1?0:l+1;
    	size--;
    	return true;
    }
    
    public boolean deleteLast() {
    	if(isEmpty()) {
    		return false;
    	}
    	r = r==0?limit-1:r-1;
    	size--;
    	return true;
    }
    
    public int getFront() {
    	return isEmpty()?-1:queue[l];
    }
    
    public int getRear() {
    	return isEmpty()?-1:queue[r==0?limit-1:r-1];
    }
    
    public boolean isEmpty() {
    	return size == 0;
    }
    
    public boolean isFull() {
    	return size == limit;
    }