Stacks

A stack is a data structure that resembles a stack of of boxes. The first box you put on the floor is the last to be removed, and the last box you stack up is the first to be removed. This is what we call First In Last Out or FILO.

Operations

  • Push is the operation to add items to a stack.

    Items are added to the stack from one end

    Items are added to the stack from one end


  • Pop is the operation to retrieve and remove items from a stack.

    Removing items from a stack is performed from the same end at which we add items achieving FILO design concept.

    Removing items from a stack is performed from the same end at which we add items achieving FILO design concept.

Use Cases

  • Call Stack: A call stack is a stack used by an operating system to keep track of function or method calls in a program. For instance a program may has a main() function which, in turn, calls a function called CreateDriveresLicense() which then calls a third function called GenerateLicenseNumber(). Every time a function is called, it is pushed to the call stack, and when the function is finished, it is popped from the call stack.
  • Expression Evaluation:One of the ways computers evaluate expressions is by storing the expression in two or more stacks (depending on the algorithm). Then to process the expression, items of stacks are popped and and the expression is calculated based on operator order and precedence. If you want to read more, here is a good article about an algorithm for computers to evaluate expressions.

Implementation

Now we know what stacks are. Let’s think about how to implement a stack in C++. Obviously, we’ll create a class Stack, but we have to have some type of a data structure to store our data for us. We can use an array as a private member of Stack and keep track of top of the stack using a pointer. One problem though, arrays are static! They have a limited size and resizing arrays is really costly because we have to declare a bigger array and copy the contents into the new, bigger array.

On the other hand, we can design a data structure that allocates memory dynamically for every item we create, and free it when we remove the item from the stack. If you think about it, the data structure that we want is very similar to the Linked List data structure we developed before. So, can we reuse that code some how to create our stack data structure? Let’s take a look.

#include "List.h"

template <typename T>
class Stack
{
public:
	Stack<T>(void) { _size = 0; }
	~Stack<T>(void) {};

	void push(T item); // Adds item to stack
	T pop(); // Removes and returns item from stack

	int size() { return _size; }

private:
	List<T> _stack;
	int _size;
};

As you can see above, we declared two methods: void push(T item) adds items to the top of the stack, and T pop() removes items. Also, we are declaring a size member so we can query the sizes of Stack objects.

In the private section, we declare _stack of type List which we will use to stack items.

Let’s take a look at push() and pop() methods:

template <typename T>
void Stack<T>::push(T item)
{
	this->_size++;
	this->_stack.addToHead(item);
}

template <typename T>
T Stack<T>::pop()
{
	this->_size--;
	return this->_stack.deleteFromHead();
}

As you see, push and pop become very simple once we employ our all-ready-to-use Linked List class.

In push() we inclrement our _size member then we pass our item to addToHead() method to add our item to the head of the list.. or the top of the stack. Probably, you can already tell that this method runs in constant time O(1) and that is because addToHead() runs in constant time.

Similarly, pop() decrements our _stack member then it removes an item and return it using deleteFromHead(). Since deleteFromHead() runs in constant time O(1), pop() also runs in constant time.

Stack are good choice of data structure for nested operations, expression evaluation, keep track of user navigation in case of accessible history feature, etc.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>