天天色图,99视频网站,国产福利视频一区二区三区

循環隊列

? ? ? ? 為充分利用向量空間，克服"假溢出"現象的方法是：將向量空間想象為一個首尾相接的圓環，并稱這種向量為循環向量。存儲在其中的隊列稱為循環隊列（Circular Queue）。

? ? ? ?? [置頂] ※數據結構※→☆線性表結構（queue）☆============循環隊列順序存儲結構（queue circular sequence）（十）

條件處理

? ? ? ?? 循環隊列中，由于入隊時尾指針向前追趕頭指針；出隊時頭指針向前追趕尾指針，造成隊空和隊滿時頭尾指針均相等。因此，無法通過條件front==rear來判別隊列是"空"還是"滿"。

? ? ? ?? 解決這個問題的方法至少有三種：
? ? ? ?? ? ? ? ?? ① 另設一布爾變量以區別隊列的空和滿；

? ? ? ?? ? ? ? ?? ② 另一種方式就是數據結構常用的：隊滿時：(rear+1)%n==front，n為隊列長度（所用數組大?。捎趓ear，front均為所用空間的指針，循環只是邏輯上的循環，所以需要求余運算。如圖情況，隊已滿，但是rear（5）+1=6！=front（0），對空間長度求余，作用就在此6%6=0=front（0）。

? ? ? ?? ? ? ? ? ③ 設隊列中元素個數大小，和內存大小個數。判斷比較二個值是否相等。.

? ?? ? ?? ? ?? ? ?? ? ?? ? ?? ②、 ③判斷代碼

? ?? ? ?? ? ?? ? ?? ? ?? ? ??

    /**

* IsFull

*

* @param

* @return BOOL

* @note the buffer is full?

* @attention

*/

template<typename T> BOOL 

AL_QueueCircularSeq<T>::IsFull() const

{

	return (m_dwMaxSize <= Size()) ? TRUE:FALSE;



// 	/*"Sacrifice a unit", ie rear +1 = front (accurately recorded is (rear +1)% m = front, m is the queue capacity) 

// 	when the team is full.*/

// 	if (TRUE == IsEmpty()) {

// 		return FALSE;

// 	}

// 

// 	return ((m_dwRear+1)%m_dwMaxSize == m_dwFront) ? TRUE:FALSE;

}

假溢出

? ?? ? ?? 系統作為隊列用的存儲區還沒有滿,但隊列卻發生了溢出,我們把這種現象稱為"假溢出"。

? ?? ? ? ? 舉例

? ?? ? ?? ? ?? ? ?? 設順序存儲隊列用一維數組q[m]表示，其中m為隊列中元素個數，隊列中元素在向量中的下標從0到m-1。設隊頭指針為front，隊尾指針是rear，約定front指向隊頭元素的前一位置，rear指向隊尾元素。當front等于-1時隊空，rear等于 m-1時為隊滿。由于隊列的性質（“刪除”在隊頭而“插入”在隊尾），所以當隊尾指針rear等于m-1時，若front不等于-1，則隊列中仍有空閑單元，所以隊列并不是真滿。這時若再有入隊操作，會造成假“溢出”。

解決辦法

? ? ? ?? 一是將隊列元素向前“平移”（占用0至rear-front-1）；

? ? ? ?? 二是將隊列看成首尾相連，即循環隊列（0..m-1）。
? ? ? ?? ? ? ? ?? 在循環隊列下，仍定義front=rear時為隊空，而判斷隊滿則用兩種辦法， ? ? ? ?? ? ? ? ??

? ? ? ?? ? ? ? ?? ? ? ? ?? ① 另設一布爾變量以區別隊列的空和滿；

? ? ? ?? ? ? ? ?? ? ? ? ?? ② 另一種方式就是數據結構常用的：隊滿時：(rear+1)%n==front，n為隊列長度（所用數組大?。捎趓ear，front均為所用空間的指針，循環只是邏輯上的循環，所以需要求余運算。如圖情況，隊已滿，但是rear（5）+1=6！=front（0），對空間長度求余，作用就 ? ?? 在此6%6=0=front（0）。

? ? ? ??? ? ? ? ? ? ? ?? ③ 設隊列中元素個數大小，和內存大小個數。判斷比較二個值是否相等。.

本文采用 循環隊列 解決 假溢出

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

? ? ? ? 隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。

? ? ? ??在隊列這種數據結構中，最先插入的元素將是最先被刪除的元素；反之最后插入的元素將是最后被刪除的元素，因此隊列又稱為“先進先出”（FIFO—first in first out）的線性表。

隊列（Queue）是只允許在一端進行插入，而在另一端進行刪除的運算受限的線性表
? ? ? ??（1）允許刪除的一端稱為隊頭（Front）。
? ? ? ??（2）允許插入的一端稱為隊尾（Rear）。
? ? ? ??（3）當隊列中沒有元素時稱為空隊列。
? ? ? ??（4）隊列亦稱作先進先出（First In First Out）的線性表，簡稱為FIFO表。
? ? ? ?

? ? ? ??隊列的修改是依先進先出的原則進行的。新來的成員總是加入隊尾（即不允許"加塞"），每次離開的成員總是隊列頭上的（不允許中途離隊），即當前"最老的"成員離隊。

? ? ? ?? [置頂] ※數據結構※→☆線性表結構（queue）☆============循環隊列順序存儲結構（queue circular sequence）（十）

順序存儲結構

? ? ? ??在計算機中用一組地址連續的存儲單元依次存儲線性表的各個數據元素,稱作線性表的順序存儲結構.

? ? ? ??順序存儲結構是存儲結構類型中的一種，該結構是把邏輯上相鄰的節點存儲在物理位置上相鄰的存儲單元中，結點之間的邏輯關系由存儲單元的鄰接關系來體現。由此得到的存儲結構為順序存儲結構，通常順序存儲結構是借助于計算機程序設計語言（例如c/c++）的數組來描述的。

? ? ? ??順序存儲結構的主要優點是節省存儲空間，因為分配給數據的存儲單元全用存放結點的數據（不考慮c/c++語言中數組需指定大小的情況），結點之間的邏輯關系沒有占用額外的存儲空間。采用這種方法時，可實現對結點的隨機存取，即每一個結點對應一個序號，由該序號可以直接計算出來結點的存儲地址。但順序存儲方法的主要缺點是不便于修改，對結點的插入、刪除運算時，可能要移動一系列的結點。
? ? ? ??

? ? ?? ??優點：

? ? ? ??? ? ? ??隨機存取表中元素。缺點：插入和刪除操作需要移動元素。

? ? ? ? 本代碼默認list可以容納的item數目為100個，用戶可以自行設置item數目。當list飽和時，會自動以2倍的長度進行遞增。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
以后的筆記瀟汀會盡量詳細講解一些相關知識的，希望大家繼續關注我的博客。
本節筆記到這里就結束了。

瀟汀一有時間就會把自己的學習心得，覺得比較好的知識點寫出來和大家一起分享。
編程開發的路很長很長，非常希望能和大家一起交流，共同學習，共同進步。
如果文章中有什么疏漏的地方，也請大家指正。也希望大家可以多留言來和我探討編程相關的問題。
最后，謝謝你們一直的支持~~~

? ? ? ?C++完整個代碼示例（代碼在VS2005下測試可運行）

? ? ? ? [置頂] ※數據結構※→☆線性表結構（queue）☆============循環隊列順序存儲結構（queue circular sequence）（十）

AL_QueueCircularSeq.h

    /**

  @(#)$Id: AL_QueueCircularSeq.h 37 2013-09-09 04:10:00Z xiaoting $

  @brief   To take advantage of vector space, to overcome the "false overflow" phenomenon is: the vector space imagined as an end to 

  end of the ring, saying such a vector is cyclic vector. Stored in a queue which is called circular queue (Circular Queue).

  

  A queue is a special linear form, so special is that it only allows the front end of the table (front) delete operation, 

  and the rear end of the table (rear) for insertion, and the stack, as the queue is an operating by restricted linear form. Insert 

  operation is called the tail end, the end delete operation called HOL. No element in the queue, it is called an empty queue.

  

  This data structure in the queue, the first element inserted will be the first element to be removed; otherwise the last inserted 

  element will be the last element to be removed, so the queue is also known as "first in first out" (FIFO-first in first out) linear 

  form.



  ////////////////////////////////Sequential storage structure//////////////////////////////////////////

  Using a set of addresses in the computer storage unit sequentially stores continuous linear form of individual data elements, called 

  the linear order of the table storage structure.



  Sequential storage structure is a type of a storage structure, the structure is the logically adjacent nodes stored in the physical 

  location of the adjacent memory cells, the logical relationship between nodes from the storage unit to reflect the adjacency. 

  Storage structure thus obtained is stored in order structure, usually by means of sequential storage structure computer programming 

  language (e.g., c / c) of the array to describe.



  The main advantage of the storage structure in order to save storage space, because the allocation to the data storage unit storing 

  all nodes with data (without regard to c / c language in the array size required for the case), the logical relationship between 

  the nodes does not take additional storage space. In this method, the node can be realized on a random access, that is, each node 

  corresponds to a number, the number can be calculated directly from the node out of the memory address. However, the main 

  disadvantage of sequential storage method is easy to modify the node insert, delete operations, may have to move a series of nodes.

  ????????

  Benefits:

	Random Access table elements. Disadvantages: insert and delete operations need to move elements.



  @Author $Author: xiaoting $

  @Date $Date: 2013-09-09 12:10:00 +0800 (周一, 09 九月 2013) $

  @Revision $Revision: 37 $

  @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_QueueCircularSeq.h $

  @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_QueueCircularSeq.h 37 2013-09-09 04:10:00Z xiaoting $

 */



#ifndef CXX_AL_QUEUECIRCULARSEQ_H

#define CXX_AL_QUEUECIRCULARSEQ_H



///////////////////////////////////////////////////////////////////////////

//			AL_QueueCircularSeq

///////////////////////////////////////////////////////////////////////////



template<typename T>  

class AL_QueueCircularSeq

{

public:

	static const DWORD QUEUESEQ_DEFAULTSIZE			= 100;

	static const DWORD QUEUESEQ_MAXSIZE				= 0xffffffff;

	/**

	* Construction

	*

	* @param DWORD dwSize (default value: STACKSEQ_DEFAULTSIZE)

	* @return

	* @note

	* @attention

	*/

	AL_QueueCircularSeq(DWORD dwSize = QUEUESEQ_DEFAULTSIZE);



	/**

	* Destruction

	*

	* @param

	* @return

	* @note

	* @attention

	*/

	~AL_QueueCircularSeq();



	/**

	* IsEmpty

	*

	* @param	VOID

	* @return	BOOL

	* @note		Returns true queue is empty

	* @attention

	*/

	BOOL IsEmpty() const;



	/**

	* Front

	*

	* @param	VOID

	* @return	T

	* @note		Returns a reference to the first element at the front of the queue.

	* @attention

	*/

	T Front() const;



	/**

	* Back

	*

	* @param	VOID

	* @return	T

	* @note		Returns a reference to the last and most recently added element at the back of the queue.

	* @attention

	*/

	T Back() const;



	/**

	* Pop

	*

	* @param	VOID

	* @return	T

	* @note		Removes an element from the front of the queue.

	* @attention

	*/

	T Pop();



		

	/**

	* Push

	*

	* @param	VOID

	* @return	DWORD

	* @note		Adds an element to the back of the queue.

	* @attention	

	*/

	VOID Push(const T& tTemplate);



	/**

	* Size

	*

	* @param	VOID

	* @return	DWORD

	* @note		Returns the number of elements in the queue

	* @attention

	*/

	DWORD Size() const;



	/**

	* Clear

	*

	* @param	VOID

	* @return	VOID

	* @note		clear all data

	* @attention

	*/

	VOID Clear();

	

protected:

private:

	/**

	* GetBuffer

	*

	* @param VOID

	* @return VOID

	* @note get the work buffer

	* @attention when the buffer is not enough, it will become to double

	*/

	VOID GetBuffer();

	

	/**

	* IsFull

	*

	* @param VOID

	* @return BOOL

	* @note the buffer is full?

	* @attention

	*/

	BOOL IsFull() const;





public:

protected:

private: 

	T*			m_pElements;

	DWORD		m_dwMaxSize;

	DWORD		m_dwSize;



	DWORD		m_dwFront;

	DWORD		m_dwRear;

};





/**

* Construction

*

* @param DWORD dwSize (default value: STACKSEQ_DEFAULTSIZE)

* @return

* @note

* @attention

*/

template<typename T> 

AL_QueueCircularSeq<T>::AL_QueueCircularSeq(DWORD dwSize):

m_pElements(NULL),

m_dwMaxSize(dwSize),

m_dwSize(0x00),

m_dwFront(0x00),

m_dwRear(0x00)

{

	if (0x00 == m_dwMaxSize) {

		//for memory deal

		m_dwMaxSize = 1;

	}

	GetBuffer();

}



/**

* Destruction

*

* @param

* @return

* @note

* @attention

*/

template<typename T> 

AL_QueueCircularSeq<T>::~AL_QueueCircularSeq()

{

	if (NULL != m_pElements) {

		delete[] m_pElements;

		m_pElements = NULL;

	}

}



/**

* IsEmpty

*

* @param	VOID

* @return	BOOL

* @note		Returns true queue is empty

* @attention

*/

template<typename T> BOOL 

AL_QueueCircularSeq<T>::IsEmpty() const

{

	return (0x00 == m_dwSize) ? TRUE:FALSE;

}





/**

* Front

*

* @param	VOID

* @return	T

* @note		Returns a reference to the first element at the front of the queue.

* @attention

*/

template<typename T> T 

AL_QueueCircularSeq<T>::Front() const

{

	T tTypeTemp;

	memset(&tTypeTemp, 0x00, sizeof(T));



	if (TRUE ==IsEmpty()) {

		return tTypeTemp;

	}



	return m_pElements[m_dwFront];

}



/**

* Back

*

* @param	VOID

* @return	T

* @note		Returns a reference to the last and most recently added element at the back of the queue.

* @attention

*/

template<typename T> T 

AL_QueueCircularSeq<T>::Back() const

{

	T tTypeTemp;

	memset(&tTypeTemp, 0x00, sizeof(T));



	if (TRUE ==IsEmpty()) {

		return tTypeTemp;

	}



	return m_pElements[m_dwRear];

}



/**

* Pop

*

* @param	VOID

* @return	T

* @note		Removes an element from the front of the queue.

* @attention

*/

template<typename T> T 

AL_QueueCircularSeq<T>::Pop()

{

	T tTypeTemp;

	memset(&tTypeTemp, 0x00, sizeof(T));



	if (TRUE ==IsEmpty()) {

		return tTypeTemp;

	}

	tTypeTemp = m_pElements[m_dwFront];

	memset(&m_pElements[m_dwFront], 0x00, sizeof(T));

	

	m_dwFront = (m_dwFront+1)%m_dwMaxSize;

	

	m_dwSize--;

	return tTypeTemp;

}



	

/**

* Push

*

* @param	VOID

* @return	DWORD

* @note		Adds an element to the back of the queue.

* @attention	

*/

template<typename T> VOID 

AL_QueueCircularSeq<T>::Push(const T& tTemplate)

{

	if (TRUE == IsFull()) {

		// full, need to get more work buffer

		GetBuffer();

	}



	if (0x00 == m_dwFront && TRUE == IsEmpty()) {

		//the first time Push, not need to ++

		m_dwRear = 0x00;

	}

	else {

		m_dwRear = (m_dwRear+1)%m_dwMaxSize;

	}

	m_pElements[m_dwRear] = tTemplate;

	

	m_dwSize++;

}



/**

* Size

*

* @param	VOID

* @return	DWORD

* @note		Returns the number of elements in the queue

* @attention

*/

template<typename T> DWORD 

AL_QueueCircularSeq<T>::Size() const

{

	return m_dwSize;

}



/**

* Clear

*

* @param	VOID

* @return	VOID

* @note		clear all data

* @attention

*/

template<typename T> VOID 

AL_QueueCircularSeq<T>::Clear()

{

	memset(m_pElements, 0x00, sizeof(T)*Size());

	m_dwSize = 0x00;

	m_dwFront = 0x00;

	m_dwRear = 0x00;

}





/**

* GetBuffer

*

* @param VOID

* @return VOID

* @note get the work buffer

* @attention when the buffer is not enough, it will become to double

*/

template<typename T> VOID 

AL_QueueCircularSeq<T>::GetBuffer()

{



	if ( (FALSE == IsFull()) &&(NULL != m_pElements) ) {

		//we do not need to get more buffer

		return;

	}



	if (NULL == m_pElements) {

		if(0 < m_dwMaxSize){

			//get the new work buffer

			m_pElements = new T[m_dwMaxSize];

			memset(m_pElements, 0x00, sizeof(T)*m_dwMaxSize);

		}

		return;

	}



	//we need to get more buffer, store the previous pointer

	T* pLastTpye = NULL;

	DWORD pLastSize = 0x00;



	// it will become to double

	pLastSize = m_dwMaxSize;

	pLastTpye = m_pElements;

	if (QUEUESEQ_MAXSIZE == m_dwMaxSize) {

		//can not get more buffer, please check the application

		return;

	}

	else if (QUEUESEQ_MAXSIZE/2 < m_dwMaxSize) {

		m_dwMaxSize = QUEUESEQ_MAXSIZE;

	}

	else {

		m_dwMaxSize *= 2;

	}

	if(0 < m_dwMaxSize){

		//get the new work buffer

		m_pElements = new T[m_dwMaxSize];

		memset(m_pElements, 0x00, sizeof(T)*m_dwMaxSize);

	}

	//need to copy the last to the current

	memcpy(m_pElements, pLastTpye, sizeof(T)*pLastSize);

	//m_dwFront move to the front

	m_dwFront = 0x00;

	//m_dwFront move to the rear

	m_dwRear = Size() - 1;



	//free the last work buffer

	delete[] pLastTpye;

	pLastTpye = NULL;

}



/**

* IsFull

*

* @param

* @return BOOL

* @note the buffer is full?

* @attention

*/

template<typename T> BOOL 

AL_QueueCircularSeq<T>::IsFull() const

{

	return (m_dwMaxSize <= Size()) ? TRUE:FALSE;



// 	/*"Sacrifice a unit", ie rear +1 = front (accurately recorded is (rear +1)% m = front, m is the queue capacity) 

// 	when the team is full.*/

// 	if (TRUE == IsEmpty()) {

// 		return FALSE;

// 	}

// 

// 	return ((m_dwRear+1)%m_dwMaxSize == m_dwFront) ? TRUE:FALSE;

}



#endif // CXX_AL_QUEUECIRCULARSEQ_H

/* EOF */

測試代碼

    #ifdef TEST_AL_QUEUECIRCULARSEQ

	AL_QueueCircularSeq<DWORD> cQueueCircularSeq(1);

	BOOL bEmpty = cQueueCircularSeq.IsEmpty();

	std::cout<<bEmpty<<std::endl;

	DWORD dwSize = cQueueCircularSeq.Size();

	std::cout<<dwSize<<std::endl;

	DWORD dwFront = cQueueCircularSeq.Front();

	std::cout<<dwFront<<std::endl;

	DWORD dwBack = cQueueCircularSeq.Back();

	std::cout<<dwBack<<std::endl;

	DWORD dwPop = cQueueCircularSeq.Pop();

	std::cout<<dwPop<<std::endl;



	cQueueCircularSeq.Push(999);

	bEmpty = cQueueCircularSeq.IsEmpty();

	std::cout<<bEmpty<<std::endl;

	dwSize = cQueueCircularSeq.Size();

	std::cout<<dwSize<<std::endl;

	dwFront = cQueueCircularSeq.Front();

	std::cout<<dwFront<<std::endl;

	dwBack = cQueueCircularSeq.Back();

	std::cout<<dwBack<<std::endl;

	dwPop = cQueueCircularSeq.Pop();

	std::cout<<dwPop<<std::endl;



	for (DWORD dwCnt=1; dwCnt<5; dwCnt++) {

		cQueueCircularSeq.Push(dwCnt);

		dwBack = cQueueCircularSeq.Back();

		std::cout<<dwBack<<std::endl;

	}



	dwPop = cQueueCircularSeq.Pop();

	std::cout<<dwPop<<std::endl;

	dwPop = cQueueCircularSeq.Pop();

	std::cout<<dwPop<<std::endl;



	for (DWORD dwCnt=5; dwCnt<16; dwCnt++) {

		cQueueCircularSeq.Push(dwCnt);

		dwBack = cQueueCircularSeq.Back();

		std::cout<<dwBack<<std::endl;

	}



	dwSize = cQueueCircularSeq.Size();

	std::cout<<dwSize<<std::endl;

	dwFront = cQueueCircularSeq.Front();

	std::cout<<dwFront<<std::endl;



	while (0x00 != cQueueCircularSeq.Size()) {

		dwPop = cQueueCircularSeq.Pop();

		std::cout<<dwPop<<std::endl;

	}



	bEmpty = cQueueCircularSeq.IsEmpty();

	std::cout<<bEmpty<<std::endl;

	dwSize = cQueueCircularSeq.Size();

	std::cout<<dwSize<<std::endl;

	dwFront = cQueueCircularSeq.Front();

	std::cout<<dwFront<<std::endl;

	dwBack = cQueueCircularSeq.Back();

	std::cout<<dwBack<<std::endl;

	dwPop = cQueueCircularSeq.Pop();

	std::cout<<dwPop<<std::endl;

#endif

[置頂] ※數據結構※→☆線性表結構（queue）☆============循環隊列順序存儲結構（queue circular sequence）（十）

更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索：z360901061

微信掃一掃加我為好友

QQ號聯系： 360901061

您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。

【本文對您有幫助就好】元

2元

5元

10元

20元

自定義