Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * Stack class
- * raw pointers
- * no Iterator
- * just the basics
- *
- * Author: Mark Ruff
- */
- template <class T>
- class Stack {
- private:
- // Define elements/nodes in the stack (unidirectional linked list)
- class StackElement {
- protected:
- T value;
- StackElement* next;
- public:
- StackElement(T value, StackElement* next)
- : value(value)
- , next(next)
- { }
- friend Stack<T>;
- };
- private:
- // Pointer to the top of the stack
- StackElement* top;
- // height of the stack
- int size;
- // recursive method used as copy constructor
- StackElement* recursiveCopy(const StackElement ¤t) {
- if ( current.next == 0 ) {
- return new StackElement(current.value, 0);
- }
- return new StackElement(current, recursiveCopy(current.next) );
- }
- public:
- // Constructor: empty stack
- Stack<T>() : top(0), size(0) { }
- // Constructor: copy constructor
- Stack<T>(const Stack<T> &that) {
- if ( that.top == 0 ) {
- top = 0;
- size = 0;
- }
- else {
- top = recursiveCopy(*(that.top));
- size = that.size();
- }
- }
- // Destructor: delete all StackElements
- ~Stack<T>() {
- while(top != 0) {
- StackElement* temp = top;
- top = temp->next;
- delete temp;
- }
- }
- // Push an element onto the stack
- void push(T value) {
- StackElement* element = new StackElement(value,top);
- top = element;
- size++;
- }
- // Pop an element off the stack
- // You mustn't pop an empty stack
- T pop() {
- StackElement* popped = top;
- T return_value = popped->value;
- top = popped->next;
- size--;
- delete popped;
- return return_value;
- }
- // Peek at the top element without popping it
- // You also mustn't peek at an empty stack
- T peek() {
- return top->value;
- }
- // return true if stack size = 0
- bool empty() {
- if ( size == 0 ) { return true; }
- else { return false; }
- }
- // return the height of the stack
- int height() { return size; }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement