I implemented std::stack
from the STL for deeper understanding of the language and memory since I still am only a beginner. I implemented the stack using a singly linked list.
Header file:
/* Header file for abstract data type "STACK" implemented using a linked list */
#ifndef STACK_H
#define STACK_H
template <class T>
class stack {
public:
void push(T); //Function that inserts elements into the stack
bool empty(); //Function to test whether the stack is empty
T top(); //Returns top element of stack
void pop(); //Removes element at the top of the stack
int size(); //Returns size of stack
void print(); //Prints stack contents
struct node { //Definition of node structure with constructor and destructor
T node_data;
node *next;
//default ctor
node() { next = nullptr; }
//default dtor
~node() { delete root_node; }
};
private:
node *root_node = nullptr;
int elements = 0;
};
#endif //STACK_H
And here is the actual implementation file:
/* Definitons of the STACK data structure implemented using a linked list */
#include <iostream>
#include "stack.h"
using std::cout;
using std::endl;
/* FUNCTION: Test to check if the stack is empty or has at least one element */
template <class T>
bool stack<T>::empty() { return (root_node == nullptr); }
/* FUNCTION: Returns current size of the stack */
template <class T>
int stack<T>::size() { return elements; }
/* FUNCTION: Adds nodes to the stack with one argument which is the data to be inserted */
template <class T>
void stack<T>::push(T data) {
//Operation to preform if the stack is empty.
//Root element is popped off last (First in, Last out)
if ( empty() ) {
root_node = new node;
root_node->node_data = data;
root_node->next = nullptr;
elements++;
}
//Operation to preform if stack is not empty.
//Elements inserted into stack with dynamic allocation.
else {
node *new_node = new node;
*new_node = *root_node;
root_node->next = new_node;
root_node->node_data = data;
elements++;
}
}
/* FUNCTION: Removes element at the top of the stack */
template <class T>
void stack<T>::pop() {
if (size() > 1) {
node *temp_node = new node;
temp_node = root_node->next;
root_node = temp_node;
elements--;
}
else if (size() == 1) {
root_node = nullptr;
elements--;
}
else {cout << "\nOperation pop() failed: Stack is empty!" << endl;}
}
/* FUNCTION: Retrieves element at the top of the stack */
template <class T>
T stack<T>::top() {
if (!empty()) {return root_node->node_data;}
else {cout << "\nOperation top() failed: Stack is empty!" << endl; return -1;}
}
/* FUNCTION: Prints the stack contents */
template <class T>
void stack<T>::print() {
int index = size();
for (int i = 1; i < index; i++) {
cout << "Element " << i << ": " << " " << top() << endl;
pop();
}
}
I would appreciate all criticism relevant to code, style, flow, camelCase vs underscore, and so forth.
public
andprivate
) should be indented, preferably by four spaces. This will also make it easier for reviewers to study the code. \$\endgroup\$stack
as it's specified in the C++ standard. Thestack
in the standard is a container adapter, which uses some underlying sequence container as its storage, so it just translatespush
intopush_back
,pop
intopop_back
, and so on. The standard gives not only the interface, but nearly the entire implementation. \$\endgroup\$