<返回更多

结构与算法:队列和栈结构

2020-09-09    
加入收藏

一、队列结构

1、基础概念

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

2、特点描述

队列是一个有序列表,可以用数组或是链表来实现,遵循先进先出的原则。即:先进入队列的数据,会先取出;后进入队列的数据,要后取出;即FIFO原则。

队列示意图

结构与算法:队列和栈结构

 

出队列示意图

结构与算法:队列和栈结构

 

通过上述两张图解,不难发现队列结构的一些特点:

队列结构的核心是对容器内是否空、是否满标志的判断算法,即容器为空不可再取,容器已满无法再存;该算法结构在仓储领域的适应非常广泛。

3、消息队列

消息队列就是基于数据结构中的“先进先出”策略实现的,将消息以排队的方式放入队列中,然后出队列被消费:

结构与算法:队列和栈结构

 

有时候某类消息消费需要有顺序控制,即可以对消息中的公共ID做取模处理,即把某类消息都置于一个队列中即可。

4、API使用案例

LinkedList类实现Queue队列接口,因此可以基于LinkedList模拟队列效果。

import JAVA.util.LinkedList;
import java.util.Queue;
public class M01_Queue {
    public static void main(String[] args) {
        // 入队列
        Queue<String> queue = new LinkedList<>();
        queue.add("head") ;
        queue.add("middle") ;
        queue.add("tail") ;
        // 当队列出数据之后,size是不断变化的
        int queueSize = queue.size() ;
        int loop = 0 ;
        // 根据队列大小,不断出队列
        while (loop < queueSize) {
            System.out.println(queue.poll());
            System.out.println(queue);
            loop ++ ;
        }
    }
}

二、栈结构

1、基础概念

栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈(push),它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈(pop),它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

2、特点描述

栈是一个先入后出的有序列表,添加和删除只能在栈顶端(Top)操作,另一端为固定的一端,称为栈底(Bottom)。

入栈示意图

结构与算法:队列和栈结构

 

出栈示意图

结构与算法:队列和栈结构

 

通过上述两张图解,栈结构的一些特点如下:

基于栈的定义可知,最先放入栈中元素在栈底,最后放入的元素在栈顶,从栈容器中而删除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除。

3、递归应用

栈在Java编程中的常见应用,(1)子程序的调用:在跳往子程序前,会将下个指令的地址存到堆栈中,直到子程序执行完后再将地址取出,退回到原来的程序中;(2)处理递归调用:和子程序的调用类似,除了存储下一个指令的地址外,也要将参数、区域变量等数据存入堆栈中。

4、API使用案例

Stack栈API是Vector的一个子类,它实现了一个标准的后进先出的栈,堆栈只定义了默认构造函数,用来创建一个空栈,堆栈除了包括由Vector定义的所有方法,也定义了自己的一些方法。

import java.util.Stack;
public class M02_Stack {
    public static void main(String[] args) {
        // 入堆栈
        Stack<String> stack = new Stack<>() ;
        stack.push("First") ;
        stack.push("Second") ;
        stack.push("Third") ;
        int stackSize = stack.size() ;
        int loop = 0 ;
        // 根据栈大小,不断出栈
        while (loop < stackSize) {
            System.out.println(stack.pop());
            System.out.println(stack);
            loop ++ ;
        }
    }
}
声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍最近更新
更多资讯 >>>