A stack is a collection data type in which elements are removed in the order that they were inserted (with the most recent element being added being the first to be removed). Stacks define two main operations:

• Push: which adds an element to the collection.
• Pop: which removes the most recently added element.

Additionally, a peek operation can be implemented which returns the last value added without removing it.

Abstract Data Type

template <class T>
class Stack {
	public:
		Stack();
	
		void push(const T& element); // Insert into the top of the stack
		T pop(); // Remove and return from the top of the stack
}

Implementation

Singly Linked List

Using a singly linked list with a head pointer and new elements are inserted and deleted at the head of the linked list to ensure insertions and deletions.

Singly linked lists offer better worst case performance as they always maintain insertions, but induce the cost of more memory usage per element when compared to stacks implemented with resizable arrays.

Resizable Array

A resizable array can be used to create a stack by maintaining a integer that stores the index of the last element which is treated as the top of the stack, elements are then inserted at the end of the array, resizing as necessary.

In the best and average case stacks implemented with resizable arrays offer insertions and deletions. However when the array is resized a large performance cost is incurred, the frequency and magnitude of which depends on the algorithm used to resize the array.