堆栈 Stack

1. 基于数组的堆

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
#ifndef __STACH_H__
#define __STACK_H__
/**
 * 使用数组实现的Stack
 *
 * a = new T[n];
 *
 * a[++p]=t
 *
 * return a[p--]
 *
 * p?-1
 */
template <typename T>
class Stack {
private:
	T* a;
	unsigned size;
	int p;
	const static unsigned DEFAULE_SIZE = 16;

public:
	/* 初始化 */
	Stack();
	/* 初始化 */
	Stack(unsigned n);
	/* 析构释放数组 */
	~Stack();
	/* 入栈 */
	bool push(T t);
	/* 出栈 */
	T pop();
	/* 取栈顶 */
	T top();
	/* 判空 */
	bool empty();
};
template <typename T>
Stack<T>::Stack() {
	size = DEFAULE_SIZE;
	a = new T[DEFAULE_SIZE];
	memset(a, 0, DEFAULE_SIZE * sizeof(T));
	p = -1;
}
template <typename T>
Stack<T>::Stack(unsigned n) {
	size = n;
	a = new T[n];
	memset(a, 0, n * sizeof(T));
	p = 0;
}
template <typename T>
Stack<T>::~Stack() {
	delete[] a;
	a = nullptr;
	p = size = -1;
}
template <typename T>
bool Stack<T>::push(T t) {
	if (p < size - 1) {
		a[++p] = t;
		return true;
	}
	return false;
}
template <typename T>
T Stack<T>::pop() {
	if (p == -1)
		return nullptr;
	return a[p--];
}
template <typename T>
T Stack<T>::top() {
	if (p != -1)
		return a[p];
	return nullptr;
}
template <typename T>
bool Stack<T>::empty() {
	return p == -1;
}
#endif

2. 基于链表的堆栈

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
#ifndef __LINKEDSTACK_H__
#define __LINKEDSTACK_H__
template <typename T>
class LSNode {
public:
	T val;
	LSNode<T>* next;
	LSNode(T t) : val(t) {}
};

template <typename T>
class LinkedStack {
private:
	LSNode<T>* __top;

public:
	/**
	 * 初始化
	 */
	LinkedStack();
	/**
	 * 析构
	 */
	~LinkedStack();
	/**
	 * 入栈
	 */
	bool push(T t);
	/**
	 * 弹出
	 */
	T pop();
	/**
	 * 取栈顶元素
	 */
	T top();
	/**
	 * 判空
	 */
	bool empty();
};
template <typename T>
LinkedStack<T>::LinkedStack() : __top(nullptr) {}
template <typename T>
LinkedStack<T>::~LinkedStack() {
	while (__top != nullptr) {
		LSNode<T>* node = __top;
		__top = __top->next;
		delete node;
	}
}
template <typename T>
bool LinkedStack<T>::push(T t) {
	LSNode<T>* node = new LSNode<T>(t);
	node->next = __top;
	__top = node;
	return true;
}
template <typename T>
T LinkedStack<T>::pop() {
	LSNode<T>* node = __top;
	T val = __top->val;
	__top = __top->next;
	delete node;
	return val;
}
template <typename T>
T LinkedStack<T>::top() {
	return __top->val;
}
template <typename T>
bool LinkedStack<T>::empty() {
	return __top == nullptr;
}
#endif

3. 堆栈的使用

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
#include <bits/stdc++.h>
#include "LinkedStack.h"
using namespace std;
/**
 * 反转
 */
template <class T>
void reverse(const T* a, int n) {
	LinkedStack<T>* s = new LinkedStack<T>();
	for (int i = 0; i < n; ++i) {
		s->push(a[i]);
	}
	while (!s->empty()) {
		std::cout << s->pop() << ' ';
	}
	cout << endl;
	delete s;
}
/**
 * 进制转换
 * conversion of number systems
 *
 * 10 -> 2
 */
void dec2bin(int n) {
	LinkedStack<int> s;
	while (n != 0) {
		s.push(n % 2);
		n /= 2;
	}
	while (!s.empty()) {
		cout << s.pop() << ' ';
	}
	cout << endl;
}
void dec2bin(double n, int e = 10) {
	int z = (int)n;
	double d = n - z;
	LinkedStack<int> s;
	while (z != 0) {
		s.push(z % 2);
		z /= 2;
	}
	while (!s.empty()) {
		cout << s.pop();
	}
	cout << '.';
	for (int i = 0; i < e; ++i) {
		if (d == 0)
			break;
		d *= 2;
		if (d >= 1) {
			cout << 1;
			--d;
		}
		else {
			cout << 0;
		}
	}
}
/**
 * 进制转换
 * conversion of number systems
 *
 * 10 -> 8
 */
void dec2oct(int n) {
	LinkedStack<int> s;
	while (n != 0) {
		s.push(n % 8);
		n /= 8;
	}
	while (!s.empty()) {
		cout << s.pop() << ' ';
	}
	cout << endl;
}

/**
 * 进制转换
 * conversion of number systems
 *
 * 10 -> 16
 */
void dec2hex(int n) {
	LinkedStack<char> s;
	while (n != 0) {
		if (n % 16 > 9) {
			s.push('A' + (n % 16) - 10);
		}
		else
			s.push('0' + n % 16);
		n /= 16;
	}
	while (!s.empty()) {
		cout << s.pop() << ' ';
	}
	cout << endl;
}
/**
 * 括号匹配
 */
bool bracketMatching(const char* a, int n) {
	LinkedStack<char> s;
	for (int i = 0; i < n; ++i) {
		if (a[i] == '(')
			s.push(a[i]);
		if (a[i] == ')') {
			if (!s.empty())
				s.pop();
			else
				return false;
		}
		if (a[i] == '[')
			s.push(a[i]);
		if (a[i] == ']') {
			if (!s.empty())
				s.pop();
			else
				return false;
		}
		if (a[i] == '{')
			s.push(a[i]);
		if (a[i] == '}') {
			if (!s.empty())
				s.pop();
			else
				return false;
		}
	}
	if (!s.empty())return false;
	return true;
}

int main(int argc, char const* argv[]) {
	char a[] = { 'A', 'B', 'C', 'D', 'E', 'F' };
	cout << "----------\n反转数组 {'A','B','C','D','E','F'} \n";
	reverse(a, sizeof(a) / sizeof(a[0]));
	cout << "----------\n17D 转二进制:\n";
	dec2bin(17);
	cout << "----------\n17D 转八进制:\n";
	dec2oct(17);
	cout << "----------\n17D 转十六进制:\n";
	dec2hex(17);
	cout << "----------\n括号匹配 '(a)af((s()fa()())' :\n";
	char s[] = "(a)af((s()fa()())";
	cout << (bracketMatching(s, sizeof(s) / sizeof(s[0])) ? "True\n" : "False\n");
	cout << "----------\n括号匹配 '(a(()d)(s))()' :\n";
	char f[] = "(a(()d)(s))()";
	cout << (bracketMatching(f, sizeof(f) / sizeof(f[0])) ? "True\n" : "False\n");
	cout << "----------\n17.256D 转二进制:\n";
	dec2bin(17.256);
	return 0;
}