Stacks

Overview

继前面单双链表之后,再来学习下Stacks.教材还是参考Data Structure and Algorithms in c++。下面是普通栈的实现和list在栈的应用。最后,实现了书中提到的大数的相加算法。

Code

Stacks
genStack.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

//
// Created by shensir on 17-5-10.
//

#ifndef CPPPROJECTS_GENSTACK_H
#define CPPPROJECTS_GENSTACK_H


#include <vector>

using namespace std;

template <class T, int capacity=30>
class Stack{
private:
vector<T>pool;
public:
Stack(){
pool.reserve(capacity);
}

void clear(){
pool.clear();
}

bool isEmpty() const {
return !pool.back();
}

T& topEl(){
return pool.back();
}

T pop(){
if(pool.size() == 0){
return 0;
}
else{
T el = pool.back();
pool.pop_back();
return el;
}

}


void push(const T& el){
pool.push_back(el);
}

// 打印stack
void printstack(){
printf("Stack: \n");
for(typename std::vector<T>::iterator i = pool.end()-1; i != pool.begin()-1; i--){
std::cout<<*i<<"\n";
}
}

// 获取stack长度
int getsize(){
return pool.size();
}


};



#endif //CPPPROJECTS_GENSTACK_H


main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
#include "genStack.h"
using namespace std;

int main(){
Stack<int>S;
S.push(1);
S.push(2);
S.push(3);
S.printstack();

S.pop();
S.printstack();

return 0;

}


输出:

Stack:
3
2
1
Stack:
2
1

List Stacks
genListStack.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

//
// Created by shensir on 17-5-10.
//

#ifndef CPPPROJECTS_GENLISTSTACK_H
#define CPPPROJECTS_GENLISTSTACK_H

#include <list>

using namespace std;

template <class T>
class LLStack{
private:
list<T>lst;

public:
LLStack(){};

void clear(){
lst.clear();
}

bool isEmpty() const {
return lst.empty();
}

T& topEl(){
return lst.back();
}

T pop(){
T el = lst.back();
lst.pop_back();
return el;
}

void push(const T&el){
lst.push_back(el);
}

void printLLStack(){
list<T>reverse_lst = lst;
reverse_lst.reverse();
for(typename list<T>::iterator i = reverse_lst.begin(); i != reverse_lst.end(); i++){
std::cout<<*i<<endl;
}
}
};

#endif //CPPPROJECTS_GENLISTSTACK_H


main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <iostream>
#include "genListStack.h"
using namespace std;

int main(){
using namespace std;

LLStack<int> lst;

lst.push(2);
lst.push(3);

lst.printLLStack();
return 0;
}

输出:

3
2

Application1: Big numbers’ adding
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

#include <iostream>
#include "genStack.h"
#include "genListStack.h"
#include <string>
#include <cstring>
#include <cmath>

using namespace std;


void pushStringToStack(Stack<int>&num, string s){
for(int i=0; i<s.length(); i++){
num.push(int(s[i])-48);
}
};


void printvector(vector<int>v){
for (int i = 0; i < v.size(); ++i) {
cout<<v[i]<<endl;
}
}


string getNumFromVector(vector<int>v){
string number_str;
for (int i = v.size()-1; i >= 0; i--) {
number_str += std::to_string(v[i]);
}
return number_str;
}

vector<int> bigNumPlus(string m, string n){
// 分别将字符串放入数组
Stack<int> num1, num2;
pushStringToStack(num1, m);
pushStringToStack(num2, n);

int max_len = max(num1.getsize(), num2.getsize());
vector<int> result;

bool next_plus_one = false;

for(int i=0; i<max_len; i++){
int x1 = num1.pop();
int x2 = num2.pop();
cout<<x1<<" "<<x2;



int x12;
if(next_plus_one) x12 = x1 + x2 + 1;
else x12 = x1 + x2;
cout<<" "<<x12<<endl;

// 是否进位
if(x12 >= 10){
next_plus_one = true;
x12 -= 10;
}
else next_plus_one = false; //重置

result.push_back(x12);

}

return result;


}

int main(){

string m("123456789"), n("12345678910");
vector<int> result = bigNumPlus(m, n);

// printvector(result);
string number_str = getNumFromVector(result);
cout<<number_str<<endl;

}


输出:

9 0 9
8 1 9
7 9 16
6 8 15
5 7 13
4 6 11
3 5 9
2 4 6
1 3 4
0 2 2
0 1 1
12469135699

Application2:Reverse the string

这里,我们介绍两种应用stack来反转字符串的方法,第一种借助stack(未用自己写的,用的STL);第二种是通过两个变量来标记字符串的方法。

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

//
// Created by shensir on 17-5-26.
//

#include <iostream>
#include <stack>
#include <cstring>

using namespace std;

// Time-complexity O(n)
// sapce-complexity O(n)
void MyReverseS(char C[]){
// get length
int n = strlen(C);

stack<char>S;
// push
for(int i=0; i<n; i++){
S.push(C[i]);
}

// pop
for(int i=0; i<n; i++){
C[i] = S.top();
S.pop();
}
}

// Time-complexity O(n)
// sapce-complexity O(1)
void MyReverseS_plus(char C[]){
int i = 0;
int j = strlen(C)-1;

for(i, j; i<=j; i++, j--){// 这里终止条件不能为i!=j,在长度为偶数时会出错
char temp = C[i];
C[i] = C[j];
C[j] = temp;
}
}

int main(){

char MyStrting[50];
cout << "Enter a string: ";
cin >> MyStrting;
MyReverseS_plus(MyStrting);
cout<<"Output = "<<MyStrting<<endl;

return 0;
}


运行:

Enter a string: datahonoe
Output = eonohatad

同样地,我们也可以使用stack反转一个linked list.

Application3: check for balanced parentheses

我们也可以用stack写一个检查括号是否平衡的程序:

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

//
// Created by shensir on 17-5-26.
//

#include <iostream>
#include <stack>
#include <cstring>
using namespace std;

// 是不是左括号
bool checkclosing(char c){
return c=='(' or c=='[' or c=='{';
}

// 是不是右括号
bool checkenclosing(char c){
return c==')' or c==']' or c=='}';
}


// 是否匹配
bool Match(char c1, char c2){
if (c1=='(' && c2== ')') return true;
else if (c1=='[' && c2== ']') return true;
else if (c1=='{' && c2== '}') return true;
else return false;
}

// 是否平衡
int CheckBalance(char C[]){
stack<char>S;
int n = strlen(C);
for(int i=0; i<n; i++){
if (checkclosing(C[i])) {
S.push(C[i]);
}
else if (checkenclosing(C[i])){
if(S.empty() || !Match(S.top(), C[i])) return 0;
else S.pop();
}

}

if (S.empty()) return 1;
else return 0;
}


int main(){

// get the string
char Mstring[50];
cout<< "Enter a string: ";
cin >> Mstring;
int result = CheckBalance(Mstring);
printf("%d", result);
return 0;
}

运行:

Enter a string: datahonor
1

Reference

YouTube

本文标题:Stacks

文章作者:不秩稚童

发布时间:2017年05月10日 - 22:40:17

最后更新:2017年05月26日 - 11:30:23

原始链接:http://datahonor.com/2017/05/10/Stacks/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

击蒙御寇