/*
* This class implements a stack by directly using a linked list, but adds
* printing to the node construction and destruction so you can see
* when they are created and destroyed.
*/
#include <iostream>
#ifndef _lnkstack_h_
#define _lnkstack_h_
template <typename T>
class Stack {
public:
// Initialize the stack empty.
Stack() {
m_head = nullptr;
m_size = 0;
std::cout << "== Creating Stack ==" << std::endl;
}
// Clean up any remaining nodes.
~Stack() {
std::cout << "== Destroying Stack (" << m_size << " nodes) =="
<< std::endl;
auto scan = m_head;
while(scan != nullptr) {
auto zombie = scan;
scan = scan->next();
delete zombie;
}
m_size = 0; // Unnecessary, since object won't exist any more.
}
// Push the argument item.
void push(const T &itm) {
m_head = new node(itm, m_head);
++m_size;
}
// Pop the argument item, and return true, or return false if the
// the stack is empty.
bool pop(T &itm) {
if(m_head == nullptr) return false;
itm = m_head->data();
node *zombie = m_head;
m_head = m_head->next();
delete zombie;
--m_size;
return true;
}
// Convenience to pop and return the top object. Only works
// for types where T() is a valid expression.
T pop() {
T ret;
if(pop(ret)) return ret;
return T();
}
// Tell if empty.
bool empty() {
return m_head == nullptr;
}
int size() {
return m_size;
}
private:
// Nodes for the linked list.
class node {
public:
node(const T &d, node *n = nullptr) {
m_data = d;
m_next = n;
std::cout << "== Creating node [" << d << "] =="
<< std::endl;
}
~node() {
// This destructor exists only to print.
std::cout << "== Destroying node [" << m_data << "] =="
<< std::endl;
}
const T& data() { return m_data; }
node *next() { return m_next; }
private:
T m_data;
node *m_next;
};
node * m_head; // Head of the linked list.
int m_size; // Size of the stack.
};
#endif