// A stack class
//
// Charles A. Cusack, May 1999
// Modified January 2001.
//
#include<cstdlib>
using namespace std;
//-------------------------------------------------------------------------
// Struct for a node.
struct node {
public:
int key; // The data. You may assume the data is positive
node *next; // The pointer to the next node
};
//-------------------------------------------------------------------------
class stack {
private:
struct node *head; // pointer to the head
public:
// The constructor. creates an empty stack
// Precondition : none
// Postcondition: the variable head has an appropriate value assigned
//
stack();
// The destructor. Deallocated the memory assigned to pointers
//Precondition : The stack exists.
//Postcondition: Memory used by the stack is freed
//
~stack();
//Copy Constructor
//Initializes stack by making a copy of an existing stack object
//Precondition : Stack S exists
//Postcondition: a "deep" copy of S is made.
//
stack(const stack &S);
//Overloaded assignment operator
//copy a stack by making a copy of an existing stack object
//Precondition : Stack S exists.
//Postcondition: Any memory used in the current stack is deallocated,
// and the current stack is a "deep" copy of S.
//
stack &operator =(const stack &S);
//Overloaded + operator, where + means append.
//Precondition : X and Y are possible empty stacks.
//Postcondition: Return a stack which consists of the elements of
// stack X followed by the elements of stack Y.
// X and Y are unchanged.
// Example: If X=[1,4,6,7] and Y=[5,3,9,2], where the top of the
// stack is the right, return a stack contining [1,4,6,7,5,3,9,2]
//
friend stack& operator+(const stack X,const stack Y);
//Adds a value to the top of the stack
//Precondition : The stack exists. The parameter x is a positive
// integer to be added to the top of the stack. There is memory
// available to add the new item in the stack.
//Postcondition: If the stack is not full, the item is added to the top
// of the stack, and 1 is returned.
// Otherwise, the stack is unchanged, and 0 is returned.
//
int push(int x);
//Removes a value from the top of the stack
//Precondition : The stack exists.
//Postcondition: If the stack is not empty, it has its top value removed
// and returned. If the stack is empty, -1 is returned.
//
int pop();
//Returns the value from the top of the stack without removing it
//Precondition : The stack exists.
//Postcondition: If the stack is not empty it has its top value returned.
// If the stack is empty -1 is returned.
//
int peek();
//Is the stack empty?
//Precondition : The stack exists.
//Postcondition: returns 1 if the stack is empty (has no elements)
// and 0 otherwise.
//
bool empty();
//Is the stack full?
//Precondition : The stack exists.
//Postcondition: returns 1 if the stack is full and 0 otherwise.
// NOTE: For a linked list implementation, the only way it can be full
// is if there is no more memory to allocate.
//
bool full();
};
//-------------------------------------------------------------------------
//Converts a stack into an array with the first item that had been
//pushed onto the stack the 0th item of the array, the 2nd item
//that had been pushed onto the stack the 1st item of the
//array, and so on, until finally the top item is added
//to the array, and the remainder of the array padded with
//zeros.
//
//Note that if there were x items in the stack, the first one
//popped from the stack would be in the (x-1)th position of
//the stack, and the xth through the nth positions would be
//filled with zeros.
//
//Precondition : The stack exists, and n is greater than or equal to
// the number of items in the stack.
//Postcondition: returns a pointer to the array of length n
// whose contents are the items from the stack as described above.
//
int* stack2array(const stack S,int n);
//-------------------------------------------------------------------------