学步园

还是前一段时间需要任职资格考试，自己练习一下栈stack的简易实现，今天把它贴出来，暴露的接口与STL类似，没有实现iterator迭代器。实现有两种方式， 基于顺序存储与链式存储。栈的特点是“后进先出”，在数学表达式运算，编译语法分析中，程序函数调用时最为常见。

公用的宏与异常类

#define NEW(var, T) do { /<br /> try { /<br /> var = new T; /<br /> }catch(...) { /<br /> var = NULL; /<br /> } /<br /> }while(0)</p> <p>#define DELETE(var) do { /<br /> if(NULL != var) /<br /> { /<br /> delete var; /<br /> var = NULL; /<br /> } /<br /> var = NULL; /<br /> }while(0)</p> <p>template<typename T><br /> struct Error<br /> {<br /> Error(const char* pszInfo = "Overflow")<br /> {<br /> printf("/nThrow a error, Info :%s/n", pszInfo);<br /> }<br /> };

顺序存储，模板实现，其中参数T为栈的存储类型，参数SIZE表示最大存储的个数。

template<typename T, size_t SIZE><br /> class Stack<br /> {<br /> public:<br /> Stack() :<br /> m_size(0)<br /> {<br /> }<br /> ~Stack()<br /> {<br /> }</p> <p> bool push(const T& t)<br /> {<br /> if (m_size == SIZE)<br /> {<br /> return false;<br /> }</p> <p> m_data[m_size] = t;<br /> m_size++;<br /> return true;<br /> }</p> <p> T& pop()<br /> {<br /> if (0 == m_size)<br /> {<br /> throw Error<T> ("Overflow");<br /> }<br /> else<br /> {<br /> T& t = m_data[m_size];<br /> m_size--;<br /> return t;<br /> }<br /> }</p> <p> void clear()<br /> {<br /> m_size = 0;<br /> }</p> <p> const bool empty() const<br /> {<br /> return 0 == m_size;<br /> }</p> <p> const size_t size() const<br /> {<br /> return m_size;<br /> }</p> <p> // 遍历所有的节点<br /> void traverse(void(*func)(T&))<br /> {<br /> if (empty())<br /> {<br /> return;<br /> }</p> <p> for (size_t idx = 0; idx < m_size; ++idx)<br /> {<br /> func(m_data[idx]);<br /> }<br /> }</p> <p>private:<br /> T m_data[SIZE];<br /> size_t m_size;<br /> };<br />

链式存储，也是模板实现，内部结构为一单向链表。入栈的元素加到链表的表头。

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

测试代码：

void print_stack(int& a)<br /> {<br /> printf("%d/t", a);<br /> }</p> <p>void test_stack()<br /> {<br /> printf("stack test /n");<br /> //Stack<int, 4> stack;<br /> LStack<int> stack;</p> <p> stack.push(1);<br /> stack.push(2);<br /> stack.push(3);<br /> stack.pop();<br /> stack.pop();<br /> stack.pop();<br /> stack.push(1);<br /> stack.push(2);<br /> stack.push(3);</p> <p> printf("/n1 : size: %d /n", stack.size());<br /> stack.traverse(print_stack);</p> <p> stack.pop();<br /> printf("/n2 : size: %d /n", stack.size());<br /> stack.traverse(print_stack);</p> <p> stack.push(4);<br /> printf("/n3 : size: %d /n", stack.size());<br /> stack.traverse(print_stack);</p> <p> stack.pop();<br /> printf("/n4 : size: %d /n", stack.size());<br /> stack.traverse(print_stack);</p> <p> stack.clear();<br /> printf("/n5 : size: %d /n", stack.size());<br /> stack.traverse(print_stack);<br /> }<br />