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