-------------------siwuxie095

   

   

   

   

   

   

   

   

   

这里介绍 ,那么什么是栈呢?

   

从字面意思上来解释:栈者,牲口棚也

   

   

   

也就是说,在古代,栈就是牲口棚的意思

   

   

   

那么在计算机中,栈是什么呢?栈是一种机制

   

   

   

   

我们把这种机制也称为 栈机制,简言之,就是 后进先出

Last In First Out,简称 LIFO

   

   

   

   

如:当进入电梯时,先进电梯的人,在乘坐电梯之后,

他一定是后出来,而后进电梯的人,在乘坐电梯之后,

他一定是先出来

   

   

   

   

   

数据结构的角度上来讲,如果有一张表,用它来存各种元素,

则称之为

   

   

   

   

当这张表是空表时,称之为 空栈,在向这张表中放数据之前,

栈就拥有一个 栈底 和一个 栈顶

   

栈底 栈顶 在栈中没有数据时,它们都指向最后一个元素,

最下面的那个元素,当开始放数据之后,栈顶 就会不断的

升高,当取出数据时,栈顶 也会逐渐的降低

   

栈顶 栈底 也都称之为 栈要素

   

   

   

虽然栈的原理非常简单,但是栈的用途却非常大,如下:

   

1)进制转换

   

   

   

   

(2)括号匹配检验

   

   

   

   

   

   

   

   

   

程序 1:

   

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 isFromBottom); //遍历栈中所有元素

private:

char *m_pBuff; //栈空间指针

int m_iSize; //栈容量

int m_iTop; //栈顶,栈中元素个数

//栈底不用写,因为它永远不变,可以认为是 0

};

   

//掌握栈的实现原理和运行机制

#endif

   

   

   

MyStack.cpp:

   

#include "MyStack.h"

#include "stdlib.h"

#include <iostream>

using namespace std;

   

   

MyStack::MyStack(int size)

{

//初始化栈容量

m_iSize = size;

//采用数组的形式,为栈分配内存空间

m_pBuff = new char[m_iSize];

//栈顶为 0,即为空栈

m_iTop = 0;

}

   

   

   

MyStack::~MyStack()

{

delete[]m_pBuff;

m_pBuff = NULL;

}

   

   

bool MyStack::stackEmpty()

{

//如果栈顶为 0,则为空栈

//

//可以将 m_iTop==0 改写为 0==m_iTop 来提高代码质量

//因为当只写了一个等号时,后者会报错,而前者不会

if (0 == m_iTop)

{

return true;

}

return false;

//或写成如下形式:

//return m_iTop == 0 ? true : false;

}

   

   

bool MyStack::stackFull()

{

//如果栈顶等于(或大于等于)栈的容量,即满栈

if (m_iTop == m_iSize)// >=

{

return true;

}

return false;

   

//或写成如下形式:

//return m_iTop == m_iSize ? true : false;

}

   

   

void MyStack::clearStack()

{

//作为一个栈来说,里面的数据可以全为0,也可以不为0

//但这并不重要,因为判断当前位置有没有被使用,不取

//决于里面的数据,而取决于栈顶 m_iTop,当栈顶为0时,

//栈就被"清空"了,原有数据全部无效,将来再放数据时,

//覆盖原来的数据即可

m_iTop = 0;

}

   

   

int MyStack::stackLength()

{

return m_iTop;

}

   

   

//入栈:将元素放到栈顶

bool MyStack::push(char elem)

{

//如果栈满,就无法入栈

//

//栈满的处理方法有两种:

//一种是返回值为bool,直接返回false

//一种是返回值为void,通过throw抛出异常

if (stackFull())

{

return false;

}

   

//将元素放到栈顶

m_pBuff[m_iTop] = elem;

   

//元素存放完毕,栈顶就相应的上浮,

//指向下一个要入栈的位置,即空位置

m_iTop++;

   

return true;

   

}

   

//弹栈:也称出栈,将栈顶元素出栈

bool MyStack::pop(char &elem)

{

//如果栈为空,就无法出栈

//

//栈为空的处理方法也有两种:

//一种是返回值为void,直接返回false

//一种是返回值为char,同时没有参数,并抛出异常

if (stackEmpty())

{

return false;

}

   

//因为栈顶总是指向下一个空的位置

//所以要先m_iTop--,使得栈顶指向

//一个拥有元素的位置,才能出栈

m_iTop--;

   

//将当前栈顶元素赋值给elem

elem = m_pBuff[m_iTop];

   

return true;

}

   

   

////弹栈时栈为空的另一种处理方法

//char MyStack::pop()

//{

// if (stackEmpty())

// {

// throw 1;

// }

//

// m_iTop--;

//

// return m_pBuff[m_iTop];

//}

   

void MyStack::stackTraverse(bool isFromBottom)

{

if (isFromBottom)

{

//从栈底向栈顶做遍历

for (int i = 0; i < m_iTop; i++)

{

cout << m_pBuff[i] << " , ";

}

}

else

{

//从栈顶向栈底做遍历

for (int i = m_iTop - 1; i >= 0; i--)

{

cout << m_pBuff[i] << " , ";

}

}

   

cout << endl;

}

   

   

   

main.cpp:

   

#include "MyStack.h"

#include "stdlib.h"

#include <iostream>

using namespace std;

   

   

int main(void)

{

MyStack *p = new MyStack(5);

   

p->push('h');//栈底

p->push('e');

p->push('l');

p->push('l');

p->push('o');//栈顶

p->stackTraverse(true);

   

char elem = 0;

p->pop(elem);

cout << elem << endl;

   

p->stackTraverse(true);

   

//p->clearStack();

if (p->stackEmpty())

{

cout << "栈为空" << endl;

}

else if (p->stackFull())

{

cout << "栈为满" << endl;

}

else

{

cout << "栈中有 " << p->stackLength() << " 个元素" << endl;

}

   

   

delete p;

p = NULL;

   

system("pause");

return 0;

}

   

   

运行一览:

   

   

   

   

   

   

   

程序 2:

   

Coordinate.h:

   

#ifndef COORDINATE_H

#define COORDINATE_H

   

class Coordinate

{

public:

Coordinate(int x = 0, int y = 0);

void printCoordinate();

private:

int m_iX;

int m_iY;

};

   

//Coordinate的对象或引用作参数时,会调用拷贝构造函数,

//因为这里Coordinate的数据成员比较简单,没有涉及到指针,

//就使用默认拷贝构造函数即可

#endif

   

   

   

Coordinate.cpp:

   

#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;

}

   

   

   

MyStack.h:

   

#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 isFromBottom); //遍历栈中所有元素

private:

Coordinate *m_pBuff;//Coordinate类型的栈空间指针

int m_iSize; //栈容量

int m_iTop; //栈顶,栈中元素个数

//栈底不用写,因为它永远不变,可以认为是 0

};

   

//掌握栈的实现原理和运行机制

#endif

   

   

   

MyStack.cpp:

   

#include "MyStack.h"

#include "stdlib.h"

#include <iostream>

using namespace std;

   

   

MyStack::MyStack(int size)

{

//初始化栈容量

m_iSize = size;

//采用数组的形式,为栈分配内存空间

m_pBuff = new Coordinate[m_iSize];

//栈顶为 0,即为空栈

m_iTop = 0;

}

   

   

   

MyStack::~MyStack()

{

delete[]m_pBuff;

m_pBuff = NULL;

}

   

   

bool MyStack::stackEmpty()

{

//如果栈顶为 0,则为空栈

//

//可以将 m_iTop==0 改写为 0==m_iTop 来提高代码质量

//因为当只写了一个等号时,后者会报错,而前者不会

if (0 == m_iTop)

{

return true;

}

return false;

   

//或写成如下形式:

//return m_iTop == 0 ? true : false;

}

   

   

bool MyStack::stackFull()

{

//如果栈顶等于(或大于等于)栈的容量,即满栈

if (m_iTop == m_iSize)// >=

{

return true;

}

return false;

   

//或写成如下形式:

//return m_iTop == m_iSize ? true : false;

}

   

   

void MyStack::clearStack()

{

//作为一个栈来说,里面的数据可以全为0,也可以不为0

//但这并不重要,因为判断当前位置有没有被使用,不取

//决于里面的数据,而取决于栈顶 m_iTop,当栈顶为0时,

//栈就被"清空"了,原有数据全部无效,将来再放数据时,

//覆盖原来的数据即可

m_iTop = 0;

}

   

   

int MyStack::stackLength()

{

return m_iTop;

}

   

   

//入栈:将元素放到栈顶

bool MyStack::push(Coordinate elem)

{

//如果栈满,就无法入栈

//

//栈满的处理方法有两种:

//一种是返回值为bool,直接返回false

//一种是返回值为void,通过throw抛出异常

if (stackFull())

{

return false;

}

   

//将元素放到栈顶

m_pBuff[m_iTop] = elem;

   

//元素存放完毕,栈顶就相应的上浮,

//指向下一个要入栈的位置,即空位置

m_iTop++;

   

return true;

   

}

   

//弹栈:也称出栈,将栈顶元素出栈

bool MyStack::pop(Coordinate &elem)

{

//如果栈为空,就无法出栈

//

//栈为空的处理方法也有两种:

//一种是返回值为void,直接返回false

//一种是返回值为char,同时没有参数,并抛出异常

if (stackEmpty())

{

return false;

}

   

//因为栈顶总是指向下一个空的位置

//所以要先m_iTop--,使得栈顶指向

//一个拥有元素的位置,才能出栈

m_iTop--;

   

//将当前栈顶元素赋值给elem

elem = m_pBuff[m_iTop];

   

return true;

}

   

   

////弹栈时栈为空的另一种处理方法

//char MyStack::pop()

//{

// if (stackEmpty())

// {

// throw 1;

// }

//

// m_iTop--;

//

// return m_pBuff[m_iTop];

//}

   

void MyStack::stackTraverse(bool isFromBottom)

{

if (isFromBottom)

{

//从栈底向栈顶做遍历

for (int i = 0; i < m_iTop; i++)

{

m_pBuff[i].printCoordinate();

}

}

else

{

//从栈顶向栈底做遍历

for (int i = m_iTop - 1; i >= 0; i--)

{

m_pBuff[i].printCoordinate();

}

}

   

cout << endl;

}

   

   

   

main.cpp:

   

#include "MyStack.h"

#include "stdlib.h"

#include <iostream>

using namespace std;

   

   

int main(void)

{

MyStack *p = new MyStack(5);

   

   

p->push(Coordinate(1,2));//栈底

p->push(Coordinate(3,4));

p->push(Coordinate(5,6));

p->push(Coordinate(7,8));//栈顶

p->stackTraverse(true);

   

Coordinate elem(0, 0);

p->pop(elem);

elem.printCoordinate();

cout << endl;

   

p->stackTraverse(false);

   

//p->clearStack();

if (p->stackEmpty())

{

cout << "栈为空" << endl;

}

else if (p->stackFull())

{

cout << "栈为满" << endl;

}

else

{

cout << "栈中有 " << p->stackLength() << " 个元素" << endl;

}

   

   

   

delete p;

p = NULL;

   

system("pause");

return 0;

}

   

   

运行一览:

   

   

   

   

   

   

   

程序 3:应用类模板

   

Coordinate.h:

   

#ifndef COORDINATE_H

#define COORDINATE_H

   

#include <ostream>

using namespace std;

   

   

class Coordinate

{

friend ostream &operator<<(ostream &out, Coordinate &coor);

   

public:

Coordinate(int x = 0, int y = 0);

void printCoordinate();

private:

int m_iX;

int m_iY;

   

   

};

   

//Coordinate的对象或引用作参数时,会调用拷贝构造函数,

//因为这里Coordinate的数据成员比较简单,没有涉及到指针,

//就使用默认拷贝构造函数即可

#endif

   

   

   

Coordinate.cpp:

   

#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)

{

   

cout << "(" << coor.m_iX << "," << coor.m_iY << ")" << endl;

return out;

}

   

   

   

MyStack.h:

   

#ifndef MYSTACK_H

#define MYSTACK_H

   

#include "stdlib.h"

   

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 isFromBottom); //遍历栈中所有元素

private:

T *m_pBuff; //栈空间指针

int m_iSize; //栈容量

int m_iTop; //栈顶,栈中元素个数

//栈底不用写,因为它永远不变,可以认为是 0

};

   

//掌握栈的实现原理和运行机制

   

   

   

template<typename T>

MyStack<T>::MyStack(int size)

{

//初始化栈容量

m_iSize = size;

//采用数组的形式,为栈分配内存空间

m_pBuff = new T[m_iSize];

//栈顶为 0,即为空栈

m_iTop = 0;

}

   

   

template<typename T>

MyStack<T>::~MyStack()

{

delete[]m_pBuff;

m_pBuff = NULL;

}

   

   

template<typename T>

bool MyStack<T>::stackEmpty()

{

//如果栈顶为 0,则为空栈

//

//可以将 m_iTop==0 改写为 0==m_iTop 来提高代码质量

//因为当只写了一个等号时,后者会报错,而前者不会

if (0 == m_iTop)

{

return true;

}

return false;

   

//或写成如下形式:

//return m_iTop == 0 ? true : false;

}

   

   

template<typename T>

bool MyStack<T>::stackFull()

{

//如果栈顶等于(或大于等于)栈的容量,即满栈

if (m_iTop == m_iSize)// >=

{

return true;

}

return false;

   

//或写成如下形式:

//return m_iTop == m_iSize ? true : false;

}

   

   

template<typename T>

void MyStack<T>::clearStack()

{

//作为一个栈来说,里面的数据可以全为0,也可以不为0

//但这并不重要,因为判断当前位置有没有被使用,不取

//决于里面的数据,而取决于栈顶 m_iTop,当栈顶为0时,

//栈就被"清空"了,原有数据全部无效,将来再放数据时,

//覆盖原来的数据即可

m_iTop = 0;

}

   

   

template<typename T>

int MyStack<T>::stackLength()

{

return m_iTop;

}

   

   

//入栈:将元素放到栈顶

template<typename T>

bool MyStack<T>::push(T elem)

{

//如果栈满,就无法入栈

//

//栈满的处理方法有两种:

//一种是返回值为bool,直接返回false

//一种是返回值为void,通过throw抛出异常

if (stackFull())

{

return false;

}

   

//将元素放到栈顶

m_pBuff[m_iTop] = elem;

   

//元素存放完毕,栈顶就相应的上浮,

//指向下一个要入栈的位置,即空位置

m_iTop++;

   

return true;

   

}

   

   

//弹栈:也称出栈,将栈顶元素出栈

template<typename T>

bool MyStack<T>::pop(T &elem)

{

//如果栈为空,就无法出栈

//

//栈为空的处理方法也有两种:

//一种是返回值为void,直接返回false

//一种是返回值为T,同时没有参数,并抛出异常

if (stackEmpty())

{

return false;

}

   

//因为栈顶总是指向下一个空的位置

//所以要先m_iTop--,使得栈顶指向

//一个拥有元素的位置,才能出栈

m_iTop--;

   

//将当前栈顶元素赋值给elem

elem = m_pBuff[m_iTop];

   

return true;

}

   

   

////弹栈时栈为空的另一种处理方法

//template<typename T>

//T MyStack<T>::pop()

//{

// if (stackEmpty())

// {

// throw 1;

// }

//

// m_iTop--;

//

// return m_pBuff[m_iTop];

//}

   

template<typename T>

void MyStack<T>::stackTraverse(bool isFromBottom)

{

if (isFromBottom)

{

//从栈底向栈顶做遍历

for (int i = 0; i < m_iTop; i++)

{

cout << m_pBuff[i] << endl;

}

}

else

{

//从栈顶向栈底做遍历

for (int i = m_iTop - 1; i >= 0; i--)

{

cout << m_pBuff[i] << endl;

}

}

   

cout << endl;

}

   

#endif

   

   

   

main.cpp:

   

#include "MyStack.h"

#include "Coordinate.h"

#include "stdlib.h"

#include <iostream>

using namespace std;

   

   

int main(void)

{

MyStack<Coordinate> *p = new MyStack<Coordinate>(5);

   

p->push(Coordinate(1, 2));//栈底

p->push(Coordinate(3, 4));

p->push(Coordinate(5, 6));

p->push(Coordinate(7, 8));//栈顶

p->stackTraverse(true);

   

Coordinate elem(0, 0);

p->pop(elem);

elem.printCoordinate();

cout << endl;

   

p->stackTraverse(false);

   

//p->clearStack();

if (p->stackEmpty())

{

cout << "栈为空" << endl;

}

else if (p->stackFull())

{

cout << "栈为满" << endl;

}

else

{

cout << "栈中有 " << p->stackLength() << " 个元素" << endl;

}

   

   

   

delete p;

p = NULL;

   

system("pause");

return 0;

}

   

   

运行一览:

   

   

   

   

   

   

   

程序 4:进制转换

   

MyStack.h:

   

#ifndef MYSTACK_H

#define MYSTACK_H

   

#include "stdlib.h"

   

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 isFromBottom); //遍历栈中所有元素

private:

T *m_pBuff; //栈空间指针

int m_iSize; //栈容量

int m_iTop; //栈顶,栈中元素个数

//栈底不用写,因为它永远不变,可以认为是 0

};

   

//掌握栈的实现原理和运行机制

   

   

   

template<typename T>

MyStack<T>::MyStack(int size)

{

//初始化栈容量

m_iSize = size;

//采用数组的形式,为栈分配内存空间

m_pBuff = new T[m_iSize];

//栈顶为 0,即为空栈

m_iTop = 0;

}

   

   

template<typename T>

MyStack<T>::~MyStack()

{

delete[]m_pBuff;

m_pBuff = NULL;

}

   

   

template<typename T>

bool MyStack<T>::stackEmpty()

{

//如果栈顶为 0,则为空栈

//

//可以将 m_iTop==0 改写为 0==m_iTop 来提高代码质量

//因为当只写了一个等号时,后者会报错,而前者不会

if (0 == m_iTop)

{

return true;

}

return false;

   

//或写成如下形式:

//return m_iTop == 0 ? true : false;

}

   

   

template<typename T>

bool MyStack<T>::stackFull()

{

//如果栈顶等于(或大于等于)栈的容量,即满栈

if (m_iTop == m_iSize)// >=

{

return true;

}

return false;

   

//或写成如下形式:

//return m_iTop == m_iSize ? true : false;

}

   

   

template<typename T>

void MyStack<T>::clearStack()

{

//作为一个栈来说,里面的数据可以全为0,也可以不为0

//但这并不重要,因为判断当前位置有没有被使用,不取

//决于里面的数据,而取决于栈顶 m_iTop,当栈顶为0时,

//栈就被"清空"了,原有数据全部无效,将来再放数据时,

//覆盖原来的数据即可

m_iTop = 0;

}

   

   

template<typename T>

int MyStack<T>::stackLength()

{

return m_iTop;

}

   

   

//入栈:将元素放到栈顶

template<typename T>

bool MyStack<T>::push(T elem)

{

//如果栈满,就无法入栈

//

//栈满的处理方法有两种:

//一种是返回值为bool,直接返回false

//一种是返回值为void,通过throw抛出异常

if (stackFull())

{

return false;

}

   

//将元素放到栈顶

m_pBuff[m_iTop] = elem;

   

//元素存放完毕,栈顶就相应的上浮,

//指向下一个要入栈的位置,即空位置

m_iTop++;

   

return true;

   

}

   

   

//弹栈:也称出栈,将栈顶元素出栈

template<typename T>

bool MyStack<T>::pop(T &elem)

{

//如果栈为空,就无法出栈

//

//栈为空的处理方法也有两种:

//一种是返回值为void,直接返回false

//一种是返回值为T,同时没有参数,并抛出异常

if (stackEmpty())

{

return false;

}

   

//因为栈顶总是指向下一个空的位置

//所以要先m_iTop--,使得栈顶指向

//一个拥有元素的位置,才能出栈

m_iTop--;

   

//将当前栈顶元素赋值给elem

elem = m_pBuff[m_iTop];

   

return true;

}

   

   

////弹栈时栈为空的另一种处理方法

//template<typename T>

//T MyStack<T>::pop()

//{

// if (stackEmpty())

// {

// throw 1;

// }

//

// m_iTop--;

//

// return m_pBuff[m_iTop];

//}

   

template<typename T>

void MyStack<T>::stackTraverse(bool isFromBottom)

{

if (isFromBottom)

{

//从栈底向栈顶做遍历

for (int i = 0; i < m_iTop; i++)

{

cout << m_pBuff[i];

}

}

else

{

//从栈顶向栈底做遍历

for (int i = m_iTop - 1; i >= 0; i--)

{

cout << m_pBuff[i];

}

}

   

cout << endl;

}

   

#endif

   

   

   

main.cpp:

   

#include "MyStack.h"

#include "stdlib.h"

#include <iostream>

using namespace std;

   

   

#define BINARY 2

#define OCTONARY 8

#define HEXADECIMAL 16

   

//描述:输入任意十进制正整数数N,分别输出该正整数N的二进制、八进制、十六进制的数

//公式:N=(N div d) * d + N mod d div 表示整除,mod 表示求余,d 表示几进制)

int main(void)

{

MyStack<int> *p = new MyStack<int>(20);

   

//N可以换为其它值测试

int N = 1348;

int mod = 0;

   

while (N != 0)

{

//OCTONARY 换为 BINARYHEXADECIMAL 进行测试

mod = N % OCTONARY;

p->push(mod);

N = N / OCTONARY;

}

   

//p->stackTraverse(false);

   

//对于十六进制中大于等于10的部分用ABC...表示

char num[] = "0123456789ABCDEF";

   

//栈中的数据不变,让出栈的数据进行转换

int elem = 0;

while (!p->stackEmpty())

{

p->pop(elem);

cout << num[elem];

}

   

   

delete p;

p = NULL;

   

system("pause");

return 0;

}

   

   

   

   

   

   

程序 5:括号匹配

   

MyStack.h:

   

#ifndef MYSTACK_H

#define MYSTACK_H

   

#include "stdlib.h"

   

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 isFromBottom); //遍历栈中所有元素

private:

T *m_pBuff; //栈空间指针

int m_iSize; //栈容量

int m_iTop; //栈顶,栈中元素个数

//栈底不用写,因为它永远不变,可以认为是 0

};

   

//掌握栈的实现原理和运行机制

   

   

   

template<typename T>

MyStack<T>::MyStack(int size)

{

//初始化栈容量

m_iSize = size;

//采用数组的形式,为栈分配内存空间

m_pBuff = new T[m_iSize];

//栈顶为 0,即为空栈

m_iTop = 0;

}

   

   

template<typename T>

MyStack<T>::~MyStack()

{

delete[]m_pBuff;

m_pBuff = NULL;

}

   

   

template<typename T>

bool MyStack<T>::stackEmpty()

{

//如果栈顶为 0,则为空栈

//

//可以将 m_iTop==0 改写为 0==m_iTop 来提高代码质量

//因为当只写了一个等号时,后者会报错,而前者不会

if (0 == m_iTop)

{

return true;

}

return false;

   

//或写成如下形式:

//return m_iTop == 0 ? true : false;

}

   

   

template<typename T>

bool MyStack<T>::stackFull()

{

//如果栈顶等于(或大于等于)栈的容量,即满栈

if (m_iTop == m_iSize)// >=

{

return true;

}

return false;

   

//或写成如下形式:

//return m_iTop == m_iSize ? true : false;

}

   

   

template<typename T>

void MyStack<T>::clearStack()

{

//作为一个栈来说,里面的数据可以全为0,也可以不为0

//但这并不重要,因为判断当前位置有没有被使用,不取

//决于里面的数据,而取决于栈顶 m_iTop,当栈顶为0时,

//栈就被"清空"了,原有数据全部无效,将来再放数据时,

//覆盖原来的数据即可

m_iTop = 0;

}

   

   

template<typename T>

int MyStack<T>::stackLength()

{

return m_iTop;

}

   

   

//入栈:将元素放到栈顶

template<typename T>

bool MyStack<T>::push(T elem)

{

//如果栈满,就无法入栈

//

//栈满的处理方法有两种:

//一种是返回值为bool,直接返回false

//一种是返回值为void,通过throw抛出异常

if (stackFull())

{

return false;

}

   

//将元素放到栈顶

m_pBuff[m_iTop] = elem;

   

//元素存放完毕,栈顶就相应的上浮,

//指向下一个要入栈的位置,即空位置

m_iTop++;

   

return true;

   

}

   

   

//弹栈:也称出栈,将栈顶元素出栈

template<typename T>

bool MyStack<T>::pop(T &elem)

{

//如果栈为空,就无法出栈

//

//栈为空的处理方法也有两种:

//一种是返回值为void,直接返回false

//一种是返回值为T,同时没有参数,并抛出异常

if (stackEmpty())

{

return false;

}

   

//因为栈顶总是指向下一个空的位置

//所以要先m_iTop--,使得栈顶指向

//一个拥有元素的位置,才能出栈

m_iTop--;

   

//将当前栈顶元素赋值给elem

elem = m_pBuff[m_iTop];

   

return true;

}

   

   

////弹栈时栈为空的另一种处理方法

//template<typename T>

//T MyStack<T>::pop()

//{

// if (stackEmpty())

// {

// throw 1;

// }

//

// m_iTop--;

//

// return m_pBuff[m_iTop];

//}

   

template<typename T>

void MyStack<T>::stackTraverse(bool isFromBottom)

{

if (isFromBottom)

{

//从栈底向栈顶做遍历

for (int i = 0; i < m_iTop; i++)

{

cout << m_pBuff[i];

}

}

else

{

//从栈顶向栈底做遍历

for (int i = m_iTop - 1; i >= 0; i--)

{

cout << m_pBuff[i];

}

}

   

cout << endl;

}

   

#endif

   

   

   

main.cpp:

   

#include "MyStack.h"

#include "stdlib.h"

#include <string>

#include <iostream>

using namespace std;

   

//栈应用--括号匹配

//描述:任意输入一组括号,可以判断括号是否匹配(包括各种括号)

//字符串示例:[()][()()][()[()]][[()]

int main(void)

{

//p存储左括号,并非所有左括号

MyStack<char> *p = new MyStack<char>(30);

//q存储右括号,并非所有右括号,而是急需匹配的字符

MyStack<char> *q = new MyStack<char>(30);

   

char str[] = "[()]";

   

//currentNeed赋一个不可见的ASCII码值

char currentNeed = 0;

   

//扫描字符数组,即遍历

for (int i = 0; i < strlen(str); i++)

{

//如果扫描到的字符是急需匹配的字符,就都出栈

//否则,左括号入p栈,右括号入q

if (str[i] != currentNeed)

{

p->push(str[i]);

switch (str[i])

{

case '[':

if (currentNeed!=0)

{

q->push(currentNeed);

}

currentNeed = ']';

break;

case '(':

if (currentNeed != 0)

{

q->push(currentNeed);

}

currentNeed = ')';

break;

default:

cout << "字符串括号不匹配" << endl;

system("pause");

return 0;

}

}

else

{

char elem;

p->pop(elem);

//q中的右括号会先变为空,所以必须判断是否为空

if (!q->pop(currentNeed))

{

currentNeed = 0;

}

}

}

   

   

if (p->stackEmpty())

{

cout << "字符串括号匹配" << endl;

}

else

{

cout << "字符串括号不匹配" << endl;

}

   

   

delete p;

p = NULL;

delete q;

q = NULL;

system("pause");

return 0;

}

   

   

   

   

   

   

   

   

   

【made by siwuxie095】

原文地址:https://www.cnblogs.com/siwuxie095/p/6822987.html