《数据结构、算法与应用C++语言描述》使用C++语言实现数组栈

《数据结构、算法与应用C++语言描述》使用C++语言实现数组栈

完整代码见：Github::Data-Structures-Algorithms-and-Applications/_8stack/

定义

栈的定义

把线性表的插入和删除操作限制在同一端进行，就得到栈数据结构。因此，栈是一个后进先出（last-in-first-out，LIFO）的数据结构。

栈（stack）是一种特殊的线性表，其插入（也称入栈或压栈）和删除（也称出栈或弹栈）操作都在表的同一端进行。这一端称为栈顶（top），另一端称为栈底（bottom）。

递归工作栈

计算机是如何执行递归函数的呢？

答案是使用递归工作栈（recursionstack）。当一个函数被调用时，一个返回地址（即被调函数一旦执行完，接下去要执行的程序指令的地址）和被调函数的局部变量和形参的值都要存储在递归工作栈中。当执行一次返回时，被调函数的局部变量和形参的值被恢复为调用之前的值（这些值存储在递归工作栈的顶部），而且程序从返回地址处继续执行，这个返回地址也存储在递归工作栈的顶部。

栈的抽象数据类型

代码

_14stack.h

抽象类栈。

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			抽象类栈
*/
#pragma once
#ifndef _STACK_H_
#define _STACK_H_
/*抽象类栈*/
template<class T>
class stack
{
public:
	virtual ~stack() {}
	//返回true，当且仅当栈为空
	virtual bool empty() const = 0;
	//返回栈中元素个数
	virtual int size() const = 0;
	//返回栈顶元素的引用
	virtual T& top() = 0;
	//删除栈顶元素
	virtual T pop() = 0;
	//将元素theElement压入栈顶
	virtual void push(const T& theELment) = 0;
};
#endif
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

_15arrayStack.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			数组存储的栈类的头文件
*/
#pragma once
#ifndef _ARRAYSTACK_H_
#define _ARRAYSTACK_H_
#include "_1myExceptions.h"
#include "_14stack.h"
#include
#include
#include
using std::ostringstream;
using std::endl;
using std::cout;
using std::istream;
using std::ostream;
using std::string;
//测试函数
void arrayStackTest();
/*
作用：将数组的长度加倍
输入：指针a指向需要改变长度的数组，oldLength表示数组原来的长度，newLength表示需要改变的新长度
结果：将数组扩容/缩容 为newLength
*/
template<class T>
void changeLength(T*& a, int oldLength, int newLength)
{
	if (newLength < 0)
		throw illegalParameterValue("new length must be >= 0");
	T* temp = new T[newLength];
	int number = min(oldLength, newLength);
	copy(a, a + number, temp);
	delete[] a;
	a = temp;
}

/*本来可以直接派生arrayList来实现，但是该方法会损失性能。*/
/*因此本节开发一个类，利用数组来包含所有的栈元素*/
template<class T>
class arrayStack :public stack<T>
{
public:
	arrayStack(int initialCapacity = 10);
	~arrayStack() { delete[] stack; }
	bool empty() const { return stackTop == -1; }
	int size() const { return stackTop + 1; }
	int capacity() const { return stackLength; }
	T& top()
	{
		if (stackTop == -1)
			throw stackEmpty();
		return stack[stackTop];
	}
	T pop()
	{
		if (stackTop == -1)
			throw stackEmpty();
		T temp = stack[stackTop];
		stack[stackTop--].~T();//T的析构函数
		while (stackTop + 1 < stackLength / 4)
		{
			changeLength(stack, stackLength, stackLength / 2);
			stackLength /= 2;
		}
		return temp;
	}
	void push(const T& theElement);
	void clear() { stackTop = -1; }
	void split(arrayStack<T>& a, arrayStack<T>& b);
	void merge(arrayStack<T>& a);

	/*重载操作符*/
	/*重载操作符[]*/
	T& operator[](int i) { return stack[i]; }

	/*友元函数*/
	friend istream& operator>> <T>(istream& in, arrayStack<T>& m);
	//输出但是不pop()元素
	friend ostream& operator<< <T>(ostream& out, arrayStack<T>& m);
private:
	int stackTop;//当前栈顶
	int stackLength;//栈容量
	T* stack;//元素数组
};
/*友元函数*/
/*>>操作符*/
template<class T>
istream& operator>>(istream& in, arrayStack<T>& m)
{
	int numberOfElement = 0;
	cout << "Please enter the number of element:";
	while (!(in >> numberOfElement))
	{
		in.clear();//清空标志位
		while (in.get() != '\n')//删除无效的输入
			continue;
		cout << "Please enter the number of element:";
	}
	T cinElement;
	for (int i = 0; i < numberOfElement; i++)
	{
		cout << "Please enter the element " << i + 1 << ":";
		while (!(in >> cinElement))
		{
			in.clear();//清空标志位
			while (in.get() != '\n')//删除无效的输入
				continue;
			cout << "Please enter the element " << i + 1 << ":";
		}
		m.push(cinElement);
	}
	return in;
}
/*<<操作符*/
template<class T>
ostream& operator<<(ostream& out, arrayStack<T>& m)
{
	for (int i = 0; i <= m.stackTop; i++)
		out << m.stack[i] << "  ";
	out << endl;
	return out;
}

/*构造函数*/
template<class T>
arrayStack<T>::arrayStack(int initialCapacity)
{
	if (initialCapacity < 1)
	{
		ostringstream s("");
		s << "Initial capacity = " << initialCapacity << "Must be > 0";
		throw illegalParameterValue(s.str());
	}
	stackLength = initialCapacity;
	stack = new T[initialCapacity];
	stackTop = -1;
}

/*将元素theElement压入栈*/
template<class T>
void arrayStack<T>::push(const T& theElement)
{
	if (stackTop == stackLength - 1)
	{
		//空间已满，容量加倍
		changeLength(stack, stackLength, 2 * stackLength);
		stackLength *= 2;
	}
	stack[++stackTop] = theElement;
}
/*将一个栈分裂为两个栈。第一个栈包含从栈底开始的一半元素，第二个栈包含剩余元素*/
template<class T>
void arrayStack<T>::split(arrayStack<T>& a, arrayStack<T>& b)
{
	//首先清空a,b栈
	b.clear();
	a.clear();
	/*将当前栈中的前一半元素存入a栈中*/
	int i = 0;
	for (i = 0; i <= stackTop / 2; i++)
		a.push(stack[i]);
	/*将当前栈中的后一半元素存入b栈中*/
	for (; i <= stackTop; i++)
		b.push(stack[i]);
}
/*将两个栈合并，把第二个栈的所有元素置于第一个栈的顶部。不改变第二个栈中元素的相对顺序*/
template<class T>
void arrayStack<T>::merge(arrayStack<T>& a)
{
	for (int i = 0; i <= a.stackTop; i++)
		push(a.stack[i]);
}
#endif
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176

_15arrayStack.cpp

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			测试_15arrayStack.h头文件中的所有函数
*/
// test array based sparse matrix class

#include 
#include "_15arrayStack.h"
using namespace std;

/*测试函数*/
void arrayStackTest()
{
	cout << endl << "*********************************arrayStackTest()函数开始*************************************" << endl;
	arrayStack<int> a;

	//测试输入和输出
	cout << endl << "测试友元函数*******************************************" << endl;
	cout << "输入输出************************" << endl;
	cin >> a;
	cout << "arrayStack a is:" << a;//arrayStack a is:1  2  3  4  5  6
	cout << endl << "测试成员函数*******************************************" << endl;
	cout << "empty()*************************" << endl;
	cout << "a.empty() = " << a.empty() << endl;//a.empty() = 0
	cout << "size()**************************" << endl;
	cout << "a.size() = " << a.size() << endl;//a.size() = 6
	cout << "top()***************************" << endl;
	cout << "a.top() = " << a.top() << endl;//a.top() = 6
	cout << "pop()***************************" << endl;
	cout << "a.capacity() = " << a.capacity() << endl;//a.capacity() = 10
	cout << "arrayStack a is:" << a;//arrayStack a is:1  2  3  4  5  6
	cout << "a.pop() = " << a.pop() << endl;//a.pop() = 6
	cout << "a.pop() = " << a.pop() << endl;//a.pop() = 5
	cout << "a.pop() = " << a.pop() << endl;//a.pop() = 4
	cout << "a.pop() = " << a.pop() << endl;//a.pop() = 3
	cout << "a.pop() = " << a.pop() << endl;//a.pop() = 2
	cout << "arrayStack a is:" << a;//arrayStack a is:1
	cout << "a.capacity() = " << a.capacity() << endl;//a.capacity() = 5
	cout << "push()**************************" << endl;
	a.push(99);
	cout << "arrayStack a is:" << a;//arrayStack a is:1  99
	cout << "split()*************************" << endl;
	arrayStack<int> b, c;
	a.split(b, c);
	cout << "arrayStack a is:" << a;//arrayStack a is:1  99
	cout << "arrayStack b is:" << b;//arrayStack b is:1
	cout << "arrayStack c is:" << c;//arrayStack c is:99
	cout << "merge()*************************" << endl;
	a.merge(b);
	cout << "arrayStack a is:" << a;//arrayStack a is:1  99  1
	cout << "arrayStack b is:" << b;//arrayStack b is:1
	cout << "*********************************arrayStackTest()函数结束*************************************" << endl;
}
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

main.cpp

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			main()函数，控制运行所有的测试函数
*/
#include 
#include "_15arrayStack.h"

int main()
{
	arrayStackTest();

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

_1myExceptions.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			综合各种异常
*/
#pragma once
#ifndef _MYEXCEPTIONS_H_
#define _MYEXCEPTIONS_H_
#include 
#include

using namespace std;

// illegal parameter value
class illegalParameterValue
{
public:
    illegalParameterValue(string theMessage = "Illegal parameter value")
    {
        message = theMessage;
    }
    void outputMessage() { cout << message << endl; }
private:
    string message;
};

// illegal input data
class illegalInputData
{
public:
    illegalInputData(string theMessage = "Illegal data input")
    {
        message = theMessage;
    }
    void outputMessage() { cout << message << endl; }
private:
    string message;
};

// illegal index
class illegalIndex
{
public:
    illegalIndex(string theMessage = "Illegal index")
    {
        message = theMessage;
    }
    void outputMessage() { cout << message << endl; }
private:
    string message;
};

// matrix index out of bounds
class matrixIndexOutOfBounds
{
public:
    matrixIndexOutOfBounds
    (string theMessage = "Matrix index out of bounds")
    {
        message = theMessage;
    }
    void outputMessage() { cout << message << endl; }
private:
    string message;
};

// matrix size mismatch
class matrixSizeMismatch
{
public:
    matrixSizeMismatch(string theMessage =
        "The size of the two matrics doesn't match")
    {
        message = theMessage;
    }
    void outputMessage() { cout << message << endl; }
private:
    string message;
};

// stack is empty
class stackEmpty
{
public:
    stackEmpty(string theMessage =
        "Invalid operation on empty stack")
    {
        message = theMessage;
    }
    void outputMessage() { cout << message << endl; }
private:
    string message;
};

// queue is empty
class queueEmpty
{
public:
    queueEmpty(string theMessage =
        "Invalid operation on empty queue")
    {
        message = theMessage;
    }
    void outputMessage() { cout << message << endl; }
private:
    string message;
};

// hash table is full
class hashTableFull
{
public:
    hashTableFull(string theMessage =
        "The hash table is full")
    {
        message = theMessage;
    }
    void outputMessage() { cout << message << endl; }
private:
    string message;
};

// edge weight undefined
class undefinedEdgeWeight
{
public:
    undefinedEdgeWeight(string theMessage =
        "No edge weights defined")
    {
        message = theMessage;
    }
    void outputMessage() { cout << message << endl; }
private:
    string message;
};

// method undefined
class undefinedMethod
{
public:
    undefinedMethod(string theMessage =
        "This method is undefined")
    {
        message = theMessage;
    }
    void outputMessage() { cout << message << endl; }
private:
    string message;
};
#endif
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151