介绍
栈是一种线性结构,它有以下几个特点:
1)栈中数据是按照“后进先出”方式进出栈的
2)向栈中添加/删除数据时,只能从栈顶进行操作
栈通常包括三种操作:top、pop、push
top -- 返回栈顶元素
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.xuebuyuan.com/Linux/2017-01/139797.htm
以上就上有关栈的解析及C++实现的全部内容,学步园全面介绍编程技术、操作系统、数据库、web前端技术等内容。