//
// 	Stack ADT implementation with linked lists
//	p.272
//

#include <iostream>

using namespace std;

struct NodeType
{
	int info;
	NodeType* next;
};

class StackType
{
	NodeType* topPtr;
public:
	// constructor, p.276
	StackType()
	{	topPtr = NULL;  }
	~Stack()	// delete all, p.277
			// needed for linked list implementations
	{	NodeType* tempPre;
		while( topPtr != NULL )
		{
			tempPtr = topPtr;
			topPtr = topPtr->next;
			delete tempPtr;
		}
	}
	void Push(int newItem)    // p.273
	{	NodeType* location = new NodeType;
		location->info = newItem;
		location->next = topPtr;
		topPtr = location;
	}
	void Print() const
	{
		NodeType* temp = topPtr;
		while(temp != NULL)
		{
			cout << temp->info << " ";
			temp = temp->next;
		}
		cout << "\n";
	}
	void Pop()	// p.273
	{	NodeType* temp = topPtr;
		topPtr = topPtr->next;
		delete temp;
	}
	int POP()	// return the top value
	{	int value = topPtr->info;
		NodeType* temp = topPtr;
		topPtr = topPtr->next;
		delete temp;
		return value;
	}
	bool IsEmpty() const
	{	return topPtr == NULL;	}
};

int main()
{
	StackType st;
	// (top) 2, 17, 6
	st.Push(6);
	st.Push(17);
	st.Push(2);
	st.Print();

	st.Push(45);	// 45 2 17 6
	st.Print();

	// call Pop
	st.Pop();  cout << "\nAfter Pop, the stack is: ";
	st.Print();	
	
	cout << "\n\nDone.\n\n";
	return 0;
}