栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

基本的栈和队列

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

基本的栈和队列

文章目录
  • 栈和队列
    • 栈:
    • 栈完整代码
    • 队列
    • 队列完整代码

栈和队列

栈和队列也是线性表

线性表:一次保存单个同类型元素,多个元素之间逻辑上连续

数组,链表,栈,队列,字符串(内部是字符数组 char[]),这些都是线性表。

栈和队列其实是操作受限的线性表

之前的数组和链表,可以在任意位置插入和删除

“栈和队列”,只能在一端插入和删除元素

栈:

(Last In First Out)简称(LIFO),就是"后进先出"的原则

栈只能在一段插入元素,且只能在这一段取出元素,这一端称之为栈顶

栈在生活中的应用有很多

如:无处不在的undo操作,即你按ctrl+z就返回了上次一输入的内容,这其就是栈的应用

普通栈基本就是包含下面三种方法

public class MyStack {
    //记录当前栈中的元素个数
    private int size;
    //实际存储数据的动态数组,在栈中,只能在数组末尾添加和删除元素
    private List date = new ArrayList<>();

    
    public void push(E val){
        date.add(val);
        size++;
    }
}

首先是push(E val),将元素添加到栈中的操作(压栈、入栈),

非常简单,只需要使用动态数组的add方法默认在数组末尾插入元素即可

其次是pop(),弹出栈顶元素的操作

public E pop(){
    if(date.isEmpty()){
        throw new NoSuchElementException("stack is empty cant pop");
    }
    E val = date.remove(size-1);
    size--;
    return val;
}

边界条件是栈是否为空,栈为空就抛出一个异常,返回被删除元素的值

最后就是peek()操作,取出当前栈顶元素但并不删除

public E peek(){
    if(date.isEmpty()){
        throw new NoSuchElementException("stack is empty cant peek");
    }
    return date.get(size-1);
}

利用动态数组的get的方法就能取出当前栈的栈顶元素

栈完整代码
public class MyStack {
    //记录当前栈中的元素个数
    private int size;
    //实际存储数据的动态数组,在栈中,只能在数组末尾添加和删除元素
    private List date = new ArrayList<>();

    
    public void push(E val){
        date.add(val);
        size++;
    }

    
    public E pop(){
        if(date.isEmpty()){
            throw new NoSuchElementException("stack is empty cant pop");
        }
        E val = date.remove(size-1);
        size--;
        return val;
    }

    
    public E peek(){
        if(date.isEmpty()){
            throw new NoSuchElementException("stack is empty cant peek");
        }
        return date.get(size-1);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(date.get(i));
            if(i != size-1){
                sb.append(", ");
            }
        }
        sb.append("] top");
        return sb.toString();
    }
}
队列

相对于栈来说队列实现的子类是比较多的,比如FIFO队列,双端队列Deque,循环队列LoopQueue,优先级队列PriorityQueue等,所以采用接口来定义队列,具体实现由子类决定

队列:(FIFO、First In First Out)

先进先出的数据结构,元素从”队尾“添加到对队列中,元素从”队首“出队列

队列在现实生活中也是非常常见,当你在排队的时候,就是一个队列,先排的人先离开,排在最前面的叫队首,排在最后面的叫队尾

一样是只有三个方法

首先是要有Queue这个接口

public interface Queue {
    //入队
    void offer(E e);
    //出队
    E poll();
    //查看队首元素
    E peek();
    boolean isEmpty();
}

普通的基于链表实现的队列,首先是定义一个链表,一样是保存一个值,然后保存下一个元素的地址

class ListNode{
    E val;
    ListNode next;

    public ListNode(E val) {
        this.val = val;
    }
}

首先是offer(E val)方法,将元素从队尾插入

public class LinkedQueue implements Queue{
    private int size;
    private ListNode head;
    private ListNode tail;
    @Override
    public void offer(E e) {
        ListNode listNode = new ListNode<>(e);
        if(head == null){
            head = tail = listNode;
        }else{
            tail.next = listNode;
            tail = listNode;
        }
        size++;
    }
}

当head为空时,就是头和尾都等于新插入的节点,否则,就是尾插让tail.next先指向新插入的元素,再更新tail为新的队尾即可。

其次时poll()方法,将队首元素弹出

边界条件是当队列为空的情况,抛出一个异常即可,当队列不为空,就只需要更新队首即可,然后将先的队首删除

public E poll() {
    if(isEmpty()){
        throw new NoSuchElementException("queue is empty cant poll");
    }
    E e = head.val;
    ListNode listNode = head;
    head = head.next;
    listNode.next = listNode = null;
    size--;
    return e;
}

最后就是peek()方法,取出当前队首元素但不删除

public E peek() {
    if(isEmpty()){
        throw new NoSuchElementException("queue is empty cant peek!");
    }
    return head.val;
}
队列完整代码
class ListNode{
    E val;
    ListNode next;

    public ListNode(E val) {
        this.val = val;
    }
}

public class LinkedQueue implements Queue{
    private int size;
    private ListNode head;
    private ListNode tail;
    @Override
    public void offer(E e) {
        ListNode listNode = new ListNode<>(e);
        if(head == null){
            head = tail = listNode;
        }else{
            tail.next = listNode;
            tail = listNode;
        }
        size++;
    }

    @Override
    public E poll() {
        if(isEmpty()){
            throw new NoSuchElementException("queue is empty cant poll");
        }
        E e = head.val;
        ListNode listNode = head;
        head = head.next;
        listNode.next = listNode = null;
        size--;
        return e;
    }

    @Override
    public E peek() {
        if(isEmpty()){
            throw new NoSuchElementException("queue is empty cant peek!");
        }
        return head.val;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/933724.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号