Intermediate - Stacks

In this course and the next two courses, we'll be going through two data structures in programming: Stacks and Queues. This course will be on stacks and its basic operations.

What is a stack?

There are many types of data structures which allow the storing of information, and a stack is one of them. A stack is a data structure that allows items to be added and removed from one end. That's why it's also described as a LIFO stack. Last In First Out. A stack can be directly compared to some real-life objects. For example, a stack of trays. Trays are only added and removed from the top. A stack of exercise books can also be used as another analogy. Students only take away or pass up exercise books from the top.

So what's the use of a stack?

While it may seem pretty useless to have a data structure that only accepts input and output from one end, you'll realize that certain applications would become easier to write when implementing stacks. For example, a calculator. Calculators are able to calculate calculations while following the rules of precedence by using stacks. Stacks are also used in your computer's allocation of memory. You see, even though the structure might seem quite rigid, stacks can actually be used in a great number of situations.

How are stacks implemented then?

Okay, let's get a bit into the theory. A stack can be implemented using an array and a number indicating the top of the stack. There is a flaw, however, that the capacity of the stack is fixed and limited. However, we could use Linked Lists to implement it so that the stack dynamically expands its capacity.

There are five basic operations associated with a stack:

init_stack
initializes an empty stack
empty_stack
returns true if stack is empty
push
inserts element onto top of stack
pop
remove, and if necessary, return the top element of stack
top
return, without removing, the top element of stack

By the way, the terms push and pop are used to describe the act of inserting or removing elements in a stack. To push is to insert an element. To pop is to remove an element. Note however, that these terms are only used in stacks.

Alright, let's start coding!

We'll start off first by declaring a constant, MAX, as the maximum height of the stack. This way, we can easily increase the maximum height as needed.

  const
    MAX = 20;

As mentioned before, each stack is made up of an array, and a number indicating its top. Since we want to make it modular, let's make our own type definition. (To learn more about user defined types, look up 'type' in the online help.)

  type
    int_Stack = record
                  int_array: array[0..MAX] of integer;
                  top: integer;
                end;

Now let's code all the five basic operations. The 'trick' is this: We identify that a stack is empty when top is equal to -1. That's why when we initialize it, we set top to become -1. Then when something is pushed, top increases to become 0. It's that simple!

  function is_empty(s: int_Stack) : boolean;
    begin
      is_empty := (s.top = -1);
    end;

  function is_full(s: int_Stack) : boolean;
    begin
      is_full := (s.top = MAX);
    end;

  function top(s: int_Stack) : integer;
    begin
      top := s.int_array[s.top];
    end;

  procedure push(var s: int_Stack; x: integer);
    begin
      if is_full(s) then
        Writeln('Stack Full')
      else
        begin
          s.top := s.top + 1;
          s.int_array[s.top] := x;
        end;
    end;

  function pop(var s: int_Stack) : integer;

    var
      t: integer;

    begin
      if is_empty(s) then
        Writeln('Stack Empty')
      else
        begin
          t := s.int_array[s.top];
          s.top := s.top - 1;
          pop := t;
        end;
    end;

Great! Now, with this library of commands, you can easily implement stacks into any program. But it doesn't end here. Go on to the next course to learn about Queues and how to implement them.