c++实现栈记录。   
  
  

基础版

MyStack.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#ifndef MYSTACK_H
#define MYSTACK_H

class MyStack
{
public:
MyStack(int size); //分配内存初始化栈空间,设定栈容量,栈顶
~MyStack(); //回收栈空间内存
bool stackEmpty(); //判定栈是否为空,为空则返回true,非空返回false
bool stackFull(); //判定栈是否已满,为满返回true,不满返回false
void clearStack(); //清空栈
int stackLength(); //已有元素的个数
bool push(char elem); //元素入栈,栈顶上升
bool pop(char &elem); //元素出栈,栈顶下降
void stackTraverse(bool isFromButtom); //遍历栈中所有元素

private:
char* m_pBuffer; //栈空间指针
int m_iSize; //栈容量
int m_iTop; //栈顶,栈中元素个数
};

#endif

MyStack.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#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;
}

bool MyStack::stackEmpty()
{
if (0 == m_iTop)//if(m_iTop==0)
{
return true;
}
return false;
}

bool MyStack::stackFull()
{
if (m_iTop == m_iSize)//>=
{
return true;
}
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;
}

// char MyStack::pop()
// {
// if (stackEmpty())
// {
// throw 1;
// }
// else
// {
// m_iTop--;
// return m_pBuffer[m_iTop];
// }
// }

bool MyStack::pop(char &elem)
{
if (stackEmpty())
{
return false;
}
m_iTop--;
elem = m_pBuffer[m_iTop];
return true;
}

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] << ",";
}

}
}

demo.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include "stdlib.h"
#include "MyStack.h"
using namespace std;

/*************************************************************************/
/*
栈类
要求:
MyStack(int size); //分配内存初始化栈空间,设定栈容量,栈顶
~MyStack(); //回收栈空间内存
bool stackEmpty(); //判定栈是否为空,为空则返回true,非空返回false
bool stackFull(); //判定栈是否已满,为满返回true,不满返回false
void clearStack(); //清空栈
int stackLength(); //已有元素的个数
void push(char elem); //元素入栈,栈顶上升
char pop(char &elem); //元素出栈,栈顶下降
void stackTraverse(); //遍历栈中所有元素

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

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

运行

result
result

中级版——复杂数据类型

Coordinate.h

若数据类型较复杂,例如数据类型为Coordinate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#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;
};

#endif

Coordinate.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#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;
}

demo.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include "stdlib.h"
#include "MyStack.h"
using namespace std;

/*************************************************************************/
/*

要求:
1.定义Coordinate坐标类
2.改造栈类,使其可以使用于坐标类

目的:灵活掌握栈机制,理解抽象数据类型在栈中的应用
*/
/*************************************************************************/

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;
if (pStack->stackEmpty())
{
cout << "栈为空" << endl;
}

if (pStack->stackFull())
{
cout << "栈为满" << endl;
}


delete pStack;
pStack = NULL;
system("pause");
return 0;
}

运行结果

(1,2)
(3,4)
(3,4)
(1,2)
2

高级版——类模板

去掉MyStack.cpp

MyStack.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#ifndef MYSTACK_H
#define MYSTACK_H

template <typename T>
class MyStack
{
public:
MyStack(int size); //分配内存初始化栈空间,设定栈容量,栈顶
~MyStack(); //回收栈空间内存
bool stackEmpty(); //判定栈是否为空,为空则返回true,非空返回false
bool stackFull(); //判定栈是否已满,为满返回true,不满返回false
void clearStack(); //清空栈
int stackLength(); //已有元素的个数
bool push(T elem); //元素入栈,栈顶上升
bool pop(T &elem); //元素出栈,栈顶下降
void stackTraverse(bool isFromButtom); //遍历栈中所有元素

private:
T *m_pBuffer; //栈空间指针
int m_iSize; //栈容量
int m_iTop; //栈顶,栈中元素个数
};
template<typename T>
MyStack<T>::MyStack(int size)
{
m_iSize = size;
m_pBuffer = new T[size];
m_iTop = 0;

}

template<typename T>
MyStack<T>::~MyStack()
{
delete[]m_pBuffer;
}

template<typename T>
bool MyStack<T>::stackEmpty()
{
if (0 == m_iTop)//if(m_iTop==0)
{
return true;
}
return false;
}

template<typename T>
bool MyStack<T>::stackFull()
{
if (m_iTop == m_iSize)//>=
{
return true;
}
return false;
}

template<typename T>
void MyStack<T>::clearStack()
{
m_iTop = 0;
}

template<typename T>
int MyStack<T>::stackLength()
{
return m_iTop;
}

template<typename T>
bool MyStack<T>::push(T elem)
{
if (stackFull())
{
return false;
}
m_pBuffer[m_iTop] = elem;
m_iTop++;//指向空位置
return true;
}


template<typename T>
bool MyStack<T>::pop(T &elem)
{
if (stackEmpty())
{
return false;
}
m_iTop--;
elem = m_pBuffer[m_iTop];
return true;
}

template<typename T>
void MyStack<T>::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];
}

}
}
#endif

Coordinate.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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;
};

#endif

Coordinate.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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;
}

demo.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include "stdlib.h"
#include "MyStack.h"
#include "Coordinate.h"

using namespace std;

/*************************************************************************/
/*
栈 类模板
要求:
将普通栈制造为类模板栈,使其可以适用于任何数据类型

目的:灵活掌握栈机制,理解抽象数据类型在栈中的应用
*/
/*************************************************************************/

int main(void)
{
MyStack<char> *pStack = new MyStack<char>(5);

pStack->push('h');
pStack->push('l');

pStack->stackTraverse(true);

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

运行结果

结果
结果

应用——进制转换

demo.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include "stdlib.h"
#include "MyStack.h"
#include "Coordinate.h"

using namespace std;

/*************************************************************************/
/*
栈应用——数制转换
描述:输入任意的十进制正整数N,分别输出该整数N的二进制、八进制、十六进制的数
公式:N=(N div d) * d + N mod d (div表示整除,mod表示求余)
(1348)(十进制) = (2504)(八进制) = (544)(十六进制) = (10101000100)(二进制)
短除法
N N div 8 N mod 8
1348 168 4
168 21 0
21 2 5
2 0 2

N N div 16 N mod 16
1348 84 4
84 5 4
5 0 5

目的:通过实例灵活掌握栈机制的使用技巧

*/
/*************************************************************************/

#define BINARY 2
#define OCTONARY 8
#define HEXADECTMAL 16
int main(void)
{
MyStack<int> *pStack = new MyStack<int>(30);

int N = 1348;
int mod = 0;

while (N != 0)
{
mod = N % OCTONARY;
pStack->push(mod);
N = N / OCTONARY;
}

pStack->stackTraverse(false);
delete pStack;
pStack = NULL;
system("pause");
return 0;
}

上述可使用于二进制、八进制,但对于十六进制还有些瑕疵。改进一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#define BINARY					2
#define OCTONARY 8
#define HEXADECTMAL 16
int main(void)
{
char num[] = "0123456789ABCDEF";
MyStack<int> *pStack = new MyStack<int>(30);

int N = 2016;
int mod = 0;

while (N != 0)
{
mod = N % HEXADECTMAL;
pStack->push(mod);
N = N / HEXADECTMAL;
}

// pStack->stackTraverse(false);

// for (int i = pStack->stackLength() - 1; i >= 0; i--)
// {
// num[pStack[i]]
// }

int elem = 0;
while (!pStack->stackEmpty())
{
pStack->pop(elem);
cout << num[elem];
}
delete pStack;
pStack = NULL;
system("pause");
return 0;
}

输出:7E0

应用——括号匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include "stdlib.h"
#include "MyStack.h"
#include "Coordinate.h"

using namespace std;

/*************************************************************************/
/*
栈应用——括号匹配
描述:任意输入一组括号,可以判断括号是否匹配
字符串示例:[()] [()()] [()[()]] [[()]
目的:通过实例灵活掌握栈机制的使用技巧
*/
/*************************************************************************/

int main(void)
{
MyStack<char> *pStack = new MyStack<char>(30);
MyStack<char> *pNeedStack = new MyStack<char>(30);

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

for (int i = 0; i < strlen(str); i++)
{
if (str[i] != currentNeed)
{
pStack->push(str[i]);
switch (str[i])
{
case '[':
if (currentNeed != 0)
{
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;
}
else
{
cout << "字符串括号不匹配" << endl;
}
delete pStack;
pStack = NULL;

delete pNeedStack;
pNeedStack = NULL;


system("pause");
return 0;
}

感觉示例代码存在问题,default后没有释放内存,存在内存泄漏。

更好的思路:一个MyStack即可,判断是否为左括号,是就push;否则是右括号,若不匹配,则cout不匹配,匹配则pop。最后栈是否为空,空则匹配。