A few stack and queue implementations for revision.

stacks-queues.cpp

template<typename T>
class ArrayStack
{
public:
	
	using size_t = std::size_t;
	
	static const size_t minimum_capacity;
	
	
	ArrayStack(size_t capacity = minimum_capacity)
	: _size(0)
	, _capacity(capacity)
	, _data(new T[capacity])
	{ }
	
	ArrayStack(std::initializer_list<T> list)
	: _size(0)
	, _capacity(std::max(list.size(), minimum_capacity))
	, _data(new T[_capacity])
	{
		for (const auto& item : list) push(item);
	}
	
	ArrayStack(const ArrayStack& other)
	: _size(other._size)
	, _capacity(other._capacity)
	, _data(new T[other._capacity])
	{
		std::copy(other._data, other._data + _size, _data);
	}
	
	ArrayStack(ArrayStack&& other)
	: ArrayStack()
	{
		swap(other);
	}
	
	ArrayStack& operator=(ArrayStack other)
	{
		swap(other);
		
		return *this;
	}
	
	void swap(ArrayStack& other) noexcept
	{
		// Enable Argument-Dependent-Lookup
		using std::swap;
		
		swap(_data, other._data);
		
		swap(_size, other._size);
		
		swap(_capacity, other._capacity);
	}
	
	friend void swap(ArrayStack& first, ArrayStack& second) noexcept
	{
		first.swap(second);
	}
	
	~ArrayStack()
	{
		delete [] _data;
	}
	
	
	void push(const T& item)
	{
		_data[_size] = item;
		
		if (++_size == _capacity) _resize();
	}
	
	const T& top() const
	{
		if (_size == 0)
		{
			throw std::out_of_range("No element at top of stack!");
		}
		
		return _data[_size - 1];
	}
	
	T pop()
	{
		if (_size == 0)
		{
			throw std::out_of_range("No element at top of stack!");
		}
		
		auto item = _data[--_size];
		
		if (_size == _capacity/4) _resize();
		
		return item;
	}
	
	void clear()
	{
		delete [] _data;
		
		_size = 0;
		
		_capacity = minimum_capacity;
		
		_data = new T[_capacity];
	}
	
	size_t size() const
	{
		return _size;
	}
	
	bool is_empty() const
	{
		return _size == 0;
	}
	
private:
	
	void _resize()
	{
		auto old_capacity = _capacity;
		
		_capacity = std::max(_size * 2, minimum_capacity);
		
		auto old = _data;
		
		_data = new T[_capacity];
		
		std::copy(old, old + old_capacity, _data);
		
		delete [] old;
	}
	
	
	size_t _size;
	
	size_t _capacity;
	
	T* _data;
};

template<typename T>
const size_t ArrayStack<T>::minimum_capacity = 8;

template<typename T>
class ListStack
{
public:
	
	using size_t = std::size_t;
	
	ListStack()
	: _first(nullptr)
	, _size(0)
	{ }
	
	ListStack(std::initializer_list<T> list)
	: _first(nullptr)
	, _size(0)
	{
		for (const auto& item : list) push(item);
	}
	
	ListStack(const ListStack& other)
	: _first(nullptr)
	, _size(other._size)
	{
		Node* previous = nullptr;
		
		for (auto node = other._first; node; node = node->next)
		{
			auto new_node = new Node(node->item);
			
			if (previous) previous->next = new_node;
			
			else _first = node;
			
			previous = new_node;
		}
	}
	
	ListStack(ListStack&& other) noexcept
	: ListStack()
	{
		swap(other);
	}
	
	ListStack& operator=(ListStack other)
	{
		swap(other);
		
		return *this;
	}
	
	void swap(ListStack& other) noexcept
	{
		// Enable Argument-Dependent-Lookup
		using std::swap;
		
		swap(_first, other._first);
	}
	
	friend void swap(ListStack& first, ListStack& second) noexcept
	{
		first.swap(second);
	}
	
	~ListStack()
	{
		_clear();
	}
	
	
	void push(const T& item)
	{
		auto node = new Node(item, _first);
		
		_first = node;
		
		++_size;
	}
	
	const T& top() const
	{
		if (_size == 0)
		{
			throw std::runtime_error("Cannot pop from empty stack!");
		}
		
		return _first->item;
	}
	
	T pop()
	{
		if (_size == 0)
		{
			throw std::runtime_error("Cannot pop from empty stack!");
		}
		
		auto node = _first;
		
		_first = _first->next;
		
		auto item = node->item;
		
		delete node;
		
		--_size;
		
		return item;
	}
	
	void clear()
	{
		_clear();
		
		_size = 0;
	}
	
	size_t size() const
	{
		return _size;
	}
	
	bool is_empty() const
	{
		return _size == 0;
	}
	
private:
	
	struct Node
	{
		Node(const T& item_ = T(),
			 Node* next_ = nullptr)
		: item(item_)
		, next(next_)
		{ }
		
		T item;
		
		Node* next;
	};
	
	void _clear()
	{
		while (_first)
		{
			auto next = _first->next;
			
			delete _first;
			
			_first = next;
		}
	}
	
	Node* _first;
	
	size_t _size;
};

template<typename T>
class ListQueue
{
public:
	
	using size_t = std::size_t;
	
	ListQueue()
	: _size(0)
	, _front(nullptr)
	, _back(nullptr)
	{ }
	
	ListQueue(std::initializer_list<T> list)
	: _size(0)
	, _front(nullptr)
	, _back(nullptr)
	{
		for (const auto& item : list) enqueue(item);
	}
	
	ListQueue(const ListQueue& other)
	: _size(other._size)
	{
		for (auto node = other._front; node; node = node->next)
		{
			auto new_node = new Node(node->item);
			
			if (! _front) _front = new_node;
			
			else _back->next = new_node;
			
			_back = new_node;
		}
	}
	
	ListQueue(ListQueue&& other) noexcept
	: ListQueue()
	{
		swap(other);
	}
	
	ListQueue& operator=(ListQueue other)
	{
		swap(other);
		
		return *this;
	}
	
	void swap(ListQueue& other) noexcept
	{
		// Enable Argument-Dependent-Lookup (ADL)
		using std::swap;
		
		swap(_front, other._front);
		
		swap(_back, other._back);
		
		swap(_size, other._size);
	}
	
	friend void swap(ListQueue& first, ListQueue& second) noexcept
	{
		first.swap(second);
	}
	
	~ListQueue()
	{
		_clear();
	}
	
	
	void enqueue(const T& item)
	{
		auto node = new Node(item);
		
		if (! _front) _front = node;
		
		else _back->next = node;
		
		_back = node;
		
		++_size;
	}
	
	
	const T& front() const
	{
		if (_size == 0)
		{
			throw std::runtime_error("No such item!");
		}
		
		return _front->item;
	}
	
	const T& back() const
	{
		if (_size == 0)
		{
			throw std::runtime_error("No such item!");
		}
		
		return _back->item;
	}
	
	
	T dequeue()
	{
		if (_size == 0)
		{
			throw std::runtime_error("Cannot dequeue from empty queue!");
		}
		
		auto node = _front;
		
		_front = _front->next;
		
		auto item = node->item;
		
		delete node;
		
		--_size;
		
		return item;
	}
	
	
	void clear()
	{
		_clear();
		
		_size = 0;
	}
	
	
	size_t size() const
	{
		return _size;
	}
	
	bool is_empty() const
	{
		return _size == 0;
	}
	
private:
	
	struct Node
	{
		Node(const T& item_ = T(),
			 Node* next_ = nullptr)
		: item(item_)
		, next(next_)
		{ }
		
		T item;
		
		Node* next;
	};
	
	void _clear()
	{
		while (_front)
		{
			auto next = _front->next;
			
			delete _front;
			
			_front = next;
		}
	}
	
	Node* _front;
	Node* _back;
	
	size_t _size;
};

template<typename T>
class ArrayQueue
{
public:
	
	using size_t = std::size_t;
	
	static const size_t minimum_capacity;
	
	ArrayQueue(size_t capacity = minimum_capacity)
	: _size(0)
	, _capacity(capacity)
	, _front(0)
	, _back(0)
	, _data(new T[_capacity])
	{ }
	
	ArrayQueue(const std::initializer_list<T>& list)
	: _size(0)
	, _capacity(std::max(list.size(), minimum_capacity))
	, _front(0)
	, _back(0)
	, _data(new T[_capacity])
	{
		for (const auto& item : list) enqueue(item);
	}
	
	ArrayQueue(const ArrayQueue& other)
	: _size(other._size)
	, _capacity(other._capacity)
	, _front(other._front)
	, _back(other._back)
	, _data(new T[other._capacity])
	{
		for (auto i = _front; i < _size; ++_incr(_front))
		{
			_data[i] = other._data[i];
		}
	}
	
	ArrayQueue(ArrayQueue&& other) noexcept
	: ArrayQueue()
	{
		swap(other);
	}
	
	void swap(ArrayQueue& other) noexcept
	{
		// Enable Argument-Dependent-Lookup (ADL)
		using std::swap;
		
		swap(_data, other._data);
		
		swap(_size, other._size);
		
		swap(_capacity, other._capacity);
		
		swap(_front, other._front);
		
		swap(_back, other._back);
	}
	
	ArrayQueue& operator=(ArrayQueue other)
	{
		swap(other);
		
		return *this;
	}
	
	friend void swap(ArrayQueue& first, ArrayQueue& second) noexcept
	{
		first.swap(second);
	}
	
	~ArrayQueue()
	{
		delete [] _data;
	}
	
	void enqueue(const T& item)
	{
		_data[_incr(_back)] = item;
		
		if (++_size == _capacity) _resize();
	}
	
	
	const T& front() const
	{
		if (_size == 0)
		{
			throw std::runtime_error("No element at front of queue!");
		}
		
		return _data[_front];
	}
	
	const T& back() const
	{
		if (_size == 0)
		{
			throw std::runtime_error("No element at back of queue!");
		}
		
		return _data[_back];
	}
	
	
	T dequeue()
	{
		if (_size == 0)
		{
			throw std::runtime_error("No element to dequeue from queue!");
		}
		
		auto item = _data[_front];
		
		_incr(_front);
		
		if (--_size == _capacity/4) _resize();
		
		return item;
	}

	void clear()
	{
		delete [] _data;
		
		_size = 0;
		
		_capacity = minimum_capacity;
		
		_data = new T[_capacity];
	}
	
	
	size_t size() const
	{
		return _size;
	}
	
	bool is_empty() const
	{
		return _size == 0;
	}
	
private:
	
	void _resize()
	{
		auto new_capacity = std::max(_size * 2, minimum_capacity);
		
		auto old = _data;
		
		_data = new T[new_capacity];
		
		for (auto i = 0; i < _size; ++i, _incr(_front))
		{
			_data[i] = old[_front];
		}
		
		delete [] old;
		
		_front = 0;
		
		_back = _size - 1;
		
		_capacity = new_capacity;
	}
	
	size_t& _incr(size_t& index)
	{
		index = (index + 1) % _capacity;
		
		return index;
	}
	
	size_t _size;
	
	size_t _capacity;
	
	size_t _front;
	
	size_t _back;
	
	T* _data;
};

template<typename T>
const size_t ArrayQueue<T>::minimum_capacity = 10;