链栈和顺序栈的实现

?

顺序栈和链栈是我复习的第二部分，同样是把之前的代码整理出来，发布给大家，实现的方法并不

难，毕竟是最基本的方法嘛。关于代码的解释已经写成注释。所以不用多说了。大家好好看代码吧~

下面的代码是栈的实习，完整代码实现下载地址；

//顺序栈

//

#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

链栈和顺序栈的实现

原文：http://448230305.iteye.com/blog/2193377