学步园

周末在家，自己用C++练一下手，用顺序存储与链表存储实现了队列queue,queue是一种先进先出的结构，有很多的应用，比如消息队列。

顺序存储实现：

 template<typename T, size_t SIZE><br /> class Queue<br /> {<br /> public:<br /> Queue() : m_front(0), m_rear(0)<br /> {<br /> }<br /> ~Queue()<br /> {<br /> }<br /> void clear()<br /> {<br /> m_front = 0;<br /> m_rear = 0;<br /> }<br /> const bool empty() const<br /> {<br /> return m_front == m_rear;<br /> }<br /> const int size() const<br /> {<br /> int s = (m_rear - m_front + (int)SIZE) % (int)SIZE ;<br /> return s;<br /> }<br /> bool push(const T& t)<br /> {<br /> int pos = (m_rear + 1) % (int)SIZE;<br /> //printf("/n m_rear = %d", pos);<br /> if (pos == m_front)<br /> {<br /> return false;// it's full<br /> }<br /> m_rear = pos;<br /> m_data[m_rear] = t;<br /> return true;<br /> }<br /> T& pop()<br /> {<br /> if (empty())<br /> {<br /> throw Error<T>("Overflow");<br /> }<br /> m_front = (m_front + 1) % (int)SIZE;<br /> //printf("/n m_front = %d", m_front);<br /> return m_data[m_front];<br /> }<br /> T& getfront()<br /> {<br /> return m_data[m_front];<br /> }<br /> // 遍历所有的节点<br /> void traverse( void (*func)(T&) )<br /> {<br /> if ( empty() ) { return;}<br /> for (int idx = m_front + 1; idx != m_rear + 1; idx++)<br /> {<br /> if ( idx == (int)SIZE)<br /> {<br /> idx %= (int)SIZE;<br /> }<br /> //printf("/n idx = %d", idx);<br /> func(m_data[idx]);<br /> }<br /> }<br /> private:<br /> T m_data[SIZE];<br /> int m_front;<br /> int m_rear;<br /> };<br />

链表存储实现：

template<typename T><br /> struct QNode<br /> {<br /> QNode() : m_pNext(NULL)<br /> {<br /> }<br /> T m_data;<br /> QNode* m_pNext;<br /> };<br /> template<typename T><br /> class LQueue<br /> {<br /> typedef QNode<T> TQNode;<br /> public:<br /> LQueue()<br /> {<br /> TQNode* pTemp = NULL;<br /> NEW(pTemp, TQNode() );<br /> m_pFront = m_pRear = pTemp;<br /> m_size = 0;<br /> }<br /> ~LQueue()<br /> {<br /> clear();<br /> DELETE(m_pFront);<br /> }<br /> void clear()<br /> {<br /> TQNode* pTemp = m_pFront->m_pNext;<br /> while(NULL != pTemp )<br /> {<br /> TQNode* pTemp2 = pTemp->m_pNext;<br /> DELETE(pTemp);<br /> pTemp = pTemp2;<br /> }<br /> m_pFront->m_pNext = NULL;<br /> m_size = 0;<br /> }<br /> const bool empty() const<br /> {<br /> return m_pFront == m_pRear;<br /> }<br /> const int size() const { return m_size;}<br /> bool push(const T& t)<br /> {<br /> TQNode* pTemp = NULL;<br /> NEW(pTemp, TQNode() );<br /> if ( NULL == pTemp) { return false;}<br /> pTemp->m_data = t;<br /> pTemp->m_pNext = m_pRear->m_pNext;<br /> m_pRear->m_pNext = pTemp;<br /> m_pRear = pTemp;<br /> m_size++;<br /> return true;<br /> }<br /> T pop()<br /> {<br /> if (empty())<br /> {<br /> throw Error<T>("Overflow");<br /> }<br /> TQNode* pTemp = m_pFront->m_pNext;<br /> T t = pTemp->m_data;<br /> m_pFront->m_pNext = pTemp->m_pNext;<br /> if (NULL == m_pFront->m_pNext)<br /> {<br /> m_pRear = m_pFront;<br /> }<br /> DELETE(pTemp);<br /> m_size--;<br /> return t;<br /> }<br /> T& getfront()<br /> {<br /> if (empty())<br /> {<br /> throw Error<T>("Overflow");<br /> }<br /> TQNode* pTemp = m_pFront->m_pNext;<br /> T t = pTemp->m_data;<br /> return t;<br /> }<br /> // 遍历所有的节点<br /> void traverse( void (*func)(T&) )<br /> {<br /> if ( empty() ) { return;}<br /> TQNode* pTemp = m_pFront->m_pNext;<br /> while(NULL != pTemp)<br /> {<br /> func(pTemp->m_data);<br /> pTemp = pTemp->m_pNext;<br /> }<br /> }<br /> private:<br /> TQNode* m_pFront;<br /> TQNode* m_pRear;<br /> int m_size;<br /> }; 

测试代码：

void print_queue(int& a)<br /> {<br /> printf("%d/t", a);<br /> }<br /> void test_queue()<br /> {<br /> LQueue<int> queue;<br /> //Queue<int, 4> queue;<br /> queue.push(1);<br /> queue.push(2);<br /> queue.push(3);<br /> queue.pop();<br /> queue.pop();<br /> queue.pop();<br /> queue.push(1);<br /> queue.push(2);<br /> queue.push(3);<br /> printf("/n1 : size: %d /n", queue.size() );<br /> queue.traverse(print_queue);<br /> queue.pop();<br /> printf("/n2 : size: %d /n", queue.size() );<br /> queue.traverse(print_queue);<br /> queue.push(4);<br /> printf("/n3 : size: %d /n", queue.size() );<br /> queue.traverse(print_queue);<br /> queue.clear();<br /> printf("/n4 : size: %d /n", queue.size() );<br /> queue.traverse(print_queue);<br /> }<br />