Loading...
墨滴

公众号:offer多多

2021/12/20  阅读:37  主题:橙心

跟源码学数据结构 |系统设计循环队列

跟源码学数据结构 |系统设计循环队列

一、题目来源:

设计你的循环队列实现。

  1. 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出),有一定容量

原则并且队尾被连接在队首之后以形成一个循环

  1. 支持任意类型数据

  2. 获取 第一大 第二大 avg 等操作

二、代码实现

#include <iostream>
using namespace std;

//单链表 
template <class T>
struct Node
{
    T data;
    //why 这里为什么不用基本类型指针呢 T* ?使用基本类型 int  a ?
    //why STL 成员 都是封装的迭代器?
    //容器的数据 都是值拷贝
    Node *next;
    Node(T &&value,Node* pnext)
    {
        next = pnext;
        data = forward<T>(value);
    }
    Node()
    {
        next = nullptr;
    }
}

template <class T>
//queue 是适配器容器, 使用 list 作为底层容器。
//循环队列 
class MyCircularQueue
{
private:
    // head 
    Node<T> *m_phead;
    Node<T> *m_ptail;

    int m_capacity;
    int m_length;

public:

 MyCircularQueue(int capacity);
 ~MyCircularQueue(); 
 bool write(T && value);
 bool read(T & value);

 // 模仿std::queue接口设计
 //What should dequeue return if the queue is empty
 //reference& front()
 //void emplace (Args&&... args)

 T max();

}

template <class T>
//构造循环链表
MyCircularQueue<T>::MyCircularQueue(int capacity)
{   

    //分配capacity大小
    m_capacity = capacity;
    m_length = 0;

    //empty  m_phead == m_ptail && len ==0  
    //full  m_phead == m_ptail->next  && len !=1 

    Node<T>* pcur = new Node<T>();
    m_phead = pcur;
    m_ptail = pcur;
   
    for (int i =1;i<capacity;i++)
    {
        pcur = new Node<T>();

        m_ptail->next = pcur;
        m_ptail = pcur;
    }

    m_ptail->next = m_phead; 
}

//思考:这里为不重写2个版本的 T value, const T && value
template <class T>
bool MyCircularQueue<T>::write(T && value)
{
    if (m_length == m_capacity)
    {
        return false;
    } //约束条件:有容量的

    //第一个元素
    if (0 == m_length)
    {
         m_ptail->data = forward<T>(value);
    }else
    {
        m_ptail = m_ptail->next;
        m_ptail->data = forward<T>(value);
    }

    m_length ++;

    return true;
}

template <class T>
bool MyCircularQueue<T>::read(T & value)
{
    if (m_length == 0)
    {
        return false;
    } 
     //front 
     value = std::move(m_phead->data)
     //pop 
     m_phead =  m_phead->next;
     m_length --;

     return true;
}

int main()
{
    MyCircularQueue<string> queue(10);
    for (int i = 0; i < 5; i++)
    {   
        string temp("abc");
        temp.append(to_string(i));
        queue.write(temp);
        queue.write(std::move(temp));
    }
    cout << "read 1 max ==="<<queue.max()<<endl; 
    cout << "read 2 max ==="<<queue.max()<<endl; 
    for (int i = 0; i < 10; i++)
    {
        string temp;
        queue.read(temp);
        cout << temp << endl;
    }
    return 0;
}

三、思路分析

小白 第一反应:

问:不知道从哪里下手

答:

//审题

01 设计循环队列的数据结构:

链表实现 ---why [适配器容器 链表和数组都可以]

支持任意类型T --why [void * 让问题更复杂]

  • 《C++ primer》中的一个例子,感觉对模板编程很有帮助,便从头到尾实现了一遍。 内部机制实际上是一个链表 https://www.kancloud.cn/digest/mystl/192553

02 满足读写功能. 参数怎么设计,如何优化

如何减少拷贝?

c+11版本的

  • std::queue 源码剖析

  • std::stack 源码剖析

  • std::vector 源码剖析

参数传递一次,

拷贝构造 拷贝赋值

左右值

03 完成max avg 功能 参数怎么设计 不用算法进行优化。

小贴士

总结:上来去优化算法干扰设计结构设计。忘记本质

初级 第一反应: 问:有人用吗?

答:

  • 初窥内核 | 躲在 kernel 里的双向循环链表 https://www.toutiao.com/i7042572225022607883/

  • C++11新特性之十:enable_shared_from_this

小贴士:

线程安全的知识卡片:

1 用法:在class内部拿到this的shared_ptr版本

2 场景: 在类中发起一个异步操作,

callback回来要保证发起操作的对象仍然有效.

https://blog.csdn.net/caoshangpa/article/details/79392878

3 原理:

欢迎关注
欢迎关注

相关文章

  • 智能指针究竟在考什么|Effective Modern C++

https://mp.weixin.qq.com/s?__biz=MzA3OTY3OTE1MQ==&mid=2651706311&idx=2&sn=cc2a69505bd612302e892d5d3b71ac5d&chksm=8456a807b3212111b0373d79829cd0b6f73e40d20c9fb6d8fb2c2505ee34ec89bb0949901e1e&token=632630228&lang=zh_CN#rd

  • 使用 C++ 智能指针遇到的坑

https://mp.weixin.qq.com/s?__biz=MzA3OTY3OTE1MQ==&mid=2651708019&idx=1&sn=088fd09e93efa60ca476b23009b25450&chksm=8456a1b3b32128a506b72e63686ee15f18c646b6f033b3086cb5d0d9fc1d3ea669297d506046&token=632630228&lang=zh_CN#rd

  • 同样代码:学会从c98实现省级到c++11的实现

https://en.cppreference.com/w/cpp/memory/enable_shared_from_this

https://www.zhihu.com/question/30957800

A Queue implemented as a linked structure in C++. https://www.cs.uah.edu/~rcoleman/Common/CodeVault/Code/Code137_Queue.html

https://www.cplusplus.com/reference/queue/queue/emplace/

microsoft_STL\stl\inc\stack 基本操作

公众号:offer多多

2021/12/20  阅读:37  主题:橙心

作者介绍

公众号:offer多多