队列（链式队列）—— 线性结构的应用之一

/**
 * @brief: 
 * @version:  
 * @author: @Shiel
 * @date: 2023-10-27 17:18:06
 **/
# include <iostream>
using namespace std;

typedef struct node
{
  int data;
  struct node* pNext;		// int* pBase; 错误！
}NODE, *PNODE;

class Queue 
{
public:
  PNODE pHead, pTail;	//pHead指向无用的头结点 pHead->pNext才指向队首元素, pTail指向队尾元素
  
public:
  Queue();
  
  void Traverse_Queue(void) const;
  bool Empty_Queue(void) const;
//	bool Full_Queue();		// 链式队列不会满！
  void En_Queue(int val);
  bool Out_Queue(int& val);	//使用引用更好；bool Out_Queue(int* pVal);
  void Clear_Queue(void);
  
  ~Queue();
};

int main(void)
{
  Queue Q;
  int val;
  
  for(int i=0;i<5;i++)
  {
    Q.En_Queue(i + 1);
  }
  Q.Traverse_Queue();
  
  if( Q.Out_Queue(val) )	//用引用代替&val
  {
    cout<<"出队成功，出队的元素是: " << val << endl;
  }
  else
    cout << "出队失败！" << endl;
  
  if( Q.Out_Queue(val) )	//用引用代替&val
  {
    cout<<"出队成功，出队的元素是: " << val << endl;
  }
  else
    cout << "出队失败！" << endl;
  
  Q.Traverse_Queue();
  
  Q.Clear_Queue();
  Q.Traverse_Queue();
  
  return 0;
}

Queue::Queue()
{
  this->pHead = this->pTail = new NODE;
  this->pHead->pNext = NULL;
}

Queue::~Queue()
{
  this->Clear_Queue();
  delete this->pHead;
}

void Queue::Traverse_Queue(void) const
{
  PNODE pTemp = this->pHead->pNext;
  
  if(pTemp == nullptr)
  {
    cout << "队列为空，无法遍历！" << endl;
  }
  
  while(pTemp != nullptr)
  {
    cout << pTemp->data << " ";
    pTemp = pTemp->pNext;
  }
  cout << endl;
}

bool Queue::Empty_Queue() const
{
  if(this->pHead == this->pTail)
  {
    return true;
  }
  else
    return false;
}

void Queue::En_Queue(int val)	//在类外必须指定成员函数的作用域Queue::
{
  PNODE pNew = new NODE;
  
  pNew->data = val;
  pNew->pNext = nullptr;		//使用nullptr而不是NULL，这是现代C++的做法
  
  this->pTail->pNext = pNew;	//用this指代当前对象的指针，增强可读性
  this->pTail = pNew;
}

bool Queue::Out_Queue(int& val)	
{
  if(this->Empty_Queue())
  {
    cout << "队列为空，无法出队！" << endl;
    return false;
  }
  else
  {
    PNODE pTemp = this->pHead->pNext;
    val = pTemp->data;
    
    this->pHead->pNext = pTemp->pNext;	//this->pHead->pNext->pNext;
    delete pTemp;		// 使用delete释放内存，而不是free(pTemp);
    pTemp = nullptr;
    
    if( nullptr == this->pHead->pNext )	//检查队列是否为空
    {
      this->pTail = this->pHead;	
      //如果队列为空，则将 pTail 指针移回 pHead，
      //这是为了确保在队列变为空时， pTail 也要指向无用的头结点。
    }
    
    return true;
  }
}

void Queue::Clear_Queue(void)
{
  while( !this->Empty_Queue() )
  {
    int val;
    this->Out_Queue(val);
  }
}