#pragma once

#include <iostream>
#include "stack.h"

using namespace std;

namespace linked_stack
{
	template <class TData>
	struct LinkedNode
	{
		TData data;
		LinkedNode<TData>* next;

		explicit LinkedNode(LinkedNode<TData>* next = NULL)
			: next(next) {}

		explicit LinkedNode(const TData& data, LinkedNode<TData>* next = NULL)
			: data(data), next(next) {}
	};
}

//// 链式栈模板类
//template <typename TData> class LinkedStack;
//// 重载<<
//template <typename TData> ostream& operator<<(ostream& os, const LinkedStack<TData>& stack);


template <class TData>
class LinkedStack :public Stack<TData>
{
	// 重载<<
	friend ostream& operator<< <>(ostream& os, const LinkedStack<TData>& stack);

private:
	// 栈顶指针(头节点)
	linked_stack::LinkedNode<TData>* top_;

public:
	LinkedStack() :top_(NULL) {}

	~LinkedStack();

	virtual bool push(const TData& data) override;

	virtual bool pop(TData& data) override;

	bool pop();

	virtual bool top(TData& data) const override;

	virtual bool isEmpty() const override;

	virtual int length() const override;

	void clear();
};

template<typename TData>
inline ostream& operator<<(ostream& os, const LinkedStack<TData>& stack)
{
	os << "栈中元素个数：" << stack.length() << endl;

	linked_stack::LinkedNode<TData>* cur = stack.top_;

	while (cur)
	{
		os << cur->data << endl;
		cur = cur->next;
	}

	return os;
}

template<class TData>
inline LinkedStack<TData>::~LinkedStack()
{
	this->clear();
}

// 就是单链表的头插法
template<class TData>
inline bool LinkedStack<TData>::push(const TData& data)
{
	linked_stack::LinkedNode<TData>* node = new linked_stack::LinkedNode<TData>(data);

	if (!node)
		throw bad_alloc();
	

	node->next = this->top_;

	this->top_ = node;

	return true;
}

template<class TData>
inline bool LinkedStack<TData>::pop(TData& data)
{
	if (this->isEmpty())
		return false;

	linked_stack::LinkedNode<TData>* temp = this->top_;

	this->top_ = this->top_->next;

	data = temp->data;

	delete temp;
	temp = NULL;

	return true;
}

template<class TData>
inline bool LinkedStack<TData>::pop()
{
	if (this->isEmpty())
		return false;

	linked_stack::LinkedNode<TData>* temp = this->top_;
	this->top_ = this->top_->next;

	delete temp;
	temp = NULL;

	return true;
}

template<class TData>
inline bool LinkedStack<TData>::top(TData& data) const
{
	if (this->isEmpty())
		return false;

	data = this->top_->data;

	return true;
}

template<class TData>
inline bool LinkedStack<TData>::isEmpty() const
{
	return this->top_ == NULL;
}

template<class TData>
inline int LinkedStack<TData>::length() const
{
	int length = 0;

	linked_stack::LinkedNode<TData>* cur = this->top_;

	while (cur)
	{
		length++;
		cur = cur->next;
	}

	return length;
}

template<class TData>
inline void LinkedStack<TData>::clear()
{
	while (!this->top_)
	{
		linked_stack::LinkedNode<TData>* target = this->top_;

		this->top_ = this->top_->next;

		delete target;
		// 防止出现悬空指针
		target = NULL;
	}
}