35数据结构-栈的概念与实现（下）

发表于

一.静态栈的缺陷

当存储的元素为类类型的时候，静态栈会的对象在创建的时候会多次调用元素类型的构造函数，影响效率，当使用原生数组作为存储空间，在创建创建栈的时候会调用泛指类型T的构造函数，当函数退出的时候又调用析构函数

1.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
c复制代码#include <iostream>
#include "staticStack.h"

using namespace std;
class Test
{
public:
	Test()
	{
		cout << "Test()" << endl;
	}

	~Test()
	{
		cout << "~Test()" << endl;
	}
};

int main()
{
	staicStack<Test, 5> stack;

	cout << stack.size() << endl;
}

结果为：
在这里插入图片描述
从结果来看，此时栈中没有任何元素，但是却调用了5次构造函数和析构函数

二.链式栈的实现

实际上就是单链表，定义一个top指针，始终指向链表的首元素，当入栈的时候将新结点的next指针指向top指针，并移动top指针，出栈的直接摧毁首结点即可

2.1 设计要点

  1. 抽象父类Stack的直接子类
  2. 在内部组合使用LinkList类，即链表类，实现栈的链式存储
  3. 只在单链表的头部进行操作
    在这里插入图片描述

2.2 入栈

单链表的头插法

1
2
3
4
5
c复制代码	void push(const T& e)
	{
		//直接使用头插法插入链表元素
		m_list.insert(0, e);
	}

2.3 出栈

移除下标为0的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
c复制代码	void pop()
	{
		//出栈直接弹出下标为0的结点
		if (m_list.length() > 0)
		{
			m_list.remove(0);

		}
		else
		{
			cout << "no node to pop" << endl;
		}

	}

2.4 获取栈顶元素

1
2
3
4
5
6
7
8
9
10
11
12
c复制代码	T top()const
	{
		if (m_list.length() > 0)
		{
			m_list.get(0);

		}
		else
		{
			cout << "no node to pop" << endl;
		}
	}

2.5 清空栈

1
2
3
4
c复制代码	void clear（）
	{
		m_list.clear();
	}

2.6 栈成员个数

1
2
3
4
c复制代码	int size()
	{
		return m_list.length();
	}

三.完整代码

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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
c复制代码#ifndef  __LINK_LIST_
#define  __LINK_LIST_

#include <iostream>
using namespace std;

template<class T>
class LinkList
{
public:
	struct Node
	{
		T	  value;
		Node* next;
	};

	mutable struct
	{
		char reverse[sizeof(T)];
		Node* next;
	} m_header;

	int m_length;
	int m_step;
	Node* m_current;

	virtual Node* create()
	{
		return new Node();
	}


	void destroy(Node* pn)
	{
		delete pn;
	}


public:
	
	LinkList()
	{
		m_header.next = NULL;
		m_length = 0;
		m_step = 0;
		m_current = NULL;
	}

	Node* position(int i)const
	{
		Node* pre = reinterpret_cast<Node*>(&m_header);
		for (int pos = 0; pos < i; pos++)
		{
			pre = pre->next;
		}

		return pre;
	}


	
	int find(const T& e)const
	{
		Node* pre = reinterpret_cast<Node*>(&m_header);
		int i = 0;

		while (e != pre->next->value)
		{
			pre = pre->next;
			i++;
		}

		return i;
	}


	bool end()
	{
		return m_current == NULL;
	}


	
	bool move(int i, int step = 1)
	{
		bool ret = (i >= 0) && (i <= m_length);
		if (ret)
		{
			m_current = position(i)->next;
			m_step = step;
		}

		return ret;
	}



	T current()
	{

		if (!end())
		{
			return m_current->value;
		}
		else
		{
			cout << "current end()" << endl;
			return -1;//不知道写啥值
		}
	}

	
	bool next()
	{
		int i = 0;
		while (!end() && i < m_step)
		{
			m_current = m_current->next;
			i++;
		}

		return i == m_step;
	}


	
	bool insert(int i, const T& e)
	{
		bool ret = (i >= 0) && (i <= m_length);
		if (ret)
		{
			Node* node = create();

			if (node != NULL)
			{
				Node* pre = reinterpret_cast<Node*>(&m_header);

				pre = position(i);

				node->value = e;
				node->next = pre->next;
				pre->next = node;
			}
			else
			{
				cout << "no memery to malloc" << endl;
			}
		}

		m_length++;
		cout << "m_l=" << m_length << endl;
		return ret;
	}


	
	bool remove(int i)
	{
		bool ret = (i >= 0) && (i <= m_length);

		if (ret)
		{
			Node* pre = reinterpret_cast<Node*>(&m_header);

			pre = position(i);

			Node* toDel = pre->next;
			pre->next = toDel->next;
			delete toDel;
			m_length--;
		}

		return ret;
	}

	
	bool set(int i, T& e)
	{
		bool ret = (i >= 0) && (i <= m_length);

		if (ret)
		{
			Node* pre = reinterpret_cast<Node*>(&m_header);

			pre = position(i);

			pre->next->value = e;
		}

		return ret;
	}


	T get(int i) const
	{
		bool ret = (i >= 0) && (i <= m_length);
		T e;

		if (ret)
		{
			Node* pre = reinterpret_cast<Node*>(&m_header);

			pre = position(i);

			e = pre->next->value;
		}

		return e;
	}



	int length() const
	{
		return m_length;
	}

	
	void clear()
	{

		while (m_header.next != NULL)
		{
			Node* toDel = m_header.next;
			m_header.next = toDel->next;
			destroy(toDel);
		}

		m_length = 0;
	}

	
	~LinkList()
	{
		clear();
	}

};



#endif

3.2 Stack.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
c复制代码#ifndef STACK_H
#define STACK_H


template<class T>
class Stack
{
public:
	virtual void push(const T& e) = 0;//入栈
	virtual void pop()			  = 0;//出栈
	virtual T    top() const	  = 0;//返回栈顶元素
	virtual void clear()		  = 0;//清空栈
	virtual int  size()			  = 0;//返回栈的大小
};

#endif

3.3 linkStack.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
c复制代码#pragma once
#include "LinkList.h"
#include "Stack.h"

template<class T>
class linkStack :public Stack<T>
{
protected:
	LinkList<T> m_list;
public:
	void push(const T& e)
	{
		//直接使用头插法插入链表元素
		m_list.insert(0, e);
	}

	void pop()
	{
		//出栈直接弹出下标为0的结点
		if (m_list.length() > 0)
		{
			m_list.remove(0);

		}
		else
		{
			cout << "no node to pop" << endl;
		}

	}

	T top()const
	{
		if (m_list.length() > 0)
		{
			return m_list.get(0);
		}
		else
		{
			cout << "no node to pop" << endl;
		}
	}


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

	int size()
	{
		return m_list.length();
	}
};

3.4 测试程序

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
c复制代码#include <iostream>

#include "linkStack.h"

using namespace std;


class Test
{
public:
	Test()
	{
		cout << "Test()" << endl;
	}

	~Test()
	{
		cout << "~Test()" << endl;
	}
};

int main()
{
	linkStack<Test> stack;

	cout << stack.size() << endl;
}

3.5 结果

在这里插入图片描述
从结果看到没有再调用构造函数

四：栈实践-符号检测

编译器是如何实现符号检测的呢，下面的实现思路

4.1 实现思路

  • 从第一个字符开始扫描
  • 当遇到普通字符则不管，遇到左符号则压栈，遇到右符号则弹出栈顶符号，并与右符号进行匹配
  • 成功：所有的字符都扫描，且栈为空
  • 失败：匹配失败且所有字符都扫描成功当栈为空

4.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
76
77
78
79
80
81
82
83
84
85
86
87
c复制代码#include <iostream>

#include "linkStack.h"

using namespace std;


bool is_left(char c)
{
	return  (c == '(') || (c == '{') || (c == '[') || (c == '<');
}

bool is_rigth(char c)
{
	return  (c == ')') || (c == '}') || (c == ']') || (c == '>');
}

bool is_quot(char c)
{
	return  (c == '\'') || (c == '\"');
}

bool is_match(char l, char r)
{
	return ((l == '(') && (r == ')')) ||
		   ((l == '{') && (r == '}')) ||
		   ((l == '[') && (r == ']')) ||
		   ((l == '<') && (r == '>')) ||
		   ((l == '\'') && (r == '\'')) ||
		   ((l == '\"') && (r == '\"'));
}


bool scan(const char* code)
{
	linkStack<char> stack;
	bool ret = true;
	int i = 0;

	code = (code == NULL) ? "" : code;

	while (code[i] != '\0')
	{
		//左符号则入栈
		if (is_left(code[i]))
		{
			stack.push(code[i]);
		}
		else if (is_rigth(code[i]))
		{
			//遇见右符号，则弹出栈顶符号与其进行匹配
			if ((stack.size() > 0 && is_match(stack.top(), code[i])))
			{
				stack.pop();
			}
			else
			{
				ret = false;
			}
		}
		else if (is_quot(code[i]))
		{
			//如果栈是空,或者当前的引号是左字符（也就是和栈顶不匹配），则入栈
			if ((stack.size() == 0) || (!is_match(stack.top(),code[i])))
			{
				
				stack.push(code[i]);
			}
			else if(is_match(stack.top(), code[i]))
			{
				//匹配上了
				stack.pop();
			}
		}
		i++;
	}

	return ret && (stack.size() == 0);
}


int main()
{

	cout << scan("<{a}{b(\'x\')c}d>") << endl;
	return 0;
}

结果：
在这里插入图片描述

五.小结

  • 栈后进先出的特性适合检测成对出现的符号
  • 栈适合就近匹配的场合

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%