【数据结构】栈和队列

xxxflower

发布于 2023-04-16 17:45:55

2180

发布于 2023-04-16 17:45:55

文章被收录于专栏：《数据结构》《数据结构》

?1.栈（Stack）

?1.1概念

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

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

?1.2栈的使用

?1.3栈的模拟实现

顺序栈：（数组实现的栈）

import java.util.Arrays;

public class MyStack {
    public int[] elem;
    public int usedSize;
    public static final int DEFAULT_SIZE = 10;

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

    public int push(int val){
        if(isFull()){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        this.elem[usedSize] = val;
        usedSize++;
        return val;
    }
    public boolean isFull(){
        if(usedSize == elem.length){
            return true;
        }
        return false;
    }
    public int pop(){
        if(isEmpty()){
            throw new IsEmptyExpection("栈为空！");
        }
        int ret = elem[usedSize-1];
        usedSize--;
        return ret;
    }
    public  boolean isEmpty(){
        return usedSize == 0;
    }
    public int peek(){
        if(isEmpty()){
            throw new IsEmptyExpection("栈为空！");
        }
        return elem[usedSize-1];
    }

    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(11);
        myStack.push(22);
        myStack.push(33);
        myStack.push(44);
        System.out.println(myStack.peek());
        System.out.println(myStack.pop());
        System.out.println(myStack.peek());
    }
}

栈的实现可以有多种方式，比如顺序栈，链式栈。双向链表实现的链式栈可以实现多种方向的先进后出。较为方便。

?1.4概念区分

栈，虚拟机栈，栈帧有什么区别？栈：是一种先进后出的数据结构。虚拟机栈：是JVM的一块内存空间。栈帧：是在调用函数的过程中，在Java虚拟机栈上开辟的一块内存。

?2.队列（Queue）

?2.1概念

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstIn First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear）出队列：进行删除操作的一端称为队头（Head/Front)

?2.2队列的使用

在Java中，Queue是个接口，底层是通过链表实现的。

注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。（接口不能被实例化！）

?2.3队列模拟实现

public class MyQueue {
    static class ListNode{
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode tail;
    public int usedSize;
    public void offer(int val){
        //尾插法
        ListNode node = new ListNode(val);
        if(head == null){
            head = node;
            tail = node;
        }else {
            tail.next = node;
            tail = tail.next;
        }
        usedSize ++;
    }
    public int poll(){
        //头删法
        if(isEmpty()){
            throw new IsEmptyExpection("队列为空！");
        }
        int ret = head.val;
        head = head.next;
        if(head == null){
            tail = null;
        }
        usedSize--;
        return ret;
    }
    public boolean isEmpty(){
        return usedSize == 0;
    }
    public int peek(){
        if(isEmpty()){
            throw new IsEmptyExpection("队列为空！");
        }
        return head.val;
    }
    public int getUsedSize(){
        return usedSize;
    }

    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.offer(11);
        myQueue.offer(22);
        myQueue.offer(33);
        myQueue.offer(44);
        System.out.println(myQueue.peek());
        System.out.println(myQueue.poll());
        System.out.println(myQueue.peek());
        System.out.println(myQueue.getUsedSize());
    }
}

?2.4循环队列

实际中我们有时还会使用一种队列叫循环队列。环形队列通常使用数组实现。

public class MyCirleQueue {
    public int[] elem;
    public int front;//队头
    public int rear;//队尾

    public MyCirleQueue(int k){
        this.elem = new int[k];
    }

    public boolean enQueue(int val){
        if(isFull()){
            return false;
        }
        elem[rear] = val;
        rear = (rear+1) % elem.length;
        return true;
    }
    public boolean isFull(){
        return (rear+1) % elem.length == front;
    }
    public boolean deQueue(){
        if(isEmpty()){
            throw new IsEmptyExpection("队列为空！");
        }
        front = (front+1) % elem.length;
        return true;
    }
    public boolean isEmpty(){
        return front == rear;
    }
    public int Front(){
        if(isEmpty()){
            throw new IsEmptyExpection("队列为空！");
        }
        return elem[front];
    }
    public int Rear(){
        if(isEmpty()){
            throw new IsEmptyExpection("队列为空！");
        }
        int index = rear == 0 ? elem.length-1 : rear-1;
        return elem[index];
    }
}