恶补基础知识:Java 栈与队列详解

@


前言

请各大网友尊重本人原创知识分享,谨记本人博客:南国以南i


提示:以下是本篇文章正文内容,下面案例可供参考

简介

使用Java实现 栈(Stack)队列(Queue) 的操作是很常见的任务。栈和队列是两种不同的数据结构,它们分别具有特定的操作和行为。

栈是一种 后进先出(LIFO, Last In First Out) 的数据结构。它只允许在栈顶进行添加(push)或删除(pop)元素的操作。类似于羽毛球球桶一样最开始放进去的球需要最后拿出来

Java实现栈的示例代码:

public static void query() {
        Queue<Integer> queue = new LinkedList<>();
        // 入队
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);

        // 查看队首元素
        System.out.println("队首元素: " + queue.peek()); // 不移除队首元素

        // 出队
        while (!queue.isEmpty()) {
            System.out.println("出队元素: " + queue.poll());
        }
    }


    public static void stack() {
        //1、创建栈:使用Stack类(尽管Stack是遗留类,更推荐使用Deque接口的实现如ArrayDeque)或Deque接口(及其实现类如ArrayDeque)来实现栈。
        //Stack<Integer> stack = new Stack<Integer>();
        Deque<Integer> stack = new ArrayDeque<>();

        //2、入栈将元素添加到栈顶
        stack.push(1);
        stack.push(2);
        stack.push(3);

        //3、出栈(Pop):从栈顶移除元素,并返回被移除的元素。Stack类提供了pop()方法用于出栈操作
        int element = stack.pop(); // 返回并移除栈顶元素
        System.out.println(element); // 输出:3


        // 4、访问栈顶元素(Peek):获取栈顶元素,但不对栈进行修改。Stack类提供了peek()方法用于访问栈顶元素
        int outElement = stack.peek(); // 返回栈顶元素但不移除
        System.out.println("栈顶元素: " + outElement); // 输出:3

        // 5、循环出栈
        while (!stack.isEmpty()) {
            System.out.println("出栈元素: " + stack.pop());
        }
        
        /*输出:
        栈顶元素: 3
        出栈元素: 3
        出栈元素: 2
        出栈元素: 1*/
    }

栈的主要应用场景包括:

  1. 函数调用栈:
    在编程语言中,函数调用是通过栈来实现的。当函数被调用时,它的局部变量、参数和返回地址等信息会被压入栈中。当函数执行完毕时,这些信息会从栈中弹出,控制权返回给调用者。

  2. 浏览器的前进后退:
    浏览器的历史记录通常使用栈来管理。当我们浏览网页时,每个访问的页面都会被压入栈中;当我们点击“后退”时,页面会从栈中弹出,返回到上一个页面。

  3. 括号匹配:
    在解析或编译代码时,检查圆括号、花括号等是否匹配是一个常见问题。栈可以用来解决这个问题,每当遇到一个左括号时,就将其压入栈中;每遇到一个右括号时,就检查栈顶元素是否与之匹配,如果匹配则弹出栈顶元素,否则报错。

  4. 撤销操作:
    在许多编辑器或图形界面中,用户可以通过撤销操作回到之前的状态。撤销操作通常使用栈来实现,每次操作都会被压入栈中,当用户执行撤销操作时,栈顶的操作会被弹出并应用于当前状态。

队列

队列是一种 先进先出(FIFO, First In First Out) 的数据结构。它只允许在队尾添加元素(enqueue)和在队首删除元素(dequeue)类似于排队的过程

Java实现队列的示例代码:

public static void queue() {
        // 1、创建队列:我们可以使用Java的集合类LinkedList来实现队列的操作。
        Queue<Integer> queue = new LinkedList<>();
        // 2、入队(Enqueue):将元素添加到队尾。LinkedList类提供了offer()方法用于入队操作。
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);

        //3、出队(Dequeue):从队头移除元素,并返回被移除的元素。LinkedList类提供了poll()方法用于出队操作。
        int element = queue.poll(); // 返回并移除队头元素
        System.out.println(element); // 输出:1

        // 4、访问队头元素(Peek):获取队头元素,但不对队列进行修改。LinkedList类提供了peek()方法用于访问队头元素。
        System.out.println("队首元素: " + queue.peek()); // 不移除队首元素

        // 5、循环出队
        while (!queue.isEmpty()) {
            System.out.println("出队元素: " + queue.poll());
        }

        /*输出:
        队首元素: 1
        出队元素: 1
        出队元素: 2
        出队元素: 3*/
    }

LinkedList中的add方法和offer方法的区别

add方法:‌ add方法属于Collection接口,‌它试图将指定的元素添加到列表中。‌如果添加成功,‌它返回true;‌如果因为某些原因(‌如容量限制)‌添加失败,‌它会抛出IllegalStateException异常。‌在LinkedList中,‌当队列为空时,‌使用add方法可能会因为违反容量限制而报错。‌此外,‌当将LinkedList视为列表使用时,‌通常采用add方法来压入对象。‌

offer方法:‌ offer方法属于Deque接口(‌双端队列)‌,‌它试图将指定的元素插入到队列中。‌如果插入成功,‌它返回true;‌如果因为空间限制无法添加元素,‌则返回false。‌与add方法不同,‌offer方法不会抛出异常,‌而是通过返回值来指示操作是否成功。‌在有容量限制的队列中,‌offer方法优于add方法,‌因为它通过返回false来处理空间不足的情况,‌而不是抛出异常,‌这种方式更加高效。‌

总结来说,‌add方法和offer方法的主要区别在于它们的返回值和异常处理方式。‌add方法可能会因为违反容量限制而抛出异常,‌而offer方法则通过返回值来指示操作是否成功,‌避免了异常处理开销。‌

队列主要应用场景:

  1. 任务调度:
    在多任务处理系统中,任务通常被存储在一个队列中。系统按照任务进入队列的顺序来执行它们,实现了公平的调度。

  2. 消息传递:
    在进程间通信或网络编程中,消息通常被存储在一个队列中。发送者将消息发送到队列的尾部,接收者从队列的头部取出消息进行处理。

  3. 页面请求处理:
    在Web服务器中,多个用户请求可能同时到达。服务器可以将这些请求存储在一个队列中,然后按照请求到达的顺序进行处理。

  4. 广度优先搜索(BFS):
    在图的遍历算法中,广度优先搜索使用队列来存储待访问的节点。算法开始时,将起始节点加入队列。然后,算法循环进行,每次从队列中取出一个节点进行访问,并将其未被访问的邻接节点加入队列。

总结

了解栈和队列的应用场景有助于我们根据实际需求选择合适的数据结构,从而更高效地解决问题。


我是南国以南i记录点滴每天成长一点点,学习是永无止境的!转载请附原文链接!!!

热门相关:腹黑boss霸宠:逃妻,吻我   纨绔毒医   赠我深爱如长风   帝少宠妻有点甜   首席的亿万老婆