隊列操作

//------------------------------------------------------------------------------
// 隊列 即比單鏈表多了頭尾標志而已，本質還是單鏈表
//------------------------------------------------------------------------------
#include <iostream>
using namespace std;

typedef struct Node
{
	int   data;
	Node* next;
} Node, *LPNode;

typedef struct Queue
{
	Node* first;			// 頭
	Node* rear;				// 尾
}Queue, *LPQueue;


//******************************************************************************
// Name: CreateQueue
// Desc: 創建隊列
//******************************************************************************
Queue* CreateQueue()
{
	// 創建並返回一個空的隊列
	Queue* tempQueue = new Queue;
	tempQueue->first = NULL;
	tempQueue->rear  = NULL;
	return tempQueue;
}

//******************************************************************************
// Name: Insert
// Desc: 入隊
//******************************************************************************
Queue* Insert(Queue* que, int data)
{
	// 隊裡為空，不能進行入隊操作
	if(que == NULL)
	{
		return  NULL;
	}

	// 先創建一個節點
	Node* newNode = new Node;
	newNode->data = data;
	newNode->next = NULL;

	// 因為隊列的特點是先進先出，所以入隊的時候，插入的位置在最後
	if(que->first == NULL)
	{
		//----------------------------------------------------------------------
		// 頭和尾公用一塊地址，所以後面插入的時候，隊首也將會自動設置next
		//----------------------------------------------------------------------
		que->first = newNode;					// 隊首
		que->rear  = newNode;
	}
	else
	{
		que->rear->next = newNode;
		que->rear = newNode;					// 隊尾
	}

	// 返回隊列
	return que;

}

//******************************************************************************
// Name: OutOfQueue
// Desc: 出隊列, 返回隊首元素使用一維指針，因為已經是指針的指針，能改變內容
//******************************************************************************
Node* OutOfQueue1(Queue* que)
{
	if(que == NULL)
	{
		cout<<"隊列為空"<<endl;
		return NULL;
	}

	// 先進先出原則
	Node* outNode = que->first;
	que->first = que->first->next;

	return outNode;							// 返回出隊列的元素
}


//******************************************************************************
// Name: OutOfQueue
// Desc: 出隊列, 返回隊首元素，改變了隊列的指針，使用二維指針
//******************************************************************************
Node* OutOfQueue2(Queue** que)
{
	if(*que == NULL)
	{
		cout<<"隊列為空"<<endl;
		return NULL;
	}

	// 先進先出原則
	Node* outNode = (*que)->first;
	(*que)->first = (*que)->first->next;

	return outNode;							// 返回出隊列的元素
}


//******************************************************************************
// Name: PrintQueue
// Desc: 打印隊列
//******************************************************************************
void PrintQueue(Queue* que)
{
	/*			改變指針的指針，改變了堆內存的東西，不想單雙鏈表那樣
	Queue* tempQue = que;
	while(tempQue->first != NULL)			
	{
		cout<<tempQue->first->data<<" ";
		tempQue->first = tempQue->first->next;
	}
	cout<<endl;
	*/


	if(que == NULL)	
	{
		cout<<"隊列為空"<<endl;
	}

	Node* tempNode = que->first;
	while(tempNode != NULL)
	{
		cout<<tempNode->data<<" ";
		tempNode = tempNode->next;
	}
	cout<<endl;
}

//******************************************************************************
// Name: QueueLength
// Desc: 返回隊列長度
//******************************************************************************
int QueueLength(Queue* que)
{
	if(que == NULL)
	{
		return 0;
	}

	int currentLength = 0;
	Node* tempNode = que->first;
	while(tempNode != NULL)
	{
		++currentLength;
		tempNode = tempNode->next;
	}

	return currentLength;

}


int main()
{
	// 創建隊列
	Queue* que = CreateQueue();
	cout<<"創建隊列成功，輸入幾組要入隊的元素"<<endl;
	
	// 入隊
	int insertElem;
	while(cin>>insertElem)
	{
		que = Insert(que, insertElem);
	}

	// 打印
	cout<<"打印隊列:"<<endl;
	PrintQueue(que);

	// 打印
	cout<<"打印隊列:"<<endl;
	PrintQueue(que);

	// 出隊列
	Node* outNode = OutOfQueue1(que);
	cout<<"隊列首出隊:"<<outNode->data<<endl;

	// 再次打印
	PrintQueue(que);

	// 打印長度
	cout<<"當前隊列長度為:"<<QueueLength(que)<<endl;

	

	system("pause");
	return 0;
}