设为首页 加入收藏

TOP

C语言 队列(循环队列)(一)
2019-08-13 05:39:25 】 浏览:17
Tags:语言 队列 循环

线性结构:有且只有一个根节点,且每个节点最多有一个直接前驱和一个直接后继的非空数据结构


非线性结构:不满足线性结构的数据结构


队列


队列一般分为两类:链式队列和顺序队列


         链式队列---链式队列即用链表实现的队列


         顺序队列---顺序队列是用数组实现的队列,顺序队列通常必须是循环队列


1、基本概念:


  队列是指允许在一端进行插入,在另一端进行删除的线性表,又称“先进先出”的线性表


  队列是一种特殊的线性结构,它只允许在队列的首部(head)进行删除操作,这称为出队


  队尾:允许插入的一端,用尾指针指向队尾元素的后一位置


  队首:允许删除的一端,用头指针指向头元素


循环队列(顺序队列)的实现:


#include <stdio.h>


#define LENGTH 11    /*定义数组最大长度 */
#define OUT 1        /* 出队 */
#define GET 2        /* 入队 */
struct queue
{
    int data[LENGTH];
    int head;    /* 队首 */
    int tail;    /* 队尾 */
};
/* 循环队列的实现 */
main()
{
    struct queue q;
    int i;
    int kk = 0;
    /* 初始化队列 */
    q.head = q.tail = 0;    /*队首队尾初始化 */
    /* 依次插入10个数 */
    for (i = 0; i < LENGTH - 1; i++)
    {
        scanf_s("%d", &q.data[q.tail]);
        q.tail = (q.tail + 1) % LENGTH;
    }
    while (1)
    {
        if (q.head == q.tail)
        {
            printf("队列已空");
            break;
        }
        printf("出队:1\n入队:2\n");
        scanf_s("%d", &kk);
        if (kk == OUT)
        {
           
            q.head = (q.head + 1) % LENGTH;
        }
        else if (kk == GET)
        {
            if (q.head == (q.tail + 1) % LENGTH)
            {
                printf("队列已满");
                break;
            }
            printf("输入入队元素:\n");
            scanf_s("%d", &q.data[q.tail]);
            q.tail = (q.tail + 1) % LENGTH;
        }


        if (q.tail != q.head)
        {
            printf("队列中剩余元素:");
            for (i = q.head; ;)
            {
                printf("%d ", q.data[i]);
                i = (i + 1) % LENGTH;
                if(i == q.tail)
                {
                    putchar('\n');
                    break;
                }
            }
        }
    }
  68


    return 0;
}


2、为什么顺序队列通常必须是循环队列


循环队列是针对顺序队列中最大内存空间有限的一种解决方法,当队列(数组)不可再插入新元素但队列的实际可用空间并未占满的问题的一种合理的解决方案


3、与普通顺序队列的区别


普通顺序队列在插入新元素(入队)时为q.tail++,删除旧元素(出队)时为q.head++(q.tail和q.head都为int型,但为了描述方便这里说成指针),在出队后再想插入新元素且此时q.tail在数组的末尾即最后一位就会出现实际可用空间并未占满但无法插入新元素的问题,强行插入会造成数
编程开发网

首页 上一页 1 2 下一页 尾页 1/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇链表(单向链表的建立、删除、插.. 下一篇C语言文件操作(FILE)与常用文件操..