//  A linear list of data accessed first in, first out (FIFO) is called a QUEUE.
//  Pelles C  (vegaseat) 

#include <stdio.h>   // in/out function header
#include <string.h>  // string function header
#include <stdlib.h>  // malloc()

void enter(void);
void list(void);
void q_store(char *ptr);
void q_delete(void);
int store = 0;         // next storage position in queue[] 
int retrieve = 0;      // retrieve position in queue[] 
char *queue[100];      // this array forms the queue 

void main(void)
{
  enter();     // enter some data in the queue and list the data 
  puts("\n\nThis is all the data in the fifo queue:");
  list();   
  q_delete();  // delete first entry in queue and list again
  puts("\n\nThis the data after one deletion (first in, first out):");
  list();    
  getchar();
}

//
// prompt for data entry and store in queue via q_store()
//
void enter(void) 
{
  static char str[100], *ptr;

  do {
    printf("Enter name (ENTER only will exit) : ");
    gets(str);
    ptr = (char *) malloc(strlen(str));  // starting address of memory 
    strcpy(ptr,str);
    if (*str)  
      q_store(ptr);   // store in queue if string has info 
  } while (*str);     // until no entry
}

void list(void)   // list the contents of the queue 
{
  int k;

  for (k = retrieve; k < store; k++)
    printf("\n%d) %s",k+1,queue[k]);
}

//
// store data items in the queue 
//
void q_store(char *ptr)
{   
  if (store == 100) { 
    puts("\nList is full!");  
    return; 
  }
  queue[store] = ptr;
  store++;  // point to next available storage position in queue[] 
}

//
// delete data at retrieve position
//
void q_delete(void)     
{
  if (store == retrieve) { 
    puts("\nQueue is empty!"); 
    return; 
  }
  retrieve++;   // move retrieve position to next data item 
}

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <string>
#include "stackli.h"
using namespace std;

struct flight {
  int num;
};

int main()
{

  flight ted;
  Stack<flight> readyq2;
  int print;

  ted.num = 1;
  readyq2.push(ted);
  ted.num = 2;
  readyq2.push(ted);
  ted.num = 3;
  readyq2.push(ted);

  ted = readyq2.topAndPop();
  cout<<ted.num<<endl;
  ted = readyq2.topAndPop();
  cout<<ted.num<<endl;
  ted = readyq2.topAndPop();
  cout<<ted.num<<endl;

  cout <<"hello"<<endl;

  return 0;
}

#ifndef STACKLI_H
#define STACKLI_H
//#include "dsexceptions.h"
#include <iostream>       // For NULL
// Stack class -- linked list implementation
//
// CONSTRUCTION: with no parameters
//
// ******************PUBLIC OPERATIONS*********************
// void push( x )         --> Insert x
// void pop( )            --> Remove most recently inserted item
// Object top( )          --> Return most recently inserted item
// Object topAndPop( )    --> Return and remove most recently inserted item
// bool isEmpty( )        --> Return true if empty; else false
// bool isFull( )         --> Return true if full; else false
// void makeEmpty( )      --> Remove all items
// ******************ERRORS********************************
// Overflow and Underflow thrown as needed
template <class Object>
class Stack
{
 public:
  Stack( );
  Stack( const Stack & rhs );
  ~Stack( );
  bool isEmpty( ) const;
  bool isFull( ) const;
  const Object & top( ) const;
  void makeEmpty( );
  void pop( );
  void push( const Object & x );
  Object topAndPop( );
 private:
  struct ListNode
            {
	      Object   element;
	      ListNode *next;
	      ListNode( const Object & theElement, ListNode * n = NULL )
		: element( theElement ), next( n ) { }
            };
            ListNode *topOfStack;
};
#include "stackli.cpp"
#endif

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

/**
 * Construct the stack.
 */
        template <class Object>
        Stack<Object>::Stack( )
{
  topOfStack = NULL;
}

/**
 * Copy constructor.
 */
        template <class Object>
        Stack<Object>::Stack( const Stack<Object> & rhs )
{
  topOfStack = NULL;
  *this = rhs;
}

/**
 * Destructor.
 */
        template <class Object>
        Stack<Object>::~Stack( )
{
  makeEmpty( );
}

/**
 * Test if the stack is logically full.
 * Return false always, in this implementation.
 */
        template <class Object>
        bool Stack<Object>::isFull( ) const
{
  return false;
}

/**
 * Test if the stack is logically empty.
 * Return true if empty, false otherwise.
 */
        template <class Object>
        bool Stack<Object>::isEmpty( ) const
{
  return topOfStack == NULL;
}

/**
 * Make the stack logically empty.
 */
        template <class Object>
        void Stack<Object>::makeEmpty( )
{
  while( !isEmpty( ) )
    pop( );
}

/**
 * Get the most recently inserted item in the stack.
 * Return the most recently inserted item in the stack
 * or throw an exception if empty.
 */
        template <class Object>
        const Object & Stack<Object>::top( ) const
{
  if( isEmpty( ) )
    {}
  ListNode *current = topOfStack;

  while(current->next != NULL)
    {
      current = current->next;
    }

  return current->element;
}

/**
 * Remove the most recently inserted item from the stack.
 * Exception Underflow if the stack is empty.
 */
        template <class Object>
        void Stack<Object>::pop( )
{
  if( isEmpty( ) )
    {}

  ListNode *previous = topOfStack;
  ListNode *toTheEnd = topOfStack;

  while(toTheEnd->next != NULL)
    {
      previous = toTheEnd;
      toTheEnd = toTheEnd->next;
    }

  /*************************
  this next line is where the problem lies
  *************************/
  previous->next = NULL;
  delete toTheEnd;
}

/**
 * Return and remove the most recently inserted item
 * from the stack.
 */
        template <class Object>
        Object Stack<Object>::topAndPop( )
{
  Object topItem = top( );
  pop( );
  return topItem;
}

/**
 * Insert x into the stack.
 */
        template <class Object>
        void Stack<Object>::push( const Object & x )
{
  topOfStack = new ListNode( x, topOfStack );

}