栈是一种线性结构，它有以下几个特点：

1）栈中数据是按照“后进先出”方式进出栈的

2）向栈中添加/删除数据时，只能从栈顶进行操作

栈通常包括三种操作：top、pop、push

top -- 返回栈顶元素

pop -- 返回并删除栈顶元素

push -- 向栈中添加元素

常见错误：栈空时进行top或pop操作

解决方法：用户在使用top或pop操作时，需确保栈是非空的

?

出栈

?

入栈

顺序栈结构实现的头文件SeqStack.h

#ifndef SeqStack_byNim
#define SeqStack_byNim

#include
using namespace std;

const int MAX_SIZE=100;

template
class SeqStack
{
?private:
? T *data;
? int topPointer;
?public:
? SeqStack();
? ~SeqStack();
?
? void push(T e);
? T pop();
? T top();
?
? bool empty();
};

template
SeqStack::SeqStack()
{
?topPointer=-1;
?data=new T[MAX_SIZE];
}

template
SeqStack::~SeqStack()
{
?topPointer=-1;
?delete []data;
}

template
void SeqStack::push(T e)?//入栈操作
{
?if(topPointer==MAX_SIZE-1)?
?{
? cout<<"OVERFLOW"<?}
?topPointer++;
?data[topPointer]=e;
}

template
T SeqStack::pop()?//出栈操作
{
?if(topPointer==-1)
?{
? throw "栈空";
?}
?return data[topPointer--];
}

template
T SeqStack::top()
{
?if(topPointer==-1)
?{
? throw "栈空";
?}
?return data[topPointer];
}

template
bool SeqStack::empty()
{
?if(topPointer==-1)
?{
? return true;
?}
?return false;
}

#endif

测试文件：SStackTest.cpp

#include
#include "SeqStack.h"
using namespace std;

int main()
{
?int tmp = 0;
?SeqStack *astack = new SeqStack;
?
?cout<<"main"<?
?//将10, 20, 30 依次推入栈中
?astack->push(10);
? ? astack->push(20);
? ? astack->push(30);
? ?
? ? // 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
? ? tmp = astack->pop();
? ? cout<<"tmp="<? ?
? ? // 只将“栈顶”赋值给tmp，不删除该元素
? ? tmp = astack->top();
? ? cout<<"tmp="<? ?
? ? astack->push(40);
? ?
? ? while(!astack->empty())
? ? {
? ? ?tmp = astack->pop();
? ? ?cout<<"tmp="<?}
?return 0;
}

链栈结构实现的头文件：LinkStack.h

#ifndef LinkStack_byNim
#define LinkStack_byNim

#include
using namespace std;

template
struct Node
{
?T data;?//数据域
?Node *next;?//指针域
};

template
class LinkStack
{
?private:
? Node *topPointer;
?public:
? LinkStack();
? ~LinkStack();
?
? void push(T e);
? T pop();
? T top();
?
? bool empty();
};

template
LinkStack::LinkStack()
{
?topPointer=new Node;
?topPointer->next=NULL;
}?

template?
LinkStack::~LinkStack()
{
?delete topPointer;
}

template
void LinkStack::push(T e)
{
?Node *aNode;
?aNode=new Node;
?aNode->data=e;
?aNode->next=topPointer;
?topPointer=aNode;
}

template
T LinkStack::pop()
{
?if(topPointer==NULL)
? throw "下溢";
?Node *p;
?p=topPointer;
?T rtndata = topPointer->data;
?topPointer=topPointer->next;
?delete p;
?return rtndata;
}

template
T LinkStack::top()
{
?if(topPointer==NULL)
? throw "Empty";
?return topPointer->data;
}

template
bool LinkStack::empty()
{
?if(topPointer==NULL)
? return true;
?return false;
}

#endif

测试文件：LStackTest.cpp

#include
#include "LinkStack.h"
using namespace std;

int main()
{
?string tmp;
?LinkStack *astack = new LinkStack;
?
?cout<<"main"<?
? //将"cat"、"dog"、"pig"依次推入栈中
?astack->push("cat");
? ? astack->push("dog");
? ? astack->push("pig");
? ?
? ? // 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
? ? tmp = astack->pop();
? ? cout<<"tmp="<? ?
? ? // 只将“栈顶”赋值给tmp，不删除该元素
? ? tmp = astack->top();
? ? cout<<"tmp="<? ?
? ? astack->push("duck");
? ?
? ? while(!astack->empty())
? ? {
? ? ?tmp = astack->pop();
? ? ?cout<<"tmp="<?}
?return 0;
}

头文件：#include

测试文件：StackTest.cpp

#include
#include
using namespace std;

int main()
{
?int tmp = 0;
?stack *astack = new stack;
?
?cout<<"main"<?
?//将10, 20, 30 依次推入栈中
?astack->push(10);
? ? astack->push(20);
? ? astack->push(30);
? ?
? ? // 删除“栈顶元素”，pop操作不返回栈顶数据
? ? astack->pop();
? ? cout<<"tmp="<? ?
? ? // 只将“栈顶”赋值给tmp，不删除该元素
? ? tmp = astack->top();
? ? cout<<"tmp="<? ?
? ? astack->push(40);
? ?
? ? while(!astack->empty())
? ? {
? ? ?tmp = astack->top();
? ? ?cout<<"tmp="<? ? ?astack->pop();
?}
?return 0;
}