Stack
Stack is a last-in-first-out data structure. It is defined by two basic operations: insert a new item, and remove an item.
So based on stack LIFO rule when a new element is added, it is always placed to top of the stack. Remove method delete the top element from the stack.For example when you click a hyperlink, your browser displays the new page (and inserts it onto a stack). You can keep clicking on hyperlinks to visit new pages. You can always revisit the previous page by clicking the back button (remove it from a stack).
The C++ code below gives a simple insight to a stack implementation. It is a dynamic implementation based on pointer arithmetics. The inner structure called Node, holds the value and a pointer to the next node. The stack wrap around the nodes and it provides methods for adding and removing element. The stack has a unique Node pointer called head for accessing the top element of the stack.
#include <stdexcept>
namespace DataStructure {
template<typename T>
class Stack {
public:
Stack() = default;
virtual ~Stack();
void push(T const&);
void push(T&&);
auto pop() -> T;
auto top() const->T;
bool isEmpty() const;
void print() const;
private:
struct Node {
T value;
Node* pNext;
Node() : value(0), pNext(nullptr) {}
Node(const int& _value) : value(_value), pNext(nullptr) {}
Node(const int& _value, Node* _pNext) : value(_value), pNext(_pNext) {}
Node(T&& _value) : value(std::move(_value)), pNext(nullptr) {}
};
Node* pHead = nullptr;
};
};
The destructor deallocates the used memory. While the stack is not empty remove the top element.
template<typename T>
DataStructure::Stack<T>::~Stack() {
while (!isEmpty())
pop();
}
Method isEmpty return true if the head pointer doesn't hold any data, e.i.: pHead = null pointer.
template<typename T>
bool DataStructure::Stack<T>::isEmpty() const{
return pHead == nullptr;
}
The push method allocates a new node in dynamic way and links to the top of the stack and finally refresh the head pointer. The second push method does the same but in a smarter way using C++11 move semantic.
template<typename T>
void DataStructure::Stack<T>::push(T const& _item) {
Node* p = new Node(_item);
p->pNext = pHead;
pHead = p;
}
template<typename T>
void DataStructure::Stack<T>::push(T&& _item) {
Node* p = new Node(std::forward<T>(_item));
p->pNext = pHead;
pHead = p;
}
The pop method remove and return back with the top element of the stack and refresh the head pointer to the next element. The second pop such as the push uses the move semantic.
template<typename T>
auto DataStructure::Stack<T>::pop() -> T {
if (isEmpty())
throw std::runtime_error("UnderFLowException");
T tmp = pHead->value;
Node* p = pHead;
pHead = pHead->pNext;
delete p;
return tmp;
}
template<typename T>
auto DataStructure::Stack<T>::top() const -> T {
if (isEmpty())
throw std::runtime_error("UnderFLowException");
return pHead->value;
}
The print method is only a helper function for show the data and it is not part of the data structure.
#include <thread>
#include <mutex>
#include <condition_variable>
namespace DataStructure {
template<typename T>
class ThreadSafeStack {
public:
T pop();
void push(const T&);
ThreadSafeStack() = default;
ThreadSafeStack(const ThreadSafeStack&) = delete; // disable copying
ThreadSafeStack& operator=(const ThreadSafeStack&) = delete; // disable assignment
private:
DataStructure::Stack<T> stack_;
std::mutex mutex_;
std::condition_variable cond_;
};
};
Thread safe push and pop are a wrapper for the original stack push and pop methods. While stack is empty the pop method is disabled. When a new element is pushed it notifies the threads and pop is enable again.
template<typename T>
T DataStructure::ThreadSafeStack<T>::pop() {
std::unique_lock<std::mutex> mlock(mutex_);
while (stack_.isEmpty()) {
cond_.wait(mlock);
}
auto val = stack_.top();
stack_.pop();
return val;
}
template<typename T>
void DataStructure::ThreadSafeStack<T>::push(const T& item) {
std::unique_lock<std::mutex> mlock(mutex_);
stack_.push(item);
mlock.unlock();
cond_.notify_one();
}
The next code demonstrates the the operating stack. The produce method push while the consume method pop from the stack. We create a producer and four consumer thread.
#include <iostream>
#include <random>
#include <functional>
#include <ctime>
#include <exception>
void produce(DataStructure::ThreadSafeStack<int>& q) {
for (int i = 0; i< 100; ++i) {
std::cout << "Pushing " << i << "\n";
q.push(i);
}
}
void consume(DataStructure::ThreadSafeStack<int>& q, unsigned int id) {
for (int i = 0; i< 25; ++i) {
auto item = q.pop();
std::cout << "Consumer " << id << " popped " << item << "\n";
}
}
std::cout << "Testing data structure Stack ...\n\n";
////////// Using random generator engine //////////
std::default_random_engine gen((unsigned int)std::time(0));
std::uniform_int_distribution<int> distribution(1, 50);
auto randInt = std::bind(distribution, gen); // using randInt() generate integer number between (1-50)
DataStructure::ThreadSafeStack<int> q;
using namespace std::placeholders;
// producer thread
std::thread prod1(std::bind(produce, std::ref(q)));
// consumer threads
std::thread consumer1(std::bind(&consume, std::ref(q), 1));
std::thread consumer2(std::bind(&consume, std::ref(q), 2));
std::thread consumer3(std::bind(&consume, std::ref(q), 3));
std::thread consumer4(std::bind(&consume, std::ref(q), 4));
prod1.join();
consumer1.join();
consumer2.join();
consumer3.join();
consumer4.join();