#pragma once
#include <iostream>
using namespace std ;
 
typedef char ItemType; 
struct NodeType
{
	ItemType info ;
	NodeType* next ;
};
 
class FullStack
// Exception class thrown by Push when stack is full.
{};
 
class EmptyStack
// Exception class thrown by Pop and Top when stack is emtpy.
{};
 
class StackType
{
public:
  StackType();		
  StackType(const StackType & copy) ;
  ~StackType();		
  void Push(ItemType);
  void Pop();
  ItemType Top();
  bool IsEmpty() const;
  bool IsFull() const;
  bool Identical(StackType stack) ;
private:
  NodeType* topPtr;
  int length ;
};
 
 
 
#include "StackType.h"
 
// Implementation file for linked StackType
void StackType::Push(ItemType newItem)
// Adds newItem to the top of the stack.
// Stack is bounded by size of memory.
// Pre:  Stack has been initialized.
// Post: If stack is full, FullStack exception is thrown;
//       else newItem is at the top of the stack.
 
{
  if (IsFull())
    throw FullStack();
  else
  {
    NodeType* location;
    location = new NodeType;
    location->info = newItem;
    location->next = topPtr;
    topPtr = location;
	length++ ;
  }
}
void StackType::Pop()
// Removes top item from Stack and returns it in item.
// Pre:  Stack has been initialized.
// Post: If stack is empty, EmptyStack exception is thrown;
//       else top element has been removed.
{
  if (IsEmpty())
    throw EmptyStack();
  else
  {  
    NodeType* tempPtr;
    tempPtr = topPtr;
    topPtr = topPtr->next;
    delete tempPtr;
	length++ ;
  }
}
ItemType StackType::Top()
// Returns a copy of the top item in the stack.
// Pre:  Stack has been initialized.
// Post: If stack is empty, EmptyStack exception is thrown;
//       else a copy of the top element is returned.
{
  if (IsEmpty())
    throw EmptyStack();
  else
    return topPtr->info;  
}
StackType::StackType()	// Class constructor.
{
    topPtr = NULL;
	length = 0 ;
}
 
StackType::StackType(const StackType & st)	// copy c-tor
{ 
	if ( st.topPtr == NULL )
		topPtr = NULL;
	else			    
	{	
		NodeType * stptr;	// pointer to source Stack
		NodeType * p;	// pointer to target Stack  
		topPtr = new NodeType(st.topPtr->info);    // first node
		stptr = st.topPtr->next;	// point to second Node
		p = topPtr;        // initialize pointer to Stack copy
		while ( stptr != NULL )   // deep copy other nodes
		{	
			p->next = new NodeType(stptr->info);
			p = p->next;	// update pointers
			stptr = stptr->next;
		} // endwhile
		p->next = NULL;
	} // endif
}
 
bool StackType::IsFull() const
// Returns true if there is no room for another ItemType 
//  on the free store; false otherwise.
{
  NodeType* location;
  try
  {
    location = new NodeType;
    delete location;
    return false;
  }
  catch(std::bad_alloc exception)
  {
    return true;
  }
}
 
bool StackType::IsEmpty() const
{
	return (topPtr == NULL) ;
}
 
StackType::~StackType()
// Post: stack is empty; all items have been deallocated.
{
  NodeType* tempPtr;
 
  while (topPtr != NULL)
  {
    tempPtr = topPtr;
    topPtr = topPtr->next;
    delete tempPtr;
  }
}
 
bool StackType::Identical(StackType stack)
{
	NodeType* tmp = stack.topPtr ;
	NodeType* tmp2 = topPtr ;
	bool iden = true ;
 
	if (length != stack.length)
		iden = false ;
 
	while(tmp->next != NULL && tmp2->next != NULL && iden)
	{
		if (tmp->info == tmp2->info)
		{
			iden = true ;
			tmp = tmp->next ;
			tmp2 = tmp2->next ;
		}
		else
			iden = false ;
	}
 
	return iden ;	
}
 
 
#include "StackType.h"
 
int main()
{
	ItemType a = 'a' ;
	ItemType b = 'b' ;
	ItemType c = 'c' ;
	ItemType d = 'd' ;
 
	StackType stack ;
	stack.Push(a) ;
	stack.Push(b) ;
	stack.Push(c) ;
	stack.Push(d) ;
 
	StackType stack_two ;
	stack_two.Push(a) ;
	stack_two.Push(b) ;
	stack_two.Push(c) ;
	stack_two.Push(d) ;
 
	bool iden = stack.Identical(stack_two) ;
	if (iden)
		cout << "Identical!\n" ;
	else
		cout << "Not Identical!\n" ;
 
	cout << "\n-- Program Complete --\n" ;
 
	return 0 ;
}

struct NodeType
{
	ItemType info ;
	NodeType* next ;
    NodeType(ItemType t) {info = t; next = NULL;}
    NodeType() {info = 0; next = NULL;}
};