栈的解析及C++实现

介绍

栈是一种线性结构，它有以下几个特点：1）栈中数据是按照“后进先出”方式进出栈的2）向栈中添加/删除数据时，只能从栈顶进行操作栈通常包括三种操作：top、pop、pushtop -- 返回栈顶元素pop -- 返回并删除栈顶元素push -- 向栈中添加元素常见错误：栈空时进行top或pop操作解决方法：用户在使用top或pop操作时，需确保栈是非空的

栈的示意图

出栈
入栈

栈的C++实现

顺序栈

顺序栈结构实现的头文件SeqStack.h#ifndef SeqStack_byNim
#define SeqStack_byNim#include<iostream>
using namespace std;const int MAX_SIZE=100;template <class T>
class SeqStack
{
private:
T *data;
int topPointer;
public:
SeqStack（）;
~SeqStack（）;

void push（T e）;
T pop（）;
T top（）;

bool empty（）;
};template <class T>
SeqStack<T>::SeqStack（）
{
topPointer=-1;
data=new T[MAX_SIZE];
}template <class T>
SeqStack<T>::~SeqStack（）
{
topPointer=-1;
delete []data;
}template <class T>
void SeqStack<T>::push（T e） //入栈操作
{
if（topPointer==MAX_SIZE-1）
{
cout<<"OVERFLOW"<<endl; return;
}
topPointer++;
data[topPointer]=e;
}template <class T>
T SeqStack<T>::pop（） //出栈操作
{
if（topPointer==-1）
{
throw "栈空";
}
return data[topPointer--];
}template <class T>
T SeqStack<T>::top（）
{
if（topPointer==-1）
{
throw "栈空";
}
return data[topPointer];
}template <class T>
bool SeqStack<T>::empty（）
{
if（topPointer==-1）
{
return true;
}
return false;
}#endif测试文件：SStackTest.cpp#include<iostream>
#include "SeqStack.h"
using namespace std;int main（）
{
int tmp = 0;
SeqStack<int> *astack = new SeqStack<int>;

cout<<"main"<<endl;

//将10, 20, 30 依次推入栈中
astack->push（10）;
astack->push（20）;
astack->push（30）;

// 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
tmp = astack->pop（）;
cout<<"tmp="<<tmp<<endl;

// 只将“栈顶”赋值给tmp，不删除该元素
tmp = astack->top（）;
cout<<"tmp="<<tmp<<endl;

astack->push（40）;

while（！astack->empty（））
{
tmp = astack->pop（）;
cout<<"tmp="<<tmp<<endl;
}
return 0;
}

链栈

链栈结构实现的头文件：LinkStack.h#ifndef LinkStack_byNim
#define LinkStack_byNim#include<iostream>
using namespace std;template<class T>
struct Node
{
T data; //数据域
Node *next; //指针域
};template<class T>
class LinkStack
{
private:
Node<T> *topPointer;
public:
LinkStack（）;
~LinkStack（）;

void push（T e）;
T pop（）;
T top（）;

bool empty（）;
};template<class T>
LinkStack<T>::LinkStack（）
{
topPointer=new Node<T>;
topPointer->next=NULL;
} template<class T>
LinkStack<T>::~LinkStack（）
{
delete topPointer;
}template<class T>
void LinkStack<T>::push（T e）
{
Node <T> *aNode;
aNode=new Node<T>;
aNode->data=e;
aNode->next=topPointer;
topPointer=aNode;
}template<class T>
T LinkStack<T>::pop（）
{
if（topPointer==NULL）
throw "下溢";
Node <T> *p;
p=topPointer;
T rtndata = topPointer->data;
topPointer=topPointer->next;
delete p;
return rtndata;
}template<class T>
T LinkStack<T>::top（）
{
if（topPointer==NULL）
throw "Empty";
return topPointer->data;
}template<class T>
bool LinkStack<T>::empty（）
{
if（topPointer==NULL）
return true;
return false;
}#endif测试文件：LStackTest.cpp#include<iostream>
#include "LinkStack.h"
using namespace std;int main（）
{
string tmp;
LinkStack<string> *astack = new LinkStack<string>;

cout<<"main"<<endl;

//将"cat"、"dog"、"pig"依次推入栈中
astack->push（"cat"）;
astack->push（"dog"）;
astack->push（"pig"）;

// 将“栈顶元素”赋值给tmp，并删除“栈顶元素”
tmp = astack->pop（）;
cout<<"tmp="<<tmp<<endl;

// 只将“栈顶”赋值给tmp，不删除该元素
tmp = astack->top（）;
cout<<"tmp="<<tmp<<endl;

astack->push（"duck"）;

while（！astack->empty（））
{
tmp = astack->pop（）;
cout<<"tmp="<<tmp<<endl;
}
return 0;
}

STL中自带的“栈”

头文件：#include <stack>测试文件：StackTest.cpp#include<iostream>
#include<stack>
using namespace std;int main（）
{
int tmp = 0;
stack<int> *astack = new stack<int>;

cout<<"main"<<endl;

//将10, 20, 30 依次推入栈中
astack->push（10）;
astack->push（20）;
astack->push（30）;

// 删除“栈顶元素”，pop操作不返回栈顶数据
astack->pop（）;
cout<<"tmp="<<tmp<<endl;

// 只将“栈顶”赋值给tmp，不删除该元素
tmp = astack->top（）;
cout<<"tmp="<<tmp<<endl;

astack->push（40）;

while（！astack->empty（））
{
tmp = astack->top（）;
cout<<"tmp="<<tmp<<endl;
astack->pop（）;
}
return 0;
}注意：STL中自带的stack的pop操作不返回栈顶元素，只进行删除动作本文永久更新链接地址：http://www.linuxidc.com/Linux/2017-01/139797.htm