深圳网站开发建设,网站的首页文案,安阳哪里有学做网站的学校,佛山企业网站建设技术数据结构探险—栈篇 什么是栈#xff1f; 古代栈就是牲口棚的意思。 栈是一种机制#xff1a;后进先出 LIFO#xff08;last in first out#xff09; 电梯 栈要素空栈。栈底#xff0c;栈顶。没有元素的时候#xff0c;栈顶和栈底指向同一个元素#xff0c;如果加入新元… 数据结构探险—栈篇 什么是栈 古代栈就是牲口棚的意思。 栈是一种机制后进先出 LIFOlast in first out 电梯 栈要素 空栈。栈底栈顶。没有元素的时候栈顶和栈底指向同一个元素如果加入新元素栈顶不断升高。取出数据时栈顶不断地降低。栈顶和栈底都称之为栈要素。 通过demo说明栈的基本原理热身运动-进制转换十进制转换到二进制八进制十六进制N (N div d) * d N mod d步步为营- 括号匹配检测检测一个字符串中的各种括号是否匹配[()] [()()] [()[()]]实例介绍 栈要求 mystack.h: #ifndef MYSTACK_H
#define MYSTACK_H
class MyStack
{
public:MyStack(int size); //分配内存初始化栈空间设定栈容量栈顶~MyStack(); //回收栈空间内存bool stackEmpty(); //判断栈是否为空bool stackFull(); //判断栈是否为满void clearStack(); //清空栈int stackLength(); //栈中元素的个数bool push(char elem); //将元素压入栈中栈顶上升bool pop(char elem); //将元素推出栈栈顶下降void stackTraverse(bool isFromButtom); //遍历栈中元素并输出
private:int m_iTop; //栈顶栈中元素个数int m_iSize; //栈容量char *m_pBuffer; //栈空间指针
};#endifmystack.cpp: #include Mystack.h
#include iostream
using namespace std;MyStack::MyStack(int size)
{m_iSize size;m_pBuffer new char[size];m_iTop 0;
}
MyStack::~MyStack()
{delete[]m_pBuffer;m_pBuffer NULL;}
bool MyStack::stackEmpty()
{if (m_iTop 0)//if(0 m_iTop){return true;}else{return false;}
}
bool MyStack::stackFull()
{if ( m_iTop m_iSize)//{return true;}else{return false;}
}void MyStack::clearStack()
{m_iTop 0;//原栈中所有值无效
}int MyStack::stackLength()
{return m_iTop;
}bool MyStack::push(char elem)//放入栈顶
{if (stackFull()){return false;}m_pBuffer[m_iTop] elem;m_iTop;return true;
}
bool MyStack::pop(char elem)
{if (stackEmpty()){return false;}m_iTop--;//因为入栈时做了使栈顶指向下一个空位置elem m_pBuffer[m_iTop];return true;
}//char MyStack::pop()
//{
// if (stackEmpty())
// {
// throw 1;
// }
// else
// {
// m_iTop--;
// return m_pBuffer[m_iTop];
// }
//}void MyStack::stackTraverse(bool isFromButtom)
{if (isFromButtom){for (int i 0; i m_iTop; i){cout m_pBuffer[i] ,;}}else{for (int i m_iTop - 1; i 0; i--){cout m_pBuffer[i] ,;}}}main.cpp: #include Mystack.h
#include iostream
#include stdlib.h
using namespace std;
int main(void)
{MyStack *pStack new MyStack(5);pStack-push(h);//底pStack-push(e);pStack-push(l);pStack-push(l);pStack-push(o);//顶pStack-stackTraverse(true);char elem 0;pStack-pop(elem);cout endl;cout elem endl;//pStack-clearStack();pStack-stackTraverse(false);cout pStack-stackLength() endl;if (pStack-stackEmpty()){cout 栈为空 endl;}if (pStack-stackFull()){cout 栈为满 endl;}delete pStack;pStack NULL;system(pause);return 0;
}运行结果 栈运行结果 案例改造。 要求 栈改造要求 #ifndef MYSTACK_H
#define MYSTACK_H
#include Coordinate.h
class MyStack
{
public:MyStack(int size); //分配内存初始化栈空间设定栈容量栈顶~MyStack(); //回收栈空间内存bool stackEmpty(); //判断栈是否为空bool stackFull(); //判断栈是否为满void clearStack(); //清空栈int stackLength(); //栈中元素的个数bool push(Coordinate elem); //将元素压入栈中栈顶上升bool pop(Coordinate elem); //将元素推出栈栈顶下降void stackTraverse(bool isFromButtom); //遍历栈中元素并输出
private:int m_iTop; //栈顶栈中元素个数int m_iSize; //栈容量Coordinate *m_pBuffer; //栈空间指针
};
#endif#include Mystack.h
#include iostream
using namespace std;MyStack::MyStack(int size)
{m_iSize size;m_pBuffer new Coordinate[size];m_iTop 0;
}
MyStack::~MyStack()
{delete[]m_pBuffer;m_pBuffer NULL;}
bool MyStack::stackEmpty()
{if (m_iTop 0)//if(0 m_iTop){return true;}else{return false;}
}
bool MyStack::stackFull()
{if ( m_iTop m_iSize)//{return true;}else{return false;}
}void MyStack::clearStack()
{m_iTop 0;//原栈中所有值无效
}int MyStack::stackLength()
{return m_iTop;
}bool MyStack::push(Coordinate elem)//放入栈顶
{if (stackFull()){return false;}m_pBuffer[m_iTop] elem;//因为这里的coordinate是一个简单的复制。所以使用默认拷贝函数就可以了m_iTop;return true;
}
bool MyStack::pop(Coordinate elem)
{if (stackEmpty()){return false;}m_iTop--;//因为入栈时做了使栈顶指向下一个空位置elem m_pBuffer[m_iTop];return true;
}//char MyStack::pop()
//{
// if (stackEmpty())
// {
// throw 1;
// }
// else
// {
// m_iTop--;
// return m_pBuffer[m_iTop];
// }
//}void MyStack::stackTraverse(bool isFromButtom)
{if (isFromButtom){for (int i 0; i m_iTop; i){//cout m_pBuffer[i] ,;m_pBuffer[i].printCoordinate();}}else{for (int i m_iTop - 1; i 0; i--){//cout m_pBuffer[i] ,;m_pBuffer[i].printCoordinate();}}}#ifndef COORDINATE_H
#define COORDINATE_H
class Coordinate
{
public:Coordinate(int x0,int y0);void printCoordinate();
private:int m_iX;int m_iY;
};
#endif#include Coordinate.h
#include iostream
using namespace std;Coordinate::Coordinate(int x, int y)
{m_iX x;m_iY y;
}
void Coordinate::printCoordinate()
{cout ( m_iX , m_iY ) endl;
}main.cpp: #include Mystack.h
#include iostream
#include stdlib.h
using namespace std;
int main(void)
{MyStack *pStack new MyStack(5);pStack-push(Coordinate(1,2));//底pStack-push(Coordinate(3, 4));pStack-stackTraverse(true);pStack-stackTraverse(false);cout pStack-stackLength() endl;delete pStack;pStack NULL;system(pause);return 0;
}运行结果 改造后运行结果 经过改造我们使栈满足了coordinate对象的入栈出栈。 将普通栈改为类模板栈。使其可以适用于任何数据类型 类模板栈实现要求 上面我们实现过两遍对于栈的实现。一次是实现char数组的栈。一次是实现coordinate对象的。两次除过数据类型。差别不是很大。所以本次我们使用类模板实现适用任何数据类型的栈 mystack.h:(因为编译器不支持类模板分开编译。所以cpp为空) #ifndef MYSTACK_H
#define MYSTACK_H
#include iostream
using namespace std;
template typename T
class MyStack
{
public:MyStack(int size); //分配内存初始化栈空间设定栈容量栈顶~MyStack(); //回收栈空间内存bool stackEmpty(); //判断栈是否为空bool stackFull(); //判断栈是否为满void clearStack(); //清空栈int stackLength(); //栈中元素的个数bool push(T elem); //将元素压入栈中栈顶上升bool pop(T elem); //将元素推出栈栈顶下降void stackTraverse(bool isFromButtom); //遍历栈中元素并输出
private:int m_iTop; //栈顶栈中元素个数int m_iSize; //栈容量T *m_pBuffer; //栈空间指针
};template typename T
MyStackT::MyStack(int size)
{m_iSize size;m_pBuffer new T[size];m_iTop 0;
}
template typename T
MyStackT::~MyStack()
{delete[]m_pBuffer;m_pBuffer NULL;}
template typename T
bool MyStackT::stackEmpty()
{if (m_iTop 0)//if(0 m_iTop){return true;}else{return false;}
}
template typename T
bool MyStackT::stackFull()
{if (m_iTop m_iSize)//{return true;}else{return false;}
}
template typename T
void MyStackT::clearStack()
{m_iTop 0;//原栈中所有值无效
}
template typename T
int MyStackT::stackLength()
{return m_iTop;
}
template typename T
bool MyStackT::push(T elem)//放入栈顶
{if (stackFull()){return false;}m_pBuffer[m_iTop] elem;//因为这里的coordinate是一个简单的复制。所以使用默认拷贝函数就可以了m_iTop;return true;
}
template typename T
bool MyStackT::pop(T elem)
{if (stackEmpty()){return false;}m_iTop--;//因为入栈时做了使栈顶指向下一个空位置elem m_pBuffer[m_iTop];return true;
}//char MyStack::pop()
//{
// if (stackEmpty())
// {
// throw 1;
// }
// else
// {
// m_iTop--;
// return m_pBuffer[m_iTop];
// }
//}
template typename T
void MyStackT::stackTraverse(bool isFromButtom)
{if (isFromButtom){for (int i 0; i m_iTop; i){cout m_pBuffer[i];//m_pBuffer[i].printCoordinate();}}else{for (int i m_iTop - 1; i 0; i--){cout m_pBuffer[i];//m_pBuffer[i].printCoordinate();}}}
#endif #ifndef COORDINATE_H
#define COORDINATE_H
#include ostream
using namespace std;
class Coordinate
{friend ostream operator(ostream out, Coordinate coor);
public:Coordinate(int x0,int y0);void printCoordinate();
private:int m_iX;int m_iY;
};
#endif#include Coordinate.h
#include iostream
using namespace std;Coordinate::Coordinate(int x, int y)
{m_iX x;m_iY y;
}
void Coordinate::printCoordinate()
{cout ( m_iX , m_iY ) endl;
}ostream operator(ostream out, Coordinate coor)
{out ( coor.m_iX , coor.m_iY ) endl;return out;
}main.cpp: #include Mystack.h
#include iostream
#include stdlib.h
#include Coordinate.h
using namespace std;
int main(void)
{MyStackCoordinate *pStack new MyStackCoordinate(5);pStack-push(Coordinate(1,2));//底pStack-push(Coordinate(3, 4));pStack-stackTraverse(true);pStack-stackTraverse(false);cout pStack-stackLength() endl;MyStackchar *pStack2 new MyStackchar(5);pStack2-push(h);//底pStack2-push(e);pStack2-push(l);pStack2-push(l);pStack2-push(o);//顶pStack2-stackTraverse(true);delete pStack;pStack NULL;system(pause);return 0;
}类模板栈运行结果 可以看到我们的类模板已经将栈改造成了通用数据类型的栈。 栈应用-进制转换 进制转换 短除法。不停除以进制数。保留余数。然后商继续除以进制保留余数。直到商为0 栈的应用将每次的余数4 0 5 2 入栈。然后从栈顶开始打印。 #ifndef MYSTACK_H
#define MYSTACK_H
#include iostream
using namespace std;
template typename T
class MyStack
{
public:MyStack(int size); //分配内存初始化栈空间设定栈容量栈顶~MyStack(); //回收栈空间内存bool stackEmpty(); //判断栈是否为空bool stackFull(); //判断栈是否为满void clearStack(); //清空栈int stackLength(); //栈中元素的个数bool push(T elem); //将元素压入栈中栈顶上升bool pop(T elem); //将元素推出栈栈顶下降void stackTraverse(bool isFromButtom); //遍历栈中元素并输出
private:int m_iTop; //栈顶栈中元素个数int m_iSize; //栈容量T *m_pBuffer; //栈空间指针
};template typename T
MyStackT::MyStack(int size)
{m_iSize size;m_pBuffer new T[size];m_iTop 0;
}
template typename T
MyStackT::~MyStack()
{delete[]m_pBuffer;m_pBuffer NULL;}
template typename T
bool MyStackT::stackEmpty()
{if (m_iTop 0)//if(0 m_iTop){return true;}else{return false;}
}
template typename T
bool MyStackT::stackFull()
{if (m_iTop m_iSize)//{return true;}else{return false;}
}
template typename T
void MyStackT::clearStack()
{m_iTop 0;//原栈中所有值无效
}
template typename T
int MyStackT::stackLength()
{return m_iTop;
}
template typename T
bool MyStackT::push(T elem)//放入栈顶
{if (stackFull()){return false;}m_pBuffer[m_iTop] elem;//因为这里的coordinate是一个简单的复制。所以使用默认拷贝函数就可以了m_iTop;return true;
}
template typename T
bool MyStackT::pop(T elem)
{if (stackEmpty()){return false;}m_iTop--;//因为入栈时做了使栈顶指向下一个空位置elem m_pBuffer[m_iTop];return true;
}//char MyStack::pop()
//{
// if (stackEmpty())
// {
// throw 1;
// }
// else
// {
// m_iTop--;
// return m_pBuffer[m_iTop];
// }
//}
template typename T
void MyStackT::stackTraverse(bool isFromButtom)
{if (isFromButtom){for (int i 0; i m_iTop; i){cout m_pBuffer[i];//m_pBuffer[i].printCoordinate();}}else{for (int i m_iTop - 1; i 0; i--){cout m_pBuffer[i];//m_pBuffer[i].printCoordinate();}}}
#endif#include Mystack.h
#include iostream
#include stdlib.h
using namespace std;#define BINARY 2
#define OCTONARY 8
#define HEXADECIMAL 16int main(void)
{MyStackint *pStack new MyStackint(30);int N 1348;int mod 0;while (N !0){mod N % BINARY;pStack-push(mod);N N / BINARY;}pStack-stackTraverse(false);delete pStack;pStack NULL;system(pause);return 0;
}二进制和8进制都没有问题了16进制还需要进一步改造。 运行结果 !运行结果](http://upload-images.jianshu.io/upload_images/1779926-c6c62f86ff27da42.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) 16进制改造 mystack.h与原来一致。 #include Mystack.h
#include iostream
#include stdlib.h
using namespace std;#define BINARY 2
#define OCTONARY 8
#define HEXADECIMAL 16int main(void)
{char num[] 0123456789ABCDEF;MyStackchar *pStack new MyStackchar(30);int N 2016;int mod 0;while (N !0){mod N % HEXADECIMAL;pStack-push(num[mod]);N N / HEXADECIMAL;}pStack-stackTraverse(false);/*for (int ipStack-stackLength()-1;i0;i--){num[pStack[i]]}*//*int elem 0;while (!pStack-stackEmpty()){pStack-pop(elem);cout num[elem];}*/delete pStack;pStack NULL;system(pause);return 0;
}如果仍使栈为int型。则可以使用注释部分打印出内容。修改为char之后。可使用pStack-push(num[mod]); 栈应用括号匹配 括号匹配 从前往后扫描。左方括号入栈左圆括号入栈当遇到右括号则左圆括号出栈。当遇到右方括号左方括号出栈。字符串扫描完毕时栈为空则全部匹配。栈中还有东西则不是全部匹配 #include Mystack.h
#include iostream
#include stdlib.h
using namespace std;int main(void)
{MyStackchar *pStack new MyStackchar(30);//已存入的字符MyStackchar *pNeedStack new MyStackchar(30);//需要的字符。char str[] [()]];char currentNeed 0;for (int i0;istrlen(str);i){if (str[i] ! currentNeed)//如果此时扫描到的字符不是我们所需要的。{pStack-push(str[i]);//那么将这个字符存入“已存入字符”switch (str[i])//对于这个字符生成它的currentneed{case [:if (currentNeed !0)//如果currentneed已经有值不为初值。{pNeedStack-push(currentNeed);//将当前的需要字符入栈。}currentNeed ];//生成当前需要。break;case (:if (currentNeed ! 0){pNeedStack-push(currentNeed);}currentNeed );break;default:cout 字符串不匹配 endl;system(pause);return 0;}}else{char elem;pStack-pop(elem);if (pNeedStack-pop(currentNeed)){currentNeed 0;}}}if (pStack-stackEmpty()){cout 字符串括号匹配 endl;}delete pStack;pStack NULL;delete pNeedStack;pNeedStack NULL;system(pause);return 0;
}运行过程 最开始currentneed为0. str[0]为[,此时需要的currentneed为0不相等。进入if内部。将[ 存入栈1。进入switch的case内部。匹配到case:[此时判断到当前的currentneed 0.不满足if。则生成currentneed ]。并break 出循环。str[1]为此时需要的currentneed是]不相等。进入if内部将(存入栈1.进入switch的case内部。匹配到case(此时判断到当前的currentneed ]不等于0.将该字符存入需要栈因为下面就要对他进行覆盖了、生成新的的currentneed)并break出循环str[2]为)正好与我们当前的currentneed一致。那么我们将栈一的(弹出。并将needstack里的上一个急需的赋值给currentneed。进入下一次循环。也就是currentneed变量里面存放的是当前下一次循环刚开始急需匹配的。 need栈里存放的是历史需要的。 当当前需要的和正在扫描的一致。则将栈1中出栈。
