Stacks

A stack is a data structure for holding objects. It is a LIFO structure. It supports two operations: pop and push.

pop returns (and removes) the last inserted element.

push adds a new element to the stack.

A Pez dispenser is a stack.

Implementations

Linked List

You can implement it with a linked list. Both push and pop commands are \(O(1)\).

Array

You can implement it using an array. The first element is inserted in the front of the array, and each additional push is inserted in the succeeding element, with an index keeping track of how much data you’ve kept in there. When you pop, you simply decrement the counter.

However, there are complications:

You have to manually maintain the size of the stack.
When you pop, you need to set the popped element of the array to NULL - otherwise you could end up with a memory leak as there will always be a pointer to the object.
You need to allocate the array size appropriately.

Resizing Arrays

Don’t resize after every push. This will cost \(O(N^{2})\) to insert \(N\) objects.

Instead, implement array doubling. Every time the array is full, allocate a new array twice as big and copy all the data over. Amortized, this costs \(O(N)\) to insert \(N\) objects.

To reduce the size of an array, it’s tempting to halve the array when it is half full, but this leads to thrashing. If you have a sequence of push and pops at the half point, you’ll keep allocating arrays and halving. So instead, halve it when the array is quarter full.

The two together lead to a guarantee that the array will be between 25% and 100% full.

Linked List vs Arrays

Most individual operations in arrays are quicker than the overhead of maintaining a linked list (with less memory per item). But with a linked list you never get sudden slow downs due to allocations.

Applications

You can evaluate infix expressions (e.g. (2 + 3 * (1 + 2)) / (1 + 1/(1+2))) with a stack. Two stacks, actually - one for the operands, and another for the operators. Whenever you encounter a right parenthesis, pop from the operator stack and pop two values and operate on them. Push the result back onto the operand stack.

Implementations In Code

Python

Python lists can be used as stacks. Not ideal, as you can do more with Python lists to mess up your stack data structure.

One could also use the Queue module and specify the queue to be LIFO.

from Queue import LifoQueue

stack = LifoQueue()

stack.put(10)
stack.put(12)
print stack.get()
stack.put(14)
print stack.get()
print stack.get()

C++

The STL has a stack class.

By default it utilizes a double ended queue, even though it’s a single ended stack. You can make it use a list or a vector in the backend if you desire by passing std::list or std::vector to the argument of Container.

Note that pop() does not return the value. To access it, use top().

#include <iostream>
#include <stack>

int main(void) {

  std::stack<int> s;

  s.push(10);
  s.push(12);

  std::cout << s.top() << std::endl;
  s.pop();
  s.push(14);
  std::cout << s.top() << std::endl;
  s.pop();
  std::cout << s.top() << std::endl;

  return 0;
}