class="MsoNormal">?
顺序栈和链栈是我复习的第二部分,同样是把之前的代码整理出来,发布给大家,实现的方法并不
难,毕竟是最基本的方法嘛。关于代码的解释已经写成注释。所以不用多说了。大家好好看代码吧~
下面的代码是栈的实习,完整代码实现下载地址;
//顺序栈
//
#ifndef ASTACK_H
#defineASTACK_H
#include"Stack.h"
template <classElem> classAStack : publicStack<Elem>{
private:
???????? int size;//栈最大长度
???????? int top;//栈长度
???????? Elem *listArray;
public:
???????? AStack(intsz = DefaultListSize){
?????????????????? size = sz;
?????????????????? top = 0;
?????????????????? listArray = newElem[sz];
???????? }
???????? ~AStack(){
?????????????????? delete [] listArray;
???????? }
???????? voidclear(){
?????????????????? top=0;
???????? }
???????? boolpush(constElem& item){//存入操作
?????????????????? if(top==size) returnfalse;
?????????????????? else{
??????????????????????????? listArray[top++] = item;
??????????????????????????? returntrue;
?????????????????? }
???????? }
???????? boolpop(Elem& it){//取出操作
?????????????????? if(top==0) returnfalse;
?????????????????? else{
??????????????????????????? it = listArray[--top];
??????????????????????????? returntrue;
?????????????????? }
???????? }
???????? booltopValue(Elem& it){//获取栈顶值
?????????????????? if(top==0) returnfalse;
?????????????????? else{
??????????????????????????? it = listArray[top-1];
??????????????????????????? returntrue;
?????????????????? }
???????? }
???????? intlength() const{//栈长度
?????????????????? return top;
???????? }
???????? //利用栈将栈逆置
???????? //具体分为以下几步:声明一个变量,用来临时存放栈顶元素,记为A;
???????? //声明一个顺序栈,栈长比原栈小1,记为ls;
???????? //首先将栈顶元素放入A,将剩下的元素放入ls,再将A放入原栈,接着将ls中所有元素放入原栈;
???????? //重复n此,n为栈长;
???????? voidreverlist(){
?????????????????? Elem it;
?????????????????? Elem A;
?????????????????? AStack<Elem> ls(top-1);
?????????????????? for (int i = 0; i < top; i++){
??????????????????????????? this->pop(A);
??????????????????????????? while (this->length())
??????????????????????????? {
???????????????????????????????????? this->pop(it);
???????????????????????????????????? ls.push(it);
??????????????????????????? }
??????????????????????????? this->push(A);
??????????????????????????? while (ls.length())
??????????????????????????? {
???????????????????????????????????? ls.pop(it);
???????????????????????????????????? this->push(it);
??????????????????????????? }
?????????????????? }
???????? }
};
#endif
?
//Stack类,定义栈中的方法
//只有五个方法:1、清空;2、进栈;3、出栈;4、获得栈顶元素值;5、输出栈高
#ifndef STACK_H
#defineSTACK_H
?
#include<iostream>
usingnamespace std;
template <classElem> classStack{
public:
???????? virtualvoidclear() = 0;
???????? virtualboolpush(constElem&) = 0;
???????? virtualboolpop(Elem&) = 0;
???????? virtualbooltopValue(Elem&) = 0;
???????? virtualintlength() const =0;
???????? virtualvoidreverlist() = 0;
};
#endif;
?
//链式栈的节点
#ifndef? SLINK_H
#define? SLINK_H
//链栈节点
#include<iostream>
usingnamespace std;
template<classElem> classSLink{
public:
???????? Elem element;
???????? SLink *next;
???????? SLink(constElem& elemval,SLink* nextval = NULL){
?????????????????? element=elemval;
?????????????????? next = nextval;
???????? }
???????? SLink(SLink* nextval =NULL){
?????????????????? next = nextval;
???????? }
};
#endif// ! SLINK_H
?
//链式栈
#ifndef LSTACK_H
#defineLSTACK_H
#include"Stack.h"
#include"SLink.h"
template <classElem> classLStack : publicStack<Elem>{
???????? SLink<Elem>* top;
???????? int size;//表长度
public:
???????? LStack(){
?????????????????? size = 0;
???????? }
???????? ~LStack(){
?????????????????? clear();
???????? }
???????? //清空表
???????? //清空表的操作流程:将top元素一个一个delete掉
???????? voidclear(){
?????????????????? if (size == 0){
??????????????????????????? cout << "This stack is empty"<<endl;
?????????????????? }
?????????????????? else{
??????????????????????????? int num = 0;
??????????????????????????? while (top != NULL&&size>1)
??????????????????????????? {
???????????????????????????????????? SLink<Elem>* temp = top;
???????????????????????????????????? top = top->next;
???????????????????????????????????? size--;
???????????????????????????????????? delete temp;
??????????????????????????? }
??????????????????????????? delete top;
??????????????????????????? size--;
??????????????????????????? cout << size << endl;
?????????????????? }
???????? }
???????? //入栈
???????? boolpush(constElem& item){
?????????????????? top =newSLink<Elem>(item,top);
?????????????????? size++;
?????????????????? returntrue;
???????? }
???????? //出栈
???????? boolpop(Elem& it){
?????????????????? if(size==0) returnfalse;
?????????????????? else{
?????????????????? it = top->element;
?????????????????? SLink<Elem>* ltemp = top->next;
?????????????????? delete top;
?????????????????? top =ltemp;
?????????????????? size--;
?????????????????? returntrue;
?????????????????? }
?
???????? }
???????? //获取栈顶值
???????? booltopValue(Elem& it){
?????????????????? if(size == 0)returnfalse;
?????????????????? it = top->element;
?????????????????? returntrue;
???????? }
???????? //获取栈长
???????? intlength() const{
?????????????????? return size;
???????? }
???????? //逆置栈,相关操作可参考顺序表实现
???????? voidreverlist(){
?????????????????? Elem it;
?????????????????? Elem A;
?????????????????? AStack<Elem> ls(size - 1);
?????????????????? for (int i = 0; i < size; i++){
??????????????????????????? this->pop(A);
??????????????????????????? while (this->length())
??????????????????????????? {
???????????????????????????????????? this->pop(it);
???????????????????????????????????? ls.push(it);
??????????????????????????? }
??????????????????????????? this->push(A);
??????????????????????????? while (ls.length())
??????????????????????????? {
???????????????????????????????????? ls.pop(it);
???????????????????????????????????? this->push(it);
??????????????????????????? }
?????????????????? }
???????? }
?
};
?
#endif