算法與數據結構基礎6：C++隊列的簡單實現
來源：程序員人生 發布時間：2014-12-13 08:36:03 閱讀次數：2498次
隊列也是基于隊列，弄懂了隊列，隊列就很好懂了
// Queue.h
#include <cstdio>
#include <cassert>
#include <iostream>
using namespace std;
class Queue
{
public:
// **************************************************************************
// 類的4大函數：構造函數、拷貝構造函數、重載賦值運算符、析構函數
// **************************************************************************
Queue();
Queue(const Queue &Queue);
Queue& operator=(const Queue &Queue);
~Queue();
// **************************************************************************
// 增刪改查
// **************************************************************************
int Pop();
void Push(const int& data);
unsigned short Size();
bool IsEmpty();
void PrintQueue();
private:
void Free();
private:
typedef struct Node{
Node(int d):data(d),next(NULL){}
int data;
struct Node* next;
}Node;
Node* m_head;
Node* m_tail;/* 這個變量加得有點雞肋，最初是想用來操作鏈表尾，發現只有插入的時候能用，刪除的時候用不了，由于沒有前指針 */
unsigned short m_size;
};
// **************************************************************************
// 私有方法
// **************************************************************************
void Queue::Free()
{
if(m_head){
Node* tmp = NULL;
while(m_head){
tmp = m_head;
m_head = m_head->next;
delete tmp;
}
}
m_head = NULL;
m_tail = NULL;
m_size = 0;
}
// **************************************************************************
// 類的4大函數：構造函數、拷貝構造函數、重載賦值運算符、析構函數
// **************************************************************************
Queue::Queue()
{
m_head = NULL;
m_tail = NULL;
m_size = 0;
}
Queue::Queue(const Queue &Queue)
{
m_head = NULL;
m_tail = NULL;
m_size = Queue.m_size;
if(Queue.m_head){
Node* tmp = Queue.m_head;
Node* q = NULL;
while(tmp){
Node* node = new Node(tmp->data);
if(!m_head){
m_head = node;
q = m_head;
}
else{
q->next = node;
q = node;
}
tmp = tmp->next;
}
m_tail = q;
}
else{
m_head = NULL;
m_tail = NULL;
}
}
Queue& Queue::operator=(const Queue &Queue)
{
Free();
m_size = Queue.m_size;
if(Queue.m_head){
Node* tmp = Queue.m_head;
Node* q = NULL;
while(tmp){
Node* node = new Node(tmp->data);
if(!m_head){
m_head = node;
q = m_head;
}
else{
q->next = node;
q = node;
}
tmp = tmp->next;
}
m_tail = q;
}
else{
m_head = NULL;
m_tail = NULL;
}
return *this;
}
Queue::~Queue()
{
if (m_head){
Node* tmp = m_head;
while (tmp){
m_head = m_head->next;
delete tmp;
tmp = m_head;
}
}
m_head = NULL;
m_tail = NULL;
}
// **************************************************************************
// 增刪改查
// **************************************************************************
void Queue::Push(const int& data)
{
Node* tmp = new Node(data);
if (!m_head) {
m_head = tmp;
m_tail = tmp;
}
else{
tmp->next = m_head;
m_head = tmp;
}
++m_size;
}
int Queue::Pop()
{
assert(m_size > 0);
int val = 0;
Node *cur, *pri;
if (!m_head->next){
val = m_head->data;
delete m_head;
m_head = NULL;
m_tail = NULL;
m_size = 0;
}
else{
cur = m_head;
while (cur->next->next){
cur = cur->next;
}
pri = cur;
m_tail = cur;
cur = cur->next;
pri->next = NULL;
val = cur->data;
delete cur;
cur = NULL;
--m_size;
}
return val;
}
unsigned short Queue::Size()
{
return m_size;
}
bool Queue::IsEmpty()
{
return (m_size == 0);
}
void Queue::PrintQueue()
{
cout << "size : " << m_size << " , content : ";
if (m_head){
Node* tmp = m_head;
while (tmp){
cout << tmp->data << " -> ";
tmp = tmp->next;
}
}
cout << "NULL" << endl;
}
// main.cpp
// test for Queue
#include "Queue.h"
#include <cstdlib>
#include <iostream>
using namespace std;
int main()
{
Queue queue;
for (int i = 1; i < 5; ++i){
queue.Push(i);
}
queue.PrintQueue();
Queue queueCopy(queue);
queueCopy.PrintQueue();
Queue queueAssig;
queueAssig = queue;
queueAssig.PrintQueue();
int pop = queue.Pop();
cout << "pop:" << pop << endl;
queue.PrintQueue();
system("pause");
return 0;
}
// 輸出截圖
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
