建站网站苏州,网页设计模板html代码文本大小,美区下载的app怎么更新,wordpress 个人说明C数据结构与算法 目录
队列介绍
队列这种容器#xff0c;就像大家排队上公交车一样。
第一个来到的人排在最前面#xff1b;
最后来的排在最后面#xff1b;
第一个先上车#xff08;离开队列#xff09;#xff1b;
队列的接口
队列是有如下接口的容器#xff1…C数据结构与算法 目录
队列介绍
队列这种容器就像大家排队上公交车一样。
第一个来到的人排在最前面
最后来的排在最后面
第一个先上车离开队列
队列的接口
队列是有如下接口的容器
class Queue
{
public:const int first(void) const;//队列的对头第一个元素最先进队列的元素inline bool empty(void) const;//判断队列里是否没有元素空队列inline size_t size(void) const;//返回队列元素数量void enqueue(const int item);//将元素item进队列void dequeue(void);//将对头队列的第一个元素出队列从队列中删除void clear(void);//清空队列中的所有元素实现思路
由于双链表的接口覆盖了队列的接口所以可以使用双链表来实现一个队列。
这样就可以在双链表外面封装出一个队列的类。
在实现的时候队列的接口只需要调用双链表的接口即可。
题目如下
#include iostream
#include iomanip
#include list
using namespace std;//------下面的代码是用来测试你的代码有没有问题的辅助代码你无需关注------
#include algorithm
#include cstdlib
#include iostream
#include vector
#include utility
using namespace std;
struct Record { Record(void* ptr1, size_t count1, const char* location1, int line1, bool is) :ptr(ptr1), count(count1), line(line1), is_array(is) { int i 0; while ((location[i] location1[i]) i 100) { i; } }void* ptr; size_t count; char location[100] { 0 }; int line; bool is_array false; bool not_use_right_delete false; }; bool operator(const Record lhs, const Record rhs) { return lhs.ptr rhs.ptr; }std::vectorRecord myAllocStatistic; void* newFunctionImpl(std::size_t sz, char const* file, int line, bool is) { void* ptr std::malloc(sz); myAllocStatistic.push_back({ ptr,sz, file, line , is }); return ptr; }void* operator new(std::size_t sz, char const* file, int line) { return newFunctionImpl(sz, file, line, false); }void* operator new [](std::size_t sz, char const* file, int line)
{return newFunctionImpl(sz, file, line, true);
}void operator delete(void* ptr) noexcept { Record item{ ptr, 0, , 0, false }; auto itr std::find(myAllocStatistic.begin(), myAllocStatistic.end(), item); if (itr ! myAllocStatistic.end()) { auto ind std::distance(myAllocStatistic.begin(), itr); myAllocStatistic[ind].ptr nullptr; if (itr-is_array) { myAllocStatistic[ind].not_use_right_delete true; } else { myAllocStatistic[ind].count 0; }std::free(ptr); } }void operator delete[](void* ptr) noexcept { Record item{ ptr, 0, , 0, true }; auto itr std::find(myAllocStatistic.begin(), myAllocStatistic.end(), item); if (itr ! myAllocStatistic.end()) { auto ind std::distance(myAllocStatistic.begin(), itr); myAllocStatistic[ind].ptr nullptr; if (!itr-is_array) { myAllocStatistic[ind].not_use_right_delete true; } else { myAllocStatistic[ind].count 0; }std::free(ptr); } }
#define new new(__FILE__, __LINE__)
struct MyStruct { void ReportMemoryLeak() { std::cout Memory leak report: std::endl; bool leak false; for (auto i : myAllocStatistic) { if (i.count ! 0) { leak true; std::cout leak count i.count Byte , file i.location , line i.line; if (i.not_use_right_delete) { cout , not use right delete. ; } cout std::endl; } }if (!leak) { cout No memory leak. endl; } }~MyStruct() { ReportMemoryLeak(); } }; static MyStruct my; void check_do(bool b, int line __LINE__) { if (b) { cout line: line Pass endl; } else { cout line: line Ohh! not passed!!!!!!!!!!!!!!!!!!!!!!!!!!! endl; exit(0); } }
#define check(msg) check_do(msg, __LINE__);
//------上面的代码是用来测试你的代码有没有问题的辅助代码你无需关注------class Queue
{
public:inline const int first(void) const;inline bool empty(void) const;inline size_t size(void) const;void enqueue(const int _item);void dequeue(void);void clear(void);
private://使用双链表实现队列std::listint m_queue;
};inline const int Queue::first(void) const
{int a 0;return a;
}bool Queue::empty(void) const
{return false;
}void Queue::clear(void)
{
}size_t Queue::size(void) const
{return -1;
}void Queue::enqueue(const int _item)
{
}void Queue::dequeue(void)
{
}int main(int argc, char** argv)
{//test clear{Queue s;check(s.size() 0);check(s.empty());s.enqueue(1);check(s.size() 1);check(s.empty() false);s.clear();check(s.size() 0);check(s.empty());}//test first{Queue q;check(q.size() 0);q.enqueue(1);check(q.size() 1);auto q2 q;check(q2.size() 1);q q2;q.enqueue(2);auto first q2.first();check(first 1);check(q.size() 2);check(q.first() 1);q.clear();check(q.size() 0 q.empty());}//test enqueue dequeue{Queue q;for (size_t i 0; i 10; i){q.enqueue(i);}int i 0;while (!q.empty()){check(q.first() i)q.dequeue();}check(q.size() 0 q.empty());}
}预期输出如下
line:71 Pass
line:72 Pass
line:74 Pass
line:75 Pass
line:77 Pass
line:78 Pass
line:83 Pass
line:85 Pass
line:87 Pass
line:91 Pass
line:92 Pass
line:93 Pass
line:95 Pass
line:107 Pass
line:107 Pass
line:107 Pass
line:107 Pass
line:107 Pass
line:107 Pass
line:107 Pass
line:107 Pass
line:107 Pass
line:107 Pass
line:110 Pass
Memory leak report:
No memory leak.
