• 数据结构——栈和队列互相实现

    数据结构——栈

    这里写目录标题

    队列和栈都是输出输入受限的线性表

    特点：先进后出

    栈是限制线性表中元素的插入和删除，上述操作只能在线性表的同一端进行的一种特殊的线性表就是栈，允许插入和删除的一端，为变化端，称为栈顶，另一端固定一端，称为栈底

    image-20220519192221747

    原理

    判断栈满，top和maxSize-1指向的位置一样

    package com.qcby.datastructure;
public class Stack {
    //定义数组
    private int[] arr;
    //栈的大小
    private int maxSize;
    //表达栈顶(初始没值，为-1)---指向最后一个有效元素
    private int top =-1;
    //初始化
    public Stack(int maxSize) {
        this.maxSize = maxSize;
        this.arr =new int[maxSize];
    }
    //栈满
    public boolean isFull(){
        return top==maxSize-1;
    }
    //栈空
    public boolean isEmpty(){
        return top==-1;
    }
    //入栈
    public void push(int num){
        if (isFull()){
            System.out.println("栈满了，考虑扩容");
            return;
        }
        top++;
        arr[top]=num;
    }
    //出栈
    public int pop(){
        if (isEmpty()){
            //空了要终止函数，用return不太合适，因为这是有类型的函数，所以通过异常抛出
            throw new RuntimeException("栈是空了，没有数据");
        }
        int res =arr[top];
        top--;
        return res;
    }
    //显示栈，从栈顶开始显示元素
    public void list(){
        if (isEmpty()){
            //空了要终止函数，用return不太合适，因为这是有类型的函数，所以通过异常抛出
            throw new RuntimeException("栈是空了，没有数据");
        }
        for (int i=top;i>=0;i--){
            System.out.println(arr[i]);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    Java.util里的Stack
    package qcby;
import java.util.Stack;

public class StackDemo {
    public static void main(String[] args) {
        Stack<String> stack =new Stack<String>();
        System.out.println("现在这个栈是: " + isEmpty(stack));
        stack.push("1");
        stack.push("2");
        stack.push("3");
        stack.push("4");
        stack.push("5");
        System.out.println("现在这个栈是: " + isEmpty(stack));
        System.out.println("栈是" + stack.toString());
        //peek和pop都是操作栈顶元素，当是peek不会弹出，pop会弹出
        System.out.println(stack.peek());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println("栈是" + stack.toString());
        //search找到该元素的索引值
        System.out.println(stack.search("2"));
    }
    public static String isEmpty(Stack<String> stack){
        return stack.empty()? "栈是空的":"栈非空";
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    image-20220520153847541

    数据结构——队列

    特点：先进先出（在数组里面就是头出尾进）

    队列是限制线性表中元素的插入和删除，上述操作只能在线性表的同一端进行的一种特殊的线性表就是队列

    队列使用数组来实现，因为队列的出队、入队是分别从头、尾端来处理的，因此需要两个变量front和rear（分别指向头尾）

    front会随着数据的出队而变化，而rear会随着数据入队而变化

    如果尾指针rear小于maxSize-1，就可以往后移动，然后把数据存在当前rear指向的数组元素上。

    当rear =maxSize-1，队列满

    当front==rear 队列空

    原理
    package com.qcby.datastructure;

public class Queue {
    //定义数组
    private int[] arr;
    //队列的大小
    private int maxSize;
    //队头“指针”
    private int front;
    //队尾“指针”
    private int rear;
    //初始化
    public Queue(int maxSize) {
        this.maxSize = maxSize;
        arr =new int[this.maxSize];
        front =-1;
        rear =-1;
    }
    //队满
    public boolean isFull(){
        return rear==maxSize-1;
    }
    //队空
    public boolean isEmpty(){
        return rear==front;
    }
    //入队
    public void add(int value){
        if (isFull()){
            System.out.println("队满，考虑扩容");
            return;
        }
        rear++;
        arr[rear]=value;
    }
    //出队
    public int remove(){
        if (isEmpty()){
            throw new RuntimeException("队空，没有数据");
        }
        front++;
        return arr[front];
    }
    //显示队列
    public void list(){
        if (isEmpty()){
            throw new RuntimeException("队空，没有数据");
        }
        for (int i=front+1;i<=rear;i++){
            System.out.println("queen:"+"["+i+"]:"+arr[i]);
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    Java.util里的Queue
    package qcby;

import java.util.LinkedList;
import java.util.Queue;

public class QueenDemo {
    public static void main(String[] args) {
        //add()和remove()方法在失败的时候会抛出异常（不推荐）
        Queue<String> queue =new LinkedList<String>();
        //添加元素
        queue.offer("a");
        queue.offer("b");
        queue.offer("c");
        queue.offer("d");
        queue.offer("e");
        System.out.print("队列的元素为: ");
        for (String q :queue){
            System.out.print(q);
            System.out.print(" ");
        }

        System.out.println(" ");
        System.out.println("===");
        System.out.println("poll="+queue.poll());//返回第一个元素，并在队列里删除
        System.out.print("队列的元素为: ");
        for (String q :queue){
            System.out.print(q);
            System.out.print(" ");
        }

        System.out.println(" ");
        System.out.println("===");
        System.out.println("poll="+queue.element());//返回第一个元素
        System.out.println("队列的元素为");
        for (String q :queue){
            System.out.print(q);
            System.out.print(" ");
        }

        System.out.println(" ");
        System.out.println("===");
        System.out.println("poll="+queue.peek());//返回第一个元素
        System.out.println("队列的元素为");
        for (String q :queue){
            System.out.print(q);
            System.out.print(" ");
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    image-20220520155318477

    用俩个栈实现队列

    两个栈，一个栈A，另一个为栈B，栈A的元素入栈后，只要栈A不空，就重复把栈顶元素放入栈B中，这样就可以得到和栈A元素顺序相反的栈B

    image-20220520162243315

    代码实现
    package qcby.StackQueen;

import java.util.Stack;

public class QueenByTwoStack {
    Stack<Integer> stack1 =new Stack<>();
    Stack<Integer> stack2 =new Stack<>();
    //向队列中插入数据
    public void add(Integer num){
        stack1.push(num);
    }
    //获取队列的当前头数据(要出队列)
    public int get(){
        Integer num;
        Integer res =null;
        //将stack1当中的数据放入到stack2
        while (!stack1.empty()){
            //stack1出栈，
            num =stack1.pop();
            //stack2入栈
            stack2.push(num);
        }
        //获取stack2的栈顶元素，即为队列的头数据
        if (!stack2.empty()){
            res = stack2.pop();
        }else {
            throw new RuntimeException("队列已经空了");
        }
        while (!stack2.empty()){
            //stack2出栈，
            num =stack2.pop();
            //stack1入栈
            stack1.push(num);
        }
        return res;
    }
    public static void main(String[] args) {
        QueenByTwoStack queenByTwoStack =new QueenByTwoStack();
        queenByTwoStack.add(1);
        queenByTwoStack.add(2);
        queenByTwoStack.add(3);
        queenByTwoStack.add(4);
        try {
            System.out.println(queenByTwoStack.get());
            System.out.println(queenByTwoStack.get());
            System.out.println(queenByTwoStack.get());
            System.out.println(queenByTwoStack.get());
            System.out.println(queenByTwoStack.get());
        }catch(Exception e) {
            System.out.println(e.getMessage());
        }

    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    image-20220520170546219

    用两个队列实现栈

    image-20220520172909802

    代码实现
    package com.qcby.datastructure.StackQueen;

import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.BrokenBarrierException;

public class StackByTwoQueen {
    Queue<Integer> queue1 =new LinkedList<>();
    Queue<Integer> queue2 =new LinkedList<>();

    public void add(Integer data){
        //queue1添加数据
        queue1.offer(data);
    }
    public int get(){
        Integer data =null;
        //data就是队列的最后一个元素（栈的栈顶）
        while (!queue1.isEmpty()){
            //返回队列第一个元素，并在队列里删除
            data =queue1.poll();
            if (queue1.isEmpty()){
                break;
            }
            //queue2添加数据
            queue2.offer(data);
        }
        //queue2不空
        while (!queue2.isEmpty()){
            queue1.offer(queue2.poll());
        }
        return data;
    }

    public static void main(String[] args) {
        StackByTwoQueen stackByTwoQueen =new StackByTwoQueen();
        stackByTwoQueen.add(1);
        stackByTwoQueen.add(2);
        stackByTwoQueen.add(3);
        System.out.println(stackByTwoQueen.get());
        stackByTwoQueen.get();
        stackByTwoQueen.get();
        stackByTwoQueen.get();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    用数组实现两个栈

  • 相关阅读:
    零基础学Python：Matplotlib用法
    react的different算法
    HashMap不安全后果及ConcurrentHashMap线程安全原理
    刷题学习记录（攻防世界）
    MindSpore：环境问题案例
    编程学习思考
    python+vue+elementui大学生假期志愿者公益网站django
    YoloV5/YoloV7优化：感受野注意力卷积运算（RFAConv），效果秒杀CBAM和CA等 | 即插即用系列
    Oracle 中排序碰到 null 值如何处理
    【工具】html请求 Content-Encoding=br 返回值乱码的问题 解码返回值
  • 原文地址：https://blog.csdn.net/m0_61820867/article/details/126548511