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

中级版——复杂数据类型

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。最后栈是否为空,空则匹配。

文章目录
  1. 1. 基础版
    1. 1.1. MyStack.h
    2. 1.2. MyStack.cpp
    3. 1.3. demo.cpp
    4. 1.4. 运行
  2. 2. 中级版——复杂数据类型
    1. 2.1. Coordinate.h
    2. 2.2. Coordinate.cpp
    3. 2.3. demo.cpp
    4. 2.4. 运行结果
  3. 3. 高级版——类模板
    1. 3.1. MyStack.h
    2. 3.2. Coordinate.h
    3. 3.3. Coordinate.cpp
    4. 3.4. demo.cpp
    5. 3.5. 运行结果
  4. 4. 应用——进制转换
  5. 5. 应用——括号匹配
|