C++——Stack（堆栈）和Queue（队列）_c++ stack

 

 
 

  

Stack（堆栈）

Class stack<>实现出一个 stack（也称为 LIFO，后进先出）。你可以使用 push() 将任意数量的元素放入 stack（如下图所示），也可以使用 pop() 将元素依其插入的相反次序从容器中移除（此即所谓“后进先出[LIFO]”）。

stack 包含在头文件< stack >中：

#include <stack>
1

在头文件< stack >中，class stack 定义如下：

namespace std{
	template <typename T,
				typename Container = deque<T> >
			class stack;
} 
1
2
3
4
5

• 第一个 template 参数代表元素类型；
• 第二个 template 参数带有默认值，用来定义 stack 内部存放元素的实际容器，默认为 deque。之所以选择 deque 而非 vector，是因为 deque 移除元素时会释放内存，并且不必在重分配时复制全部元素。

定义一个 int 类型的 stack：

stack<int> st;
1

Stack 的实现中只是很单纯地把各项操作转化为内部容器的对应调用（如下图所示）。你可以使用任何 sequence 容器支持 stack，只要它们提供以下成员函数: back()、push_back() 和 pop_back()。例如你可以使用 vector 或 list 来容纳元素；

stack<int, vector<int> > st;
1

 
 

 
 

 
 

核心接口

Stack 的核心接口由三个成员函数提供：push()、 top() 和 pop()。

• push()：将一个元素放入 stack 内。
• top()：返回 stack 内的“下一个”元素。
• pop()：从 stack 中移除元素。

注意， pop() 移除下一个元素，但是并不返回它；top() 返回下一个元素，但是并不移除它。所以，如果你想移除 stack 的下一个元素同时返回它，那么这两个的接口可能有点麻烦，但如果你只是想移除下一个元素而并不想处理它，这样的安排就比较好。注意，如果 stack 内没有元素，调用 top() 和 pop() 会导致不明确的行为。你可以采用成员函数 size() 和 empty() 来检验容器是否为空。
  如果你不喜欢 stack<> 的标准接口，轻易便可写出若干更方便的接口。

 
 

 
 

 
 

stack 运用实例

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

int main(){
	stack<int> st;
	st.push(1);st.push(2);st.push(3);
	
	printf("%d\n", st.top());//1--2--3
	st.pop();
	printf("%d\n", st.top());//1--2
	st.pop();
	
	st.top() = 66;//1-->66
	
	st.push(4);//66--4
	st.push(5);//66--4--5
	
	st.pop();//66--4
	
	while(!st.empty()){
		printf("%d ", st.top());
		st.pop();
	}
	return 0;
}
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

 
 
注意，当使用 nontrivial (译注：意指不凡的、复杂的）元素类型时，你可以考虑在安插“不再被使用的元素”时采用 move()，或是采用 emplace()，由 stack 内部创建元素（二者都始自C++11)：

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

int main(){
	stack<pair<string, string> > s;
	auto p = make_pair("qw", "666");
	s.push(move(p));
	cout << s.top().first << "  " << s.top().second << endl;
	s.emplace("qwjy", "666");
	cout << s.top().first << "  " << s.top().second << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

 
 

 
 

 
 

用户自定义 Stack Class

标准的 stack<> class 将运作速度置于方便性和安全性之上。但我通常并不很重视这些，所以我自己写了一个 stack class，拥有以下优势：

1. pop() 会返回下一元素。
2. 如果 stack 为空，pop() 和 top() 会抛出异常。

此外，我把一般人不常使用的成员函数如比较动作(comparison)略去。我的 stack class定义如下：
编写 hpp 文件，dev C++编写只需要保存是改成 .hpp 文件即可。

#ifndef STACK_HPP
#define STACK_HPP

#include <deque>
#include <exception>

template <typename T>
class Stack{
	protected:
		std:: deque<T> c;
	public:
		class ReadEmptyStack : public std::exception{
			public:
				virtual const char* what() const throw(){
					return "read empty stack";
				}
		};
		
		typename std::deque<T>::size_type size() const{
			return c.size();
		}
		
		bool empty() const{
			return c.empty();
		}
		
		void push(const T& elem){
			c.push_back(elem);
		}
		
		T pop(){
			if(c.empty()){
				throw ReadEmptyStack();
			}
			T elem(c.back());
			c.pop_back();
			return elem;
		}
		
		T& top(){
			if(c.empty()){
				throw ReadEmptyStack();
			}
			return c.back();
		}
};

#endif
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

下面看一下使用的例子，代码如下：

#include <iostream>
#include <exception>
#include "Stack.hpp"
using namespace std;

int main(){
	try{
		Stack<int> st;
		
		st.push(1);//1
		st.push(2);//1--2
		st.push(3);//1--2--3
		
		cout << st.pop() << endl;//1--2
		cout << st.pop() << endl;//1
		
		st.top() = 66;//1-->55
		
		st.push(4);//66--4
		st.push(5);//66--4--5
		
		st.pop();//66--4
		
		cout << st.pop() << endl;//66
		cout << st.pop() << endl;//空 
		cout << st.pop() << endl;//报错 
	}catch(const exception& e){
		cerr << "EXCEPTION: " << e.what() << endl;
	}
	return 0;
}
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

 
 

 
 

 
 

Queue（队列）

Class queue<> 实现出一个 queue（也称为 FIFO [先进先出]）。你可以使用 push() 将任意数量的元素放入 queue 中（如下图所示），也可以使用 pop() 将元素依其插入次序从容器中移除（此即所谓“先进先出 [FIFO]”）。换句话说，queue 是一个典型的数据缓冲构造。

queue 包含在头文件< queue > 中：

#include <queue>
1

在头文件< queue >中，class queue 定义如下：

namespace std{
	template <typename T,
				typename Container = deque<T> >
			class queue;
}
1
2
3
4
5

• 第一个 template 参数代表元素类型。
• 第二个 template 参数带有默认值，定义 queue 内部用来存放元素的实际容器，默认采用 deque。

例如下面的例子定义出了一个内含 string 的 queue：

queue<string> q;
1

实际上 queue 只是很单纯地把各项操作转化为内部容器的对应调用（如下图所示）。你可以使用任何 sequence 容器支持 queue，只要它们支持 front()、 back()、push_back() 和 pop_front() 等操作。

例如你可以使用 list 来容纳元素：

queue<string, list<string> > q;
1

 
 

 
 

 
 

核心接口

Queue 的核心接口主要由成员函数push()、 front()、 back() 和 pop() 构成：

• push()：将一个元素放入 queue 内。
• front()：返回 queue 内的下一个元素（也就是第一个被放入的元素）。
• back()：返回 queue 内的最后一个元素（也就是第一个被插入的元素）。
• pop()：从 queue 中移除一个元素。

注意，pop() 虽然移除下一个元素，但是并不返回它，front() 和 back() 返回下一个元素，但并不移除它。所以，如果你想移除 queue 的下一一个元素，又想处理它，那就得同时调用 front() 和 pop()。这样的接口可能有点麻烦，但如果你只是想移除下一个元素而并不想处理它，这样的安排就比较好。注意，如果 queue 内没有元素，则 front()、back() 和 pop() 的执行会导致不确定的行为。你可以采用成员函数 size() 和 empty() 来检验容器是否为空。

 
 

 
 

 
 

Queue运用实例

#include <iostream>
#include <queue>
using namespace std;

int main(){
	queue<int> q;
	q.push(1);q.push(2);q.push(3);
	
	printf("%d\n", q.front());//1--2--3
	q.pop();
	printf("%d\n", q.front());//2--3
	q.pop();
	
	q.push(4);//3--4
	q.push(5);//3--4--5
	
	q.pop();//4--5
	
	printf("%d\n", q.front());//4--5
	q.pop();
	printf("%d\n", q.front());//5
	q.pop();
	
	printf("size(): %d", q.size());
	return 0;
}
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

 
 

 
 

 
 

自定义Queue Class

标准的 queue<> class 将运作速度置于方便性和安全性之上。但不是所有程序员都喜欢这样。你可以轻松提供你自己完成的一个 queue class，就像先前自己完成一个 stack class 一样（如上 stack class）。

1. pop() 会返回下一元素。
2. 如果 stack 为空，pop()、 front() 和 bush() 会抛出异常。

#ifndef Queue_HPP
#define Queue_HPP

#include <deque>
#include <exception>

template <typename T>
class Queue{
	protected:
		std:: deque<T> c;
	public:
		class ReadEmptyQueue : public std::exception{
			public:
				virtual const char* what() const throw(){
					return "read empty queue";
				}
		};
		
		typename std::deque<T>::size_type size() const{
			return c.size();
		}
		
		bool empty() const{
			return c.empty();
		}
		
		void push(const T& elem){
			c.push_back(elem);
		}
		
		T pop(){
			if(c.empty()){
				throw ReadEmptyQueue();
			}
			T elem(c.front());
			c.pop_front();
			return elem;
		}
		
		T front(){
			if(c.empty()){
				throw ReadEmptyQueue();
			}
			T elem(c.front());
			return elem;
		}
		
		T back(){
			if(c.empty()){
				throw ReadEmptyQueue();
			}
			T elem(c.back());
			return elem;
		}
};

#endif
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

下面看使用 Queue 的代码：

#include <iostream>
#include <exception>
#include "Queue.hpp"
using namespace std;

int main(){
	try{
		Queue<int> q;
		q.push(1);q.push(2);q.push(3);
		
		printf("%d\n", q.front());//1--2--3
		q.pop();
		printf("%d\n", q.front());//2--3
		q.pop();
		
		q.push(4);//3--4
		q.push(5);//3--4--5
		
		q.pop();//4--5
		
		printf("%d\n", q.pop());//4--5
		printf("%d\n", q.pop());//5
		
		printf("size(): %d\n", q.size());
		q.pop();//报错 
//		q.front();//报错
//		q.back();//报错
	}catch (const exception& e){
		cerr << "EXCEPTION: " << e.what() << endl;
	}
	return 0;
}
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