A stack or LIFO (last in, first out) is an abstract data type that serves as a collection of elements, with two principal operations: push, which adds an element to the collection, and pop, which removes the last element that was added.
Push():
Insert new elements into the top of the Stack. Following image will explain it better:
Pop():
Delete an element from the top of the stack. Following image will explain it better:
Implementation:
template<class T>
class Stack
{
public:
Stack<T>(){}
void push(T elem);
void pop();
T top();
bool empty();
~Stack(){}
private:
std::list<T> m_list;
};
template<class T>
void Stack<T>::push(T elem)
{
m_list.push_front(elem);
}
template<class T>
void Stack<T>::pop()
{
m_list.pop_front();
}
template<class T>
T Stack<T>::top()
{
return m_list.front();
}
template<class T>
bool Stack<T>::empty()
{
return m_list.empty();
}
Complexity: O(1) for all of the above operations
Nice tutorial :-)
ReplyDelete