第93篇 C++数据结构（三）栈_c++ stack 清空操作函数

栈的详细介绍网上有很多博文，在此不多做说明。

1.栈的简介

栈（stack）又名堆栈，作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。栈具有先进后出的特性。

1.1.入栈

也称为压栈，往栈里面添加新元素。

1.2.出栈

删除栈顶元素。

1.3.实现形式

（1）数组：数组实现的话栈的长度固定。
（2）链表：比较灵活。

2.节点

为了设计比较灵活，就写一个链表形式的栈，在此定义一个节点。

template <typename _dataType>
struct StackNode {
	using _stackNodePtr = StackNode<_dataType>*;

	_dataType m_value;
	_stackNodePtr m_next;

	StackNode() : m_value(_dataType()), m_next(nullptr) {}
	StackNode(_dataType value) : m_value(value), m_next(nullptr) {}
	StackNode(_dataType value, _stackNodePtr next) : m_value(value), m_next(next) {}
};
1
2
3
4
5
6
7
8
9
10
11

3.实现

3.1.变量

3.2.方法

4.测试

4.1.测试代码

#include <iostream>

#include "Stack.h"

void stackTest()
{
	std::cout << "\n构造：" << std::endl;
	Stack<int> s;

	std::cout << "\n数据个数：" << s.size() << std::endl;

	std::cout << "\nempty:" << std::endl;
	if (s.empty()) {
		std::cout << "s is empty!" << std::endl;
	}
	else {
		std::cout << "s isn't empty!" << std::endl;
	}

	std::cout << "\npush（7）" << std::endl;
	s.push(7);
	std::cout << "\n数据个数：" << s.size() << std::endl;
	std::cout << "top = " << s.top() << std::endl;

	std::cout << "\npush:1,2,3,4,5,6" << std::endl;
	int num = 1;
	while (num < 7) {
		s.push(num++);
	}
	std::cout << "\n数据个数：" << s.size() << std::endl;
	std::cout << "top = " << s.top() << std::endl;

	Stack<int> st = s;
	while (!st.empty()) {
		std::cout << st.top() << ", ";
		st.pop();
	}

	std::cout << "\nempty:" << std::endl;
	if (s.empty()) {
		std::cout << "s is empty!" << std::endl;
	}
	else {
		std::cout << "s isn't empty!" << std::endl;
	}

	std::cout << "\npop" << std::endl;
	s.pop();
	std::cout << "\n数据个数：" << s.size() << std::endl;
	std::cout << "top = " << s.top() << std::endl;

	std::cout << "\n清空栈：" << std::endl;
	while (!s.empty()) {
		s.pop();
	}

	std::cout << "\n数据个数：" << s.size() << std::endl;
	std::cout << "\nempty:" << std::endl;
	if (s.empty()) {
		std::cout << "s is empty!" << std::endl;
	}
	else {
		std::cout << "s isn't empty!" << std::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
56
57
58
59
60
61
62
63
64
65
66

4.2.输出结果

构造：

数据个数：0

empty:
s is empty!

push（7）

数据个数：1
top = 7

push:1,2,3,4,5,6

数据个数：7
top = 6
6, 5, 4, 3, 2, 1, 7,
empty:
s isn't empty!

pop

数据个数：6
top = 5

清空栈：

数据个数：0

empty:
s is empty!

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

5.实现代码

#pragma once
#ifndef _STACK_H_
#define _STACK_H_

#include <cassert>

template <typename _dataType>
struct StackNode {
	using _stackNodePtr = StackNode<_dataType>*;

	_dataType m_value;
	_stackNodePtr m_next;

	StackNode() : m_value(_dataType()), m_next(nullptr) {}
	StackNode(_dataType value) : m_value(value), m_next(nullptr) {}
	StackNode(_dataType value, _stackNodePtr next) : m_value(value), m_next(next) {}
};

template <typename _dataType>
class Stack
{
	using _stackNodePtr = StackNode<_dataType>*;
public:
	Stack() : m_top(nullptr), m_len(0) {}

	Stack(const Stack& s)
	{
		if (s.m_top) {
			m_top = new StackNode<_dataType>(s.m_top->m_value);
			_stackNodePtr top = m_top;
			_stackNodePtr stop = s.m_top->m_next;
			while (stop) {
				top->m_next = new StackNode<_dataType>(stop->m_value);
				top = top->m_next;
				stop = stop->m_next;
			}

			m_len = s.m_len;
		}
		else {
			m_top = nullptr;
			m_len = 0;
		}
	}

	~Stack()
	{
		while (this->m_top) {
			this->pop();
		}
	}

	Stack& operator = (const Stack& s)
	{
		while (this->m_top) {
			this->pop();
		}

		if (s.m_top) {
			m_top = new StackNode<_dataType>(s.m_top->m_value);
			_stackNodePtr top = m_top;
			_stackNodePtr stop = s.m_top->m_next;
			while (stop) {
				top->m_next = new StackNode<_dataType>(stop->m_value);
				top = top->m_next;
				stop = stop->m_next;
			}

			m_len = s.m_len;
		}
		else {
			m_top = nullptr;
			m_len = 0;
		}

		return *this;
	}

	void push(_dataType value)
	{
		m_top = new StackNode<_dataType>(value, m_top);
		m_len++;
	}

	void pop()
	{
		assert(m_top);

		_stackNodePtr top = m_top;
		m_top = m_top->m_next;

		delete top;
		top = nullptr;

		m_len--;
	}

	_dataType& top()
	{
		assert(m_top);

		return m_top->m_value;
	}

	bool empty()
	{
		return m_top == nullptr;
	}

	size_t size() const
	{
		return m_len;
	}

private:
	_stackNodePtr m_top;
	size_t m_len;
};

#endif // !_STACK_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
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

6.总结

只在实现，不在解释说明。