STL栈实现及书本对比

发表于 | 分类于

返回目录

栈是一种只允许在一端进行插入与移除的数据结构。

一、课本分析

书本上的栈，主要分为两种实现

  • 顺序栈
  • 链栈

顺序栈需要事先指定元素，空间固定。
链栈随用随申请，一般不会出现空间问题。

栈实现比较简便，功能明确，

  • top() 获取栈顶元素
  • push(T x) 向栈中压入元素
  • pop() 弹出栈顶元素
  • size() 返回元素个数
  • empty() 判断栈是否为空

具体实现可以参见：顺序栈以及双栈的设计与测试

二、STL栈

文章内容参考：STL系列之二 stack栈

下面，贴出在VS中，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
template<class _Ty, class _Container = deque<_Ty> >
class stack
{	// LIFO queue implemented with a container
public:
	typedef _Container container_type;
	typedef typename _Container::value_type value_type;
	typedef typename _Container::size_type size_type;
	typedef typename _Container::reference reference;
	typedef typename _Container::const_reference const_reference;
	
	stack() : c()
	{	// construct with empty container
	}

	explicit stack(const _Container& _Cont) : c(_Cont)
	{	// construct by copying specified container
	}

	bool empty() const
	{	// test if stack is empty
		return (c.empty());
	}

	size_type size() const
	{	// test length of stack
		return (c.size());
	}

	reference top()
	{	// return last element of mutable stack
		return (c.back());
	}

	const_reference top() const
	{	// return last element of nonmutable stack
		return (c.back());
	}

	void push(const value_type& _Val)
	{	// insert element at end
		c.push_back(_Val);
	}

	void pop()
	{	// erase last element
		c.pop_back();
	}

	const _Container& _Get_container() const
	{	// get reference to container
		return (c);
	}

protected:
	_Container c;	// the underlying container
};

不难发现，栈并没有提供自身的函数，而是封装了其他的数据结构，提供了对外的接口函数。

在c++面向对象实用教程一书中，第275页，讲述了stack和queue本身都不是独立的容器，默认条件下，是用的deque的容器来构造的。

在C++ Primer中第九章详细介绍了容器类型，deque双向队列是一种双向开口的连续线性空间，可以高效的在头尾两端插入和删除元素。

相比之下，STL栈并没有实现判满操作，因为，其使用容器类，不存在空间分配问题。同时，由于其余功能均采用容器，提供接口访问。在头部插入和删除的效率很高。使用时，仅需要包含其头文件即可。