5. 栈
（1）实现一个栈
#include <iostream>
using namespace std;
//通过链表来实现栈
struct Node
{
int data;
Node *next;
};
struct LStack//代表linked stack
{
Node *top;//栈顶
};
int main()
{
LStack *ls = new LStack;
//这里也可以直接构造LStack对象（LStack ls;），但是为了与前面相一致，以使得pushNode函数
//和popNode函数的参数都为指针形式（方便记忆），这里仍用动态分配的方式
Node *newNode = new Node;
newNode->data = 0;
newNode->next = NULL;
ls->top = newNode;
for(int i=1; i<10; ++i)
{
newNode = new Node;
newNode->data = i;
newNode->next = ls->top;
ls->top = newNode;
}
//下面的输出不能称为是栈的打印，因为这是链表的接口用法，对栈而言，它应该只能用popNode()函数
//这里仅仅是为了显示一下栈中的数据而已。
//真正的栈的打印见后面。
for(Node *currPtr=ls->top; currPtr!=NULL; currPtr=currPtr->next)
{
cout << currPtr->data << " ";
}
cout << endl;//输出：8 7 6 5 4 3 2 1
return 0;
}
（2）栈的入栈
struct Node
{
int data;
Node *next;
};
struct LStack//代表linked stack
{
Node *top;//栈顶
};
void pushNode(LStack *&ls, int item)
{
Node *newNode = new Node;
newNode->data = item;
newNode->next = ls->top;
ls->top = newNode;
//【注】栈的新结点与原栈顶的指向不能弄反了，否则不能按照“后进先出”的规则出栈。
}
（3）栈的出栈
struct Node
{
int data;
Node *next;
};
struct LStack//代表linked stack
{
Node *top;//栈顶
};
//出栈函数不应该返回出栈结点的值（因为STL中的pop函数也没有返回值）
void popNode(LStack *&ls)
{
if(NULL == ls->top)//栈为空时
{
cerr << "the stack have been empty\n";
exit(1);
}
else
{
Node *temp = ls->top;
ls->top = ls->top->next;
delete temp;
}
}
（4）栈的打印
void printStack(LStack *&ls)
{
while(ls->top != NULL)
{
cout << popNode(ls) << " ";
}
cout << endl;
//【注】栈的打印要体现栈本身的特性，故一定要要popNode()函数进行栈的打印！
//当打印完毕后，栈也就被清空了
}
（5）用两个栈实现一个队列的功能
这道题不像前面那些题那样，本题不要求自己编写一个队列，而是以栈为基本元素来实现队列的入队、出队这样的功能，也即，本题所述的“栈”是STL中的栈模板，故本题属于泛型编程的范畴。因此，不要将本题中的pop()成员函数与前面自定义的popNode()函数相混淆！
#include "stdafx.h"
#include <iostream>
#include <stack>
using namespace std;
//用s1提供入队操作，而用s2提供出队操作。
//【注】front()与deleteNode()的不同就如同stack的类成员函数中top()与pop()的不同一样，
//前者返回队首元素的引用，而后者令队首元素出队/删除
template <typename T>
struct SQueue//代表stack queue
{
stack<T> s1, s2;//对于类或结构体而言，成员变量放在成员函数前、后都是一样的。
void insertNode(T &item)
{
s1.push(item);
}
T front()
{
if(s2.empty())