*栈的定义——Stack
栈是只允许在末端进行插入和删除的线性表，栈具有后进先出的特征（LIFO,Last In First Out）.
*栈的应用
栈很大意义上模拟了压栈，实现了递归转非递归。还有算术表达式求值，波兰表达式（后缀表达式），迷宫问题等。
*队列的定义
队列值允许在表的队尾进行插入，在表对头进行删除。队列具有先进先出的特性（FIFO,First In First Out）.
1、优先级队列的定义
每次从队列中取出的都是最高优先级的数据，这种队列就是优先级队列。
——后续使用Heap实现
2、队列的应用
（1）生产者消费者模型，如网络数据buffer
（2）任务队列
（3）图的广度优先遍历
*一般函数的调用栈帧
*递归函数调用栈帧
*函数栈帧调用&数据结构栈帧--栈实现将递归程序转换为非递归程序
#include<iostream> #include<stack> using namespace std; template<class T> struct Node { public: Node(const T& x) :_data(x) ,_next(0) {} T _data;//数据 Node* _next;//指向下个节点的指针 }; template<class T> class SList { public: SList() :_head(0) ,_tail(0) {} public: void PushBack(const T& x) { if(!_head)//链表为空 { _head=new Node<T> (x); _tail=_head; } else { _tail->_next=new Node<T> (x); _tail=_tail->_next; } } Node<T>* GetHead() { return _head; } private: Node<T>* _head; Node<T>* _tail; }; //逆序打印单链表递归实现 template<class T> void PrintTailToHead_R(Node<T>* head) { if(head) { PrintTailToHead_R(head->_next); cout<<head->_data<<" "; } } //逆序打印单链表非递归实现 template<class T> void PrintTailToHead(Node<T>* head) { stack<Node<T>*> s; while(head) { s.push(head); head=head->_next; } while(!s.empty()) { cout<<s.top()->_data<<" "; s.pop(); } } void Test() { SList<int> s1; s1.PushBack(1); s1.PushBack(2); s1.PushBack(3); s1.PushBack(4); s1.PushBack(5); PrintTailToHead_R(s1.GetHead()); cout<<endl; PrintTailToHead(s1.GetHead()); cout<<endl; } int main() { Test(); return 0; }
