STL Stack

STL Stack

LIFO
包含头文件<stack>

定义：

namespace std {
	template <	typename T,
			typename Container = deque<T> >
	class stack;
}

内部Container默认是用deque实现的。因为deque会在删除元素后释放内存，并且不用在重分配时拷贝元素。
可以用其他提供back(), push_back()和pop_back()的顺序容器，如vector。

The Core Interface

• push() inserts an element into the stack.
• top() returns the next element in the stack.
• pop() removes an element from the stack.
• size()/empty()

Example of Using Stacks

#include <iostream>
#include <stack>
using namespace std;
int main(){

	stack<int> st;
	// push three elements into the stack
	st.push(1);
	st.push(2);
	st.push(3);
	// pop and print two elements from the stack
	cout << st.top() << ' ';
	st.pop();
	cout << st.top() << ' ';
	st.pop();
	// modify top element
	st.top() = 77;
	// push two new elements
	st.push(4);
	st.push(5);
	// pop one element without processing it
	st.pop();
	// pop and print remaining elements
	while (!st.empty())
	{
		cout << st.top() << ' ';
		st.pop();
	}
	cout << endl;
	system("Pause");
}

A User-Defined Stack Class

标准的stack为速度牺牲了方便与安全。接下来的实现有两点不同：

• pop()会返回下一个元素。
• pop()和top()在栈为空的时候会抛出异常。

/*
Stack.h
- safer and more covenient stack class
*/
#pragma once
#include <deque>
#include <exception>
template <typename T>
class Stack
{
protected:
	std::deque<T> c;	// container for the elements
public:
	// exception class for pop() and top() with empty stack
	class ReadEmptyStack : public std::exception
	{
	public:
		virtual const char* what() const throw()
		{
			return "read empty stack";
		}
	};
	// number of elements
	typename std::deque<T>::size_type size() const
	{
		return c.size();
	}
	// is stack empty?
	bool empty() const {return c.empty();}
	// push element into the stack
	void push (const T& elem) {c.push_back(elem);}
	// pop element out of the stack and return its value
	T pop()
	{
		if (c.empty()) {throw ReadEmptyStack();}
		T elem(c.back());
		c.pop_back();
		return elem;
	}
	// return value of next element
	T& top()
	{
		if (c.empty()) {throw ReadEmptyStack();}
		return c.back();
	}
};

[1] The C++ Standard Library 2nd Edition