C++数据结构之链式队列(Linked Queue)
2024-08-21 11:10:53
C++数据结构之链式队列,实现的基本思想和链式栈的实现差不多,比较不同的一点也是需要注意的一点是,链式队列的指向指针有两个,一个是队头指针(front),一个是队尾指针(rear),注意指针的指向是从队首指到队尾(front -> Front_Node -> …… -> rear -> Rear_Node).
代码:
Node.h文件
/* * Node.h * * Created on: 2015年9月10日 * Author: Lv_Lang */ #ifndef NODE_H_ #define NODE_H_ #include "stdio.h" // for NULL typedef int Queue_entry; typedef Queue_entry Node_entry; struct Node { // data members Node_entry entry; // 存放的元素 Node *next; // 指向下一个元素的指针 // Constructors Node(); Node(Node_entry item, Node *add_on = NULL); }; #endif /* NODE_H_ */
Node.cpp文件:
/* * Node.cpp * * Created on: 2015年9月10日 * Author: Lv_Lang */ #include "Node.h" Node::Node() { next = NULL; } Node::Node(Node_entry item, Node *add_on) { entry = item; next = add_on; }
Queue.h文件:
/* * Queue.h * * Created on: 2015年9月10日 * Author: Lv_Lang */ #ifndef QUEUE_H_ #define QUEUE_H_ #include "stdio.h" #include "Node.h" enum Error_code {overflow,underflow,success}; class Queue { public: // Standard Queue methods Queue(); bool empty()const; Error_code append(const Queue_entry &item); Error_code serve(); Error_code retrieve(Queue_entry &item)const; // Safety features for linked structures ~Queue(); Queue(const Queue &original); void operator = (const Queue &original); // Extended linked queue bool full()const; int size()const; void clear(); protected: Node *front, *rear; }; #endif /* QUEUE_H_ */
Queue.cpp文件
/* * Queue.cpp * * Created on: 2015年9月10日 * Author: Lv_Lang */ #include "Queue.h" Queue::Queue() { front = NULL; rear = NULL; } bool Queue::empty()const { if((front == NULL) && (rear == NULL)) return true; else return false; } Error_code Queue::append(const Queue_entry &item) { Node *new_rear = new Node(item); if(new_rear == NULL) return overflow; if(rear == NULL) front = rear = new_rear; else { rear->next = new_rear; rear = new_rear; } return success; } Error_code Queue::serve() { if(empty()) return underflow; else { Node *old_front = front; front = front->next; if(front == NULL) rear = NULL;// 此处需注意将rear也置为0 delete old_front; return success; } } Error_code Queue::retrieve(Queue_entry &item)const { if(empty()) return underflow; else { item = front->entry; return success; } } Queue::~Queue() { if(!empty()) { serve(); } } Queue::Queue(const Queue &original) { Node *new_front, *original_front = original.front; if(original.front == NULL) front = rear= NULL; else { front = new_front = new Node(original_front->entry); while(original_front->next != NULL) { original_front = original_front->next; new_front->next = new Node(original_front->entry); new_front = new_front->next; } } } void Queue::operator =(const Queue &original) { Node *new_front, *original_front = original.front; if(original.front == NULL) front = rear= NULL; else { if(!empty()) clear(); else { front = new_front = new Node(original_front->entry); while(original_front->next != NULL) { original_front = original_front->next; new_front->next = new Node(original_front->entry); new_front = new_front->next; } } } } bool Queue::full()const { Node *new_front = new Node(); if(new_front == NULL) <span style="white-space:pre"> </span>{
<span style="white-space:pre"> delete new_front;</span>
<span style="white-space:pre"> </span>return true;
<span style="white-space:pre"> </span>} else { delete new_front; return false; } } int Queue::size()const { Node *window = front; int count = 0; while(window != NULL) { window = window->next; count++; } return count; } void Queue::clear() { if(!empty()) { serve(); } }
main函数测试文件:
/* * main.cpp * * Created on: 2015年9月10日 * Author: Lv_Lang */ #include "Queue.h" int main() { Queue myqueue; myqueue.append(2); myqueue.append(6); int size; size = myqueue.size(); printf("%s %d\n","Size is ",size); myqueue.serve(); int a; myqueue.retrieve(a); printf("%d\n",a); size = myqueue.size(); printf("%s %d\n","Size is ",size); Queue QUEUE(myqueue); int b; QUEUE.retrieve(b); printf("%d\n",b); size = QUEUE.size(); printf("%s %d\n","Size for QUEUE is ",size); myqueue.clear(); size = myqueue.size(); printf("%s %d\n","Size is ",size); return 0; }
最新文章
- 【转载】Understand the serialVersionUID
- 贼溜的更新Android-SDK的方法(亲测很好用)
- cssSlidy.js 响应式手机图片轮播
- Java网络编程——TCP/UDP
- git简介及安装配置
- jquery获取文档高度和窗口高度的例子
- [Doc ID 1666646.1]如何使用功能管理员清除缓存?
- Java操作属性文件,支持新增或更新多个属性
- Linux中oracle的安装,亲测
- lombk在IDEA中报ClassNotFoundException错误
- 双11电商剁手节,最全的H5互动营销案例合集
- 笔记-JS高级程序设计-基本概念篇
- java8_api_io
- 【Javascript系列】变量作用域
- java ==与equals()方法的总结
- linux服务器时间同步失败解决方法
- Linux中inotify软件部署及参数事件演示
- 在IIS上部署你的ASP.NET Core项目 (转载)
- No mapping found for HTTP request with URI [/Portal/download] in DispatcherServlet with name &#39;springmvc&#39;
- 初始Hive
热门文章
- 抓包工具Fidder设置(移动端抓包)
- POST中文乱码解决方案
- 浅谈AsyncState与AsyncDelegate使用的异同
- 024-ActionResult解说
- informix数据库下导出表结构
- [ssc] 数据库管理工具——SQuirreL SQL Client使用入门
- [saiku] 系统登录成功后查询Cubes
- Compound Interest Calculator3.0续
- 231. Power of Two 342. Power of Four -- 判断是否为2、4的整数次幂
- 石子归并问题(nyoj737)