Wednesday, August 17, 2011

How stacks work, and how to implement

What is a stack?

A stack is a data structure in which elements can only be added and removed from one end. A good way to think about a stack is like a stack of plates. You can push(add) plates to the top of the stack or pop(remove) them from the top of the stack. The only way to get to a plate in the middle of the stack is to first remove the plates that are on top of it. Afterwards the other plates can be added back onto the stack.

1 ->

5 -> 1

9-> 1 5

1 5 9

You can see from the diagram above that as elements are pushed onto the stack they are appended to the end of the structure. Now if we were to pop the top value from the stack you would remove the top value. The result would be the following:

1 5

But what if I don't want to remove the element you ask? Well in that case you would just want to 'peek' at or read the value of the top element. This structure is usually provided in a library or as part of the language. In perl arrays already have these functions. But for the sake of the structure, the following code is a simple implementation of how this would be implemented in Perl.

$top = 0;

sub push{
my ($arr,$element) = @_;
$arr[top] = $element;

sub pop {
my $arr = shift;
$elem = $arr[top];
$arr[top] = 0;
$top = $top -1;
return $elem;

sub peek {
my $arr = shift;
return $arr[top];

@arr = ();

print "@arr";
my $topElem = pop(\@arr);
print "@arr";
$topElem = peek(\@arr);