数据结构-栈

Computer

      本次链栈用到的Node.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
template<typename T>
class Node {
public:
	Node() {}
	Node(T data, Node<T> *nextptr) :data(data), next(nextptr){
	}
	~Node() {}
	T getData();
	void setData(T newData);
	Node<T> *getNext();
	void setNext(Node<T> *ptr);
private:
	T data;
	Node<T> *next;
};
template<typename T>
T Node<T>::getData() {
	return data;
}
template<typename T>
void Node<T>::setData(T newData) {
	data = newData;
}
template<typename T>
Node<T> *Node<T>::getNext() {
	return next;
}
template<typename T>
void Node<T>::setNext(Node<T> *ptr) {
	next = ptr;
}

      顺序栈SeqStack.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
const int StackSize = 10;
template<typename T>
class SeqStack {
public:
	SeqStack() { top = -1; }
	~SeqStack() {}
	void Push(T x);
	T Pop();
	T GetTop();
	bool Empty();
	bool Full();
private:
	T data[StackSize];
	int top;
};
template<typename T>
void SeqStack<T>::Push(T x) {
	if (Full()) {
		throw "栈为满！";
	}
	else {
		data[++top] = x;
	}
}
template<typename T>
T SeqStack<T>::Pop() {
	if (Empty()) {
		throw "栈为空！";
	}
	else {
		return data[top--];
	}
}
template<typename T>
T SeqStack<T>::GetTop() {
	if (Empty()) {
		throw "栈为空！";
	}
	else {
		return data[top];
	}
}
template<typename T>
bool SeqStack<T>::Empty() {
	if (top == -1) {
		return true;
	}
	else {
		return false;
	}
}
template<typename T>
bool SeqStack<T>::Full() {
	if (top == StackSize - 1) {
		return true;
	}
	else {
		return false;
	}
}

      共享栈BothStack.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
const int StackSize = 10;
template <typename T>
class BothStack {
public:
	BothStack() { top1 = -1; top2 = StackSize; }
	~BothStack() {}
	void Push(int i, T x);
	T Pop(int i);
	T GetTop(int i);
	bool Empty();
	bool Full();
private:
	T data[StackSize];
	int top1, top2;
};
template<typename T>
void BothStack<T>::Push(int i, T x) {
	if (top1 == top2 - 1) {
		throw "栈为满！";
	}
	else if (i == 1) {
		data[++top1] = x;
	}
	else if (i == 2) {
		data[--top2] = x;
	}
	else {
		throw"输入的值有误，没有对应的栈！";
	}
}
template<typename T>
T BothStack<T>::Pop(int i) {
	if (i == 1) {
		if (top1 == -1) {
			throw"栈1为空！";
		}
		else {
			return data[top1--];
		}
	}
	else if (i == 2) {
		if (top2 == StackSize) {
			throw"栈2为空！";
		}
		else {
			return data[top2++];
		}
	}
	else {
		throw"输入的值有误，没有对应的栈！";
	}
}
template<typename T>
T BothStack<T>::GetTop(int i) {
	if (i == 1) {
		if (top1 == -1) {
			throw"栈1为空！";
		}
		else {
			return data[top1];
		}
	}
	else if (i == 2) {
		if (top2 == StackSize) {
			throw"栈2为空！";
		}
		else {
			return data[top2];
		}
	}
	else {
		throw"输入的值有误，没有对应的栈！";
	}
}
template<typename T>
bool BothStack<T>::Empty() {
	if (top1 == -1 && top2 == StackSize) {
		return true;
	}
	else {
		return false;
	}
}
template<typename T>
bool BothStack<T>::Full() {
	if (top1 == top2 - 1) {
		return true;
	}
	else {
		return false;
	}
}

      链栈LinkStack.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
#include<iostream>
using namespace std;
#include"Node.cpp"
template<typename T>
class LinkStack {
public:
	LinkStack();
	~LinkStack();
	void Push(T x);
	T Pop();
	T GetTop();
	bool Empty();
private:
	Node<T> *top;
};
template<typename T>
LinkStack<T>::LinkStack() {
	top = NULL;
}
template<typename T>
LinkStack<T>::~LinkStack() {
	Node<T> *temp;
	while (top != NULL) {
		temp = top;
		top = top->getNext();
		delete temp;
	}
}
template<typename T>
void LinkStack<T>::Push(T x) {
	Node<T> *temp = new Node<T>;
	temp->setData(x);
	temp->setNext(top);
	top = temp;
}
template<typename T>
T LinkStack<T>::Pop() {
	if (Empty()) {
		throw"栈为空！";
	}
	else {
		T x = top->getData();
		Node<T> *temp = top;
		top = top->getNext();
		delete temp;
		return x;
	}
}
template<typename T>
T LinkStack<T>::GetTop() {
	if (Empty()) {
		throw"栈为空！";
	}
	else {
		return top->getData();
	}
}
template<typename T>
bool LinkStack<T>::Empty() {
	if (top == NULL) {
		return true;
	}
	else {
		return false;
	}
}

      main.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
/*
	顺序栈测试文件
*/
//#include<iosteam>
//using namespace std;
//#include"SeqStack.cpp"
//int main() {
//	SeqStack<int> stack;
//	int array[] = { 1,2,3,4,5,6,7,8,9,10,11,12};
//	try {
//		for (int i = 0; i < 12; i++) {
//			stack.Push(array[i]);
//		}
//	}
//	catch(char *s){
//		cout << s << endl;
//		while (!stack.Empty()) {
//			cout << stack.Pop() << endl;
//		}
//	}
//	system("pause");
//	return 0;
//}
/*
	共享栈测试文件
*/
//#include<iosteam>
//using namespace std;
//#include"BothStack.cpp"
//int main() {
//	BothStack<int> bothstack;
//	int array[] = { 1,2,3,4,5,6,7,8,9,10,11,12,13};
//	try {
//		for (int i = 0; i < 13; i++) {
//			bothstack.Push(1,array[i]);
//			bothstack.Push(2, array[12 - i]);
//		}
//	}
//	catch (char *s) {
//		cout << s << endl;
//		while (!bothstack.Empty()) {
//			cout << bothstack.Pop(1) << " " << bothstack.Pop(2) << endl;
//		}
//	}
//	system("pause");
//	return 0;
//}
/*
	链栈测试文件
*/
#include"LinkStack.cpp"
int main() {
	LinkStack<int> linkstack;
	try {
		linkstack.Push(1);
		linkstack.Push(2);
		cout << linkstack.GetTop() << endl;
		cout << linkstack.Pop() << endl;
		cout << linkstack.Pop() << endl;
		cout << linkstack.Pop() << endl;
	}
	catch(char *s){
		cout << s << endl;
	}
	if (linkstack.Empty()) {
		cout << "栈为空！" << endl;
	}
	system("pause");
	return 0;
}

      在这次的作业中还用的一种叫做指针栈的东西，指针栈是我起的名字，因为是一种通过指针实现的栈，即在内存中开辟一块连续的空间做栈的操作，与数组实现的会稍微有一些不同。
      分析：其实本质上来说就是在一段连续的内存空间中实现一个栈，之前实现栈数据结构的时候使用的存储结构是数组，而这次使用的是指针。与数组存储不同的时候，这个时候的数指针不可以设置为-1，因为会产生指针指向越界，也不可以将指针设置超过最大值，也是会产生指针指向越界。
      因此在这里我使用了两个指针，一个是bottom，另外一个是top。一个数据存放栈的最大值MaxLength，另外用两个标志FlagBottom和FlagTop，专门用于处理判定栈空和栈满时对应的位置是否存放有数据值。如果top==bottom并且FlagBottom为false，那么栈底就是真正的空，如果此时为True，证明栈底还是有数据的。如果top-bottom==MaxLength-1并且FlagTop为True，证明栈满了，如果为false，证明这个位置没有存放数据，可以继续放数据。需要注意的是，指针指向的是一个地址的开端，所以指向栈顶的时候要减去1的地址值，否则就会出现指针越界。通过这样指示实现不浪费空间，按照分配的内存大小来存放所需的数据量，代码实现如下。
      PointerStack.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
template<typename T>
class PointerStack {
public:
	PointerStack() {};
	PointerStack(int n);
	~PointerStack();
	void push(T data);
	T pop();
	T get();
	bool Full();
	bool Empty();
private:
	T *bottom,*top;
	//记录长度
	int MaxLength;
	//标记栈底和栈顶数据空间是否有数据
	bool FlagBottom;
	bool FlagTop;
};
template<typename T>
PointerStack<T>::PointerStack(int n) {
	bottom = new T[n];
	top = bottom;
	FlagBottom = FlagTop = false;
	MaxLength = n;
}
template<typename T>
PointerStack<T>::~PointerStack() {
	delete[] bottom;
}
template<typename T>
void PointerStack<T>::push(T data) {
	if (Full()) {throw "栈满！";}
	else if (top == bottom) {
		*(top++) = data;
		FlagBottom = true;
	}
	//进入最后一个空白空间
	else if(top - bottom == MaxLength - 1){
		*top = data; 
		FlagTop = true;
	}
	else {*(top++) = data;}
}
template<typename T>
T PointerStack<T>::pop() {
	if (Empty()) {throw "栈空！";}
	else if (top == bottom) {
		T data = *top;
		FlagBottom = false;
		return data;
	}
	//进入最后一个空白空间
	else if (top - bottom == MaxLength - 1) {
		T data = *(top--);
		FlagTop = false;
		return data;
	}
	else {
		T data = *(top--);
		return data;
	}
}
template<typename T>
T PointerStack<T>::get() {
	if (Empty()) {throw "栈空！";}
	else {return *top;}
}
template<typename T>
bool PointerStack<T>::Empty() {
	if ((top == bottom) && !FlagBottom) {return true;}
	else {return false;}
}
template<typename T>
bool PointerStack<T>::Full() {
	if ((top - bottom == MaxLength - 1)&& FlagTop) {return true;}
	else {return false;}
}

文章目录
|