【Java数据结构】手动实现——栈和队列

2021-08-11 07:11:39

【Java数据结构】手动实现——栈和队列【Java数据结构】手动实现——栈和队列

栈（Stack）

概念

实现

队列（Queue）

概念

实现

双端队列

概念

Java中的栈和队列

栈（Stack）

概念

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据在栈顶。

【Java数据结构】手动实现——栈和队列

实现

利用顺序表实现，即使用尾插 + 尾删的方式实现
利用链表实现，则头尾皆可

相对来说，顺序表的实现上要更为简单一些，所以优先用顺序表实现栈。

import java.util.Arrays;

public class MyStack<T> {
    private T[]stack;//数组
    private int top;//当前可以存放数据元素的下标——>栈顶指针

    //用构造函数给定一个初始容量10的数组
    public MyStack( ){
        this.stack = (T[])new Object[10];//泛型不能实例化对象，但是可以类型转换
    }

    //判断栈是否满了
    public boolean isFull(){
        return (stack.length == this.top);
    }

    //判断栈是否为空
    public boolean empty(){
        return this.top == 0;
    }

    //入栈操作
    public void push(T value) {
        //判断栈是否已经满了
        if (isFull()){
            this.stack = Arrays.copyOf(stack,2*stack.length);//满了就扩容成原来容量的两倍
        }

        this.stack[this.top] = value;//给top位置添加元素
        this.top++;//top指针指向下一可用空间
    }

    //出栈操作，并返回弹出（删除）栈顶元素
    public T pop() {
        //先判断栈是否为空
        if (empty()) {
            throw new IllegalStateException("栈为空！");
        }

        //弹出元素
        T ret = this.stack[this.top-1];
        this.top--;
        return ret;//返回删除的元素
    }

    //得到栈顶元素，但是不删除
    public T peek() {

        //判断是否为空
        if (empty()){
            throw new IllegalStateException("栈为空！");
        }
        //返回栈顶元素，不删除
        return this.stack[top-1];
    }

    //展示栈元素
    public void show() {
        for (int i = top-1; i>=0 ; i--){
            System.out.print(stack[i]+" ");
        }
        System.out.println();
    }
}

代码测试：

队列（Queue）

概念

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

入队列：进行插入操作的一端称为队尾（Tail/Rear）

出队列：进行删除操作的一端称为队头（Head/Front）

【Java数据结构】手动实现——栈和队列

实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

【Java数据结构】手动实现——栈和队列

public class MyQueue {
    private Node first;
    private Node last;

    //队列是否为空
    public boolean isEmpty() {
        return this.first == null;
    }

    //入队
    public void offer(int value){
        Node node = new Node(value);
        //尾插法，要判断是否第一次插入
        if (this.first == null){
            this.first = node;
            this.last = node;
        }else{
            this.last.setNext(node);
            this.last = node;
        }
    }

    //出队
    public int poll(){
        //判断是否为空
        if (isEmpty()){
            throw new IllegalStateException("队列为空");
        }
        int ret = this.first.getVal();
        this.first = this.first.getNext();
        return ret;//返回出队元素
    }

    //得到队头元素但是不删除
    public int peek() {
        //不要移动first
        if(isEmpty()) {
            throw new UnsupportedOperationException("队列为空！");
        }
        return this.first.getVal();
    }

    //展示队列
    public void show() {
        Node cur = this.first;
        while(cur != null) {
            System.out.print(cur.getVal()+" ");
            cur = cur.getNext();
        }
        System.out.println();
    }
}