/**
 * Stack class from before modified to use a linked list instead of
 * a statically allocated array.  Use with exmaple application from
 * before.
 */

using namespace std;

#include <cassert>
#include <cstdlib>

#include "stack.h"

/**
 * Constructs an empty stack.
 */

Stack::Stack()
{
  // initialize head pointer

  head = NULL;
}

/**
 * pre: none
 * post: returns true iff the stack is full.
 */

bool Stack::isFull() const
{
  // we assume a never-ending supply of memory here

  return false;
}

/**
 * pre: none
 * post: returns true iff the stack is empty
 */

bool Stack::isEmpty() const
{
  // empty iff no head

  return (head == NULL);
}

/**
 * pre: this stack is not empty
 * post: the top item is removed from this stack and copied into the parameter
 */

void Stack::pop(ItemType& popped)
{
  assert(head != NULL);

  // get info out of head
  popped = head->info;

  // remember where old head was so we can delete it later
  Node* oldHead = head;

  // set head to next node
  head = head->next;

  // remove old head to avoid memory leak
  delete oldHead;
}

/**
 * pre: none
 * post: the stack is empty
 */

void Stack::makeEmpty()
{
  Node *curr = head;

  // run through all nodes, deleting each one

  while (curr != NULL)
    {
      Node *temp = curr->next;
      delete curr;
      curr = temp; // can't do standard curr = curr->next here since we deleted curr
    }

  head = NULL;
}

/**
 * pre: this stack is not full
 * post: item toAdd has been added to this stack
 */

void Stack::push(const ItemType& toAdd)
{
  assert(!isFull());

  // make new node
  Node* newHead = new Node;

  // initialize its info
  newHead->info = toAdd;


  // link to existing nodes
  newHead->next = head;

  // make it the new head
  head = newHead;
}