目录

一、栈

1.1 栈的使用

1.2 模拟实现栈

二、队列

2.1 队列的使用

2.2 环形队列

2.3 双端队列

总结


一、栈

只允许在固定的一端进行元素的插入和删除操作的一种特殊线性表。其中进行元素的插入和删除操作的一端称为栈顶,另一端称为栈底。栈遵循先进后出 (后进先出) 原则。

入栈:栈的插入操作称为入栈/进栈/压栈,入数据在栈顶

出栈:栈的删除操作称为出栈,出数据在栈顶

1.1 栈的使用

在 Java 中,提供了 Stack 类来表示栈。

【栈方法】

方法功能
E push(E e)将 e 入栈,并返回
E pop()将栈顶元素出栈,并返回
E peek()获取栈顶元素
int size()获取栈中有效元素个数
boolean empty()判断栈中是否为空

1.2 模拟实现栈

首先定义定义数组来实现栈、usedSize 记录栈中有效元素个数、并定义其默认容量及其构造方法。

    //数组实现栈
    private int[] array;
    //栈中有效元素个数
    private int usedSize = 0;
    //栈默认容量
    private static final int DEFAULT_CAPACITY = 10;

    public MyStack() {
        array = new int[DEFAULT_CAPACITY];
    }

1、push():入栈

    public void push(int e) {
        //若栈已满,则扩容
        if (full()) {
            array = Arrays.copyOf(array, 2*array.length);
        }
        //usedSize标记着栈中元素个数的同时,
        //由于下标从 0 开始计数,元素个数从 1 开始计数
        //所以 usedSize 可以视为栈顶元素下标 +1
        array[usedSize] = e;

        usedSize++;
    }
    //是否已满
    public boolean full() {
        return usedSize == array.length;
    }

 usedSize 做当前可存放元素的下标:

2、pop():栈顶元素出栈,并返回

    public int pop() {
        //若栈为空,则抛异常
        if (empty()) {
            throw new EmptyException("栈为空!");
        }
        //创建变量接收原栈顶元素
        int old = array[usedSize-1];

        //栈顶元素被获取
        usedSize--;

        //返回原栈顶元素
        return old;
    }

3、peek():获取栈顶元素 

    public int peek() {
        //栈中有效个数为 0,抛异常
        if (usedSize == 0) {
            throw new EmptyException("栈为空!");
        }
        //返回栈顶元素
        return array[usedSize-1];
    }

4、size():获取栈中有效元素个数

    public int size() {
        //返回栈中有效元素个数
        return usedSize;
    }

5、empty():判断栈是否为空

    public boolean empty() {
        //若栈中有效个数为 0,则返回 true;反之 false
        return usedSize == 0;
    }


二、队列

队列是只允许在一端进行插入数据操作,在另一端进行删除数据操作的一种特殊线性表。队列遵循先进先出原则。

入队列:进行插入操作的一端称为队尾

出队列:进行删除操作的一端称为队头

2.1 队列的使用

在 Java 中,提供了 Queue 接口来表示队列,其底层是通过链表实现的。由于 Queue 是一个接口,所以实例化队列时必须实例化 LinkedList 对象,因为 LinkedList 实现了 Queue 接口。

【队列方法】

方法功能
boolean offer(E e)入队列
E poll()出队列
E peek()获取队头元素
int size()获取队列内有效元素个数
boolean isEmpty()判断队列内是否为空
import java.util.LinkedList;
import java.util.Queue;

public class QueueDemo {
    public static void main(String[] args) {
        //创建一个空队列
        Queue<Integer> queue = new LinkedList<>();

        //入队列
        queue.offer(11);
        queue.offer(22);
        queue.offer(33);

        //获取队头元素
        System.out.println(queue.peek()); //11

        //获取队列中有效元素个数
        System.out.println(queue.size()); //3

        //出队列:先进先出
        queue.poll(); //11最先进入,故 11出队列

        //再次获取队头元素
        System.out.println(queue.peek()); //22

        System.out.println(queue.size()); //2

        //判断队列是否为空
        System.out.println(queue.isEmpty()); //false
    }
}

2.2 环形队列

环形队列还可以叫做循环队列,顾名思义,即当队列存放元素至队列尾后,此时可存放元素的下标再次循环至队列头,其通常使用数组实现。在生产者消费者模型中,就可以使用循环队列。

在实现环形队列之前,我们先定义变量 front 与 rear,front 表示队列头,rear 表示当前可以存放元素的下标。

此时就需要解决 rear 与 front 相遇时队列为空还是为满的问题,这里我们采用浪费一个空间来判断队列是否已满,即当 rear 的下一个就是 front 时,此时认为队列已满,需等 front 下标元素出队,才可再次存放元素。

同时,还需解决 rear 怎么从 5 下标前往 0 下标的问题,我们可以使用 (rear+1) % length 来决定当前存放元素的下标。

class MyCircularQueue {

    public int[] array; //定义数组实现环形队列
    public int front = 0; //队头,初始为 0
    public int rear = 0; //当前存放元素的下标,初始为 0

    public MyCircularQueue(int size) {
        array = new int[size];
    }

    //入队
    public boolean inQueue(int value) {
        //若队列已满,则 false
        if (isFull()) {
            return false;
        }
        //存入元素
        array[rear] = value;
        //为防止前往 0 下标时出错,故不用 rear++
        rear = (rear+1) % array.length;

        return true;
    }

    //出队
    public boolean outQueue() {
        //若队列为空,则 false
        if (isEmpty()) {
            return false;
        }
        //与 rear 同理,防止前往 0 下标时出错
        front = (front+1) % array.length;

        return true;
    }

    //获取队头元素
    public int Front() {
        //若队列为空,则 -1
        if (isEmpty()) {
            return -1;
        }
        //返回 front 下标元素
        return array[front];
    }

    //获取队尾元素
    public int Rear() {
        //若队列为空,则 -1
        if (isEmpty()) {
            return -1;
        }
        //队尾元素是处于 rear 下标的前一个,
        //若 rear 下标为 0,则队尾元素在队列最大下标处;
        //其余情况,队尾元素处于 rear-1 下标处。
        int tail = rear == 0 ? array.length-1 : rear-1;
        return array[tail];
    }
    
    //判断队列是否为空
    public boolean isEmpty() {
        //若 front 与 rear 相等,则队列为空
        return front == rear;
    }
    
    //判断队列是否已满
    public boolean isFull() {
        //若 rear 的下一个是 front,则队列已满
        return (rear+1) % array.length == front;
    }
}

2.3 双端队列

双端队列是指在队列两端都可以进行入队和出队的操作。Java 中提供 Deque 接口来表示双端队列。

【栈和队列均可使用 Deque 接口】

1、双端队列的线性实现:Deque<Integer> stack = new ArrayDeque<>();

2、双端队列的链式实现:Deque<Integer> queue = new LinkedList<>();


总结

1、栈遵循先进后出 (后进先出) 原则,队列遵循先进先出原则。

2、栈只允许在固定的一端进行元素的插入和删除操作。

3、队列只允许在一端进行插入数据操作,在另一端进行删除数据操作。

4、栈和队列均可使用 Deque 接口。 

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部