Java学习苦旅(十七)——栈和队列

2024-01-02 14:33:56

本篇博客将详细讲解Java中的栈和队列。

概念

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

压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶

出栈:栈的删除操作叫做出栈,出数据在栈顶

image-20220301134330322

Java中Stack常用方法

方法解释
E push(E item)压栈
E pop()出栈
E peek()查看栈顶元素
boolean empty()判断栈是否为空

代码实现

使用顺序表实现push(),pop(),peek()

import java.util.*;

public class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack() {
        this.elem = new int[5];
    }

    public void push(int val) {
        if(isFUll()) {
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.usedSize] = val;
        this.usedSize++;
    }

    public boolean isFUll() {
        return this.usedSize == this.elem.length;
    }

    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空");
        }
        int oldVal = this.elem[usedSize-1];
        this.usedSize--;
        return oldVal;
    }

    public boolean isEmpty() {
        return this.usedSize == 0;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空");
        }
        return this.elem[usedSize-1];
    }
}

队列

概念

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)。

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

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

image-20220301155409751

队列常用方法对比

Queue

错误处理抛储异常返回特殊值
入队列add(e)offer(e)
出队列remove()poll()
队首元素element()peek()

Deque

头部/尾部头部元素(队首)尾部元素(队尾)
错误处理抛出异常返回特殊值抛出异常返回特殊值
入队列addFirst(e)offerFirst(e)addLast(e)offerLast(e)
出队列removeFirst()pollFirst()removeLast()pollLast()
获取元素getFirst()peekFirst()getLast()peekLast()

代码实现Queue

class Node {
    public int val;
    public Node next;
    public Node(int val) {
        this.val = val;
    }
}

public class MyQueue {
    public Node head;
    public Node last;

    /**
     * 尾插法
     * @param val
     */
    public void offer(int val) {
        Node node = new Node(val);
        if (head == null) {
            head = node;
            last = node;
        } else {
            last.next = node;
            last = last.next;
        }
    }

    public int poll() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        int oldVal = head.val;
        this.head = head.next;
        return oldVal;
    }

    public boolean isEmpty() {
        return this.head == null;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return head.val;
    }
}

结尾

本篇博客到此结束。
上一篇博客:Java学习苦旅(十六)——List
下一篇博客预告:Java学习苦旅(十八)——详解Java中的二叉树

文章来源:https://blog.csdn.net/m0_53408775/article/details/135338740
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。