草庐IT

队列的链式表示和实现(链队)

li水台 2023-09-21 原文

链队：队列的链式表示和实现

相应函数定义

InitQueue(&Q);                  构造空队列
DestroyQueue(&Q);               销毁队列
ClearQueue(&S);                 清空队列
QueueEmpty(S);                  判空.空-TRUE
QueueLength(Q);                 取队列长度
GetHead(Q, &e);                 取队头元素
EnQueue(&Q, e);                 入队列
DeQueue(&Q, &e);                出队列
QueueTraverse(Q, visit());      遍历

头文件、宏定义

#include<stdlib.h>      // 使用exit(0)时需要引用头文件
#define MAXSIZE 100
#define ElemType int
// 以下为使用Status的配套操作
#define Status int
#define OK 1
#define Error 1

定义结构体

#define ElemType int 
typedef struct QNode        // 当定义链式结构(需要定义指针时),记得需要再struct后面加类名
{
    ElemType data;
    struct QNode* next;     // 这个记得要写对,就算定义链式结构中next指针时记得加struct
}QNode, *QueuePtr;

typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

链队初始化

  • step 1 ： 生成新节点作为头结点，队头和队尾指针都指向此结点。
  • step 2 : 头结点的指针域取为NULL
Status InitQueue(LinkQueue& Q)
{
    // 生成新节点作为头结点，对头和队尾指针指向该结点
    Q.front = Q.rear = new QNode;
    Q.front->next = NULL;   //头结点的指针与置空
    return OK;
}

判断链队是否为空

bool EmptyQueue(LinkQueue Q)
{
    return Q.front == Q.rear;
}

求链队的队头元素

  • 记得判断队列是否非空
Status GetHeadQueue(LinkQueue Q, ElemType& e)
{
    if (Q.front == Q.rear) return Error;  // 判断队列是否非空
    e = Q.front->data;
    return OK;
}

链队入队

  • step 1：为入队元素分配结点空间，用指针p指向
  • step 2：将新结点数据域置为e，指针域置为空
  • step 3：将新结点插入到队尾
  • step 4：修改队尾指针为p
Status EnQueue(LinkQueue& Q, ElemType e)
{
    // 链队不需要判断是否队满
    QNode* p = new QNode;   // 为入队元素分配结点空间，用指针p指向
    p->data = e;            // 将新结点数据域置为e
    p->next = NULL;
    Q.rear->next = p;       // 将新结点插入到队尾
    Q.rear = p;             // 修改队尾指针
    return OK;
}

思考：链队**需要头结点**，因为当没有头结点时，我们需要判断是否为第一个结点，如果为第一个结点，那么就将`front`以及`rear`指针指向第一个结点，

链队出队

  • step 1：判断队列是否为空，若空着返回Error
  • step 2：临时保存队头元素的空间，已备释放
  • step 3：修改头结点的指针域，使其指向下一个结点
  • step 4：判断出队元素是否为最后一个元素，若是，则将队尾指针重新赋值，指向头结点。
  • step 5：释放原始队头元素的空间
Status DeQueue(LinkQueue& Q, ElemType& e)
{
    if (Q.front == Q.rear) return Error;
    QNode* p = new QNode;
    p = Q.front->next;                  // p 指向首元结点
    e = Q.front->data;                  // e保存队头结点的数据域
    Q.front = Q.front->next;            // 修改头结点的指针域
    if (Q.rear == p) Q.rear = Q.front;  // 若删的是最后一个元素，则修改队尾指针指向头结点
    delete p;                           // 释放原队头元素的空间
    return OK;
}

思考：链队**需要头结点**，因为当没有头结点时，如果链队出完后为空，那么我需要将`front`和`rear`指针置空，又会多一步判断。

销毁链表

  • 将rear指针当做第三方指针，用于记录front->next指针，然后删除前一个指针，直到front指针为空，那么就删除完了。
Status DestroyQueue(LinkQueue& Q)
{
    while (Q.front)
    {
        Q.rear = Q.front->next;
        delete Q.front;
        Q.front = Q.rear;
    }
    return OK;
}
和实队列codefrontpre

有关队列的链式表示和实现(链队)的更多相关文章

  1. ruby - 分布式事务和队列，ruby，erlang，scala - 2

    我有一个涉及多台机器、消息队列和事务的问题。因此，例如用户点击网页，点击将消息发送到另一台机器，该机器将付款添加到用户的帐户。每秒可能有数千次点击。事务的所有方面都应该是容错的。我以前从未遇到过这样的事情，但一些阅读表明这是一个众所周知的问题。所以我的问题。我假设安全的方法是使用两阶段提交，但协议(protocol)是阻塞的，所以我不会获得所需的性能，我是否正确？我通常写Ruby，但似乎Redis之类的数据库和Rescue、RabbitMQ等消息队列系统对我的帮助不大——即使我实现某种两阶段提交，如果Redis崩溃，数据也会丢失，因为它本质上只是内存。所有这些让我开始关注erlang和

  2. Ruby - 如何将消息长度表示为 2 个二进制字节 - 2

    我正在使用Ruby，我正在与一个网络端点通信，该端点在发送消息本身之前需要格式化“header”。header中的第一个字段必须是消息长度，它被定义为网络字节顺序中的2二进制字节消息长度。比如我的消息长度是1024。如何将1024表示为二进制双字节？ 最佳答案 Ruby(以及Perl和Python等)中字节整理的标准工具是pack和unpack。ruby的packisinArray.您的长度应该是两个字节长，并且按网络字节顺序排列，这听起来像是n格式说明符的工作:n|Integer|16-bitunsigned,network(bi

  3. ruby - 扩展类和实例 - 2

    这个问题有两个部分。在RubyProgrammingLanguage一书中，有一个使用模块扩展字符串对象和类的示例(第8.1.1节)。第一个问题。为什么如果您使用新方法扩展类，然后创建该类的对象/实例，则无法访问该方法？irb(main):001:0>moduleGreeter;defciao;"Ciao!";end;end=>nilirb(main):002:0>String.extend(Greeter)=>Stringirb(main):003:0>String.ciao=>"Ciao!"irb(main):004:0>x="foobar"=>"foobar"irb(main):

  4. ruby-on-rails - Ruby 长时间运行的进程对队列事件使用react - 2

    我有一个将某些事件写入队列的Rails3应用。现在我想在服务器上创建一个服务，每x秒轮询一次队列，并按计划执行其他任务。除了创建ruby​​脚本并通过cron作业运行它之外，还有其他稳定的替代方案吗？ 最佳答案 尽管启动基于Rails的持久任务是一种选择，但您可能希望查看更有序的系统，例如delayed_job或Starling管理您的工作量。我建议不要在cron中运行某些东西，因为启动整个Rails堆栈的开销可能很大。每隔几秒运行一次它是不切实际的，因为Rails上的启动时间通常为5-15秒，具体取决于您的硬件。不过，每天这样做几

  5. ruby - 优雅的链式 'or' 用于测试 Ruby 中的相同变量 - 2

    怎样说才是明智的呢？if@thing=="01"or"02"or"03"or"04"or"05"(数字包含在数据类型字符串的列中。) 最佳答案 制作数组并使用.include?if["01","02","03","04","05"].include?(@thing)如果值真的都是连续的，你可以使用像(1..5).include?这样的范围对于字符串，你可以使用:if("01".."05").include?(@thing) 关于ruby-优雅的链式'or'用于测试Ruby中的相同变量，我

  6. ruby - 如何在 Ruby 中返回整数的固定长度二进制表示？ - 2

    我知道我可以使用Fixnum#to_s将整数表示为二进制格式的字符串。但是1.to_s(2)生成1而我希望它生成00000001。我怎样才能使所有返回的字符串都以零作为填充到8个字符？我可以使用类似的东西:binary="#{'0'*(8-(1.to_s(2)).size)}#{1.to_s(2)}"if(1.to_s(2)).size但这看起来不是很优雅。 最佳答案 使用字符串格式。"%08b"%1#=>"00000001" 关于ruby-如何在Ruby中返回整数的固定长度二进制表示？

  7. ruby - 在不提供其所有属性的情况下获取队列 - 2

    我正在尝试为现有队列编写消费者。RabbbitMQ在一个单独的实例中运行，名为“org-queue”的队列已经创建并绑定(bind)到一个交换器。org-queue是一个持久队列，它还有一些额外的属性。现在我需要从这个队列接收消息。我使用下面的代码来获取队列的实例conn=Bunny.newconn.startch=conn.create_channelq=ch.queue("org-queue")它抛出一个错误，指出不同的耐用属性。默认情况下，Bunny似乎使用durable=false。所以我添加了durabletrue作为参数。现在它说明了其他参数之间的区别。我是否需要指定所有参

  8. ruby - 如何在特定队列中推送作业并使用 sidekiq 限制工作人员数量？ - 2

    我知道我们可以做到:sidekiq_optionsqueue:"Foo"但在这种情况下，Worker只分配给一个队列:“Foo”。我需要在特定队列中分配作业(而不是worker)。使用Resque很容易:Resque.enqueue_to(queue_name,my_job)另外，为了并发问题，我需要限制每个队列的Worker数量为1。我该怎么做？ 最佳答案 您可能会使用https://github.com/brainopia/sidekiq-limit_fetch然后:Sidekiq::Client.push({'class'=>

  9. 欧拉角表示的姿态矩阵（313和312转序） - 2

    一、习惯约定图片来自PSINS（高精度捷联惯导算法）PSINS工具箱入门与详解.pptx二、基本旋转矩阵绕x轴逆时钟旋转α\alphaα角度Rx(α)=[ 1000cos⁡αsin⁡α0−sin⁡αcos⁡α]R_x(\alpha)=\begin{bmatrix}\1&0&0\\0&\cos\alpha&\sin\alpha\\0&-\sin\alpha&\cos\alpha\end{bmatrix}Rx​(α)=​ 100​0cosα−sinα​0sinαcosα​​绕y轴逆时钟旋转α\alphaα角度Ry(α)=[ cos⁡α0−sin⁡α010sin⁡α0cos⁡α]R_y(\alpha

  10. Python：每日一题之小张的衣服（优先队列、哈夫曼编码） - 2

    题目描述小张买了 n 件白色的衣服，他觉得所有衣服都是一种颜色太单调，希望对这些衣服进行染色，每次染色时，他会将某种颜色的所有衣服寄去染色厂，第 i 件衣服的邮费为 ai​ 元，染色厂会按照小张的要求将其中一部分衣服染成同一种任意的颜色，之后将衣服寄给小张，请问小张要将 n 件衣服染成不同颜色的最小代价是多少？输入描述第一行为一个整数 n ，表示衣服的数量。第二行包括 n 个整数a1​,a2​...an​ 表示第 i 件衣服的邮费为 ai​ 元。（1≤n≤10^5,1≤ai​≤10^9 ）输出描述输出一个整数表示小张所要花费的最小代价。输入输出样例输入551321输出25 思考🤔：题意：意思是

随机推荐