Stack Operations

The two operations that form the majority of the functionality of the stack are the operation of adding to the stack, and the operation of removing items from the stack.

Click here

to View a Simple Animation on Stack & Stack Operation

For historical reasons the operation of adding items to a stack is called push. For similar reasons the operation of removing an item from a stack is usually referred to as pop.

There are a couple more operations that we must consider before we attempt to implement a stack. The first of these is an operation called init. This initialises the stack, and ensures that state of the software is in a known condition before we try to use it. Just about every structure that we will ever use will require an initialisation routine - get into the habit of writing the outline of the init operation first!

As this is a course in developing software, we must also consider the possibility of errors. The easiest error to envisage for a stack is when a program tries to remove an item from an empty stack. This condition is called underflow, and if undetected will probably cause a series of mysterious errors before the program crashes. The method that we use to detect this problem is to use an operation called isEmpty to tell us if the stack is empty. If we try and take data from an empty stack the error condition is usually called underflow. Similarly there is a possibility that we might run out of space. To counter this we can provide an operation called isFull.

Using this analysis we can conclude that we need to provide five operations to implement a stack. These operations are:

init
isEmpty
isFull
push
pop

If we can satisfactorily implement these operations we have implemented a stack. Note that we do not have to say at this stage exactly how these operations are implemented, or exactly how the data is held. There is more than one way of implementing a stack. In this Unit we are going to consider how to implement a stack using an array.

Array Implementation

The first decision that must be made is how big an array to declare to hold the data items in the stack. It is usually prudent to use a constant as the size of the stack. In C a declaration along the lines of:

#define STACKSIZE 10

will declare a stack size of 10 elements (from 0 to 9). If we need to change the size of the stack later we can just change this value and recompile. In addition to the data being held in the stack, we will need to hold data about the stack, in particular the number of entries being held in the stack. We need to hold the data about the stack in the same place as the data in the stack, so this probably means that we need to use a C struct. Trying to use meaningful variable names we have a declaration of:

struct stack{
   int top;
   int items[STACKSIZE];
};

now that we have the declaration of the structure we can make our function prototypes:

void init(struct stack *);

int isEmpty(struct stack);
int isFull(struct stack);
void push(struct stack *, int item);
int pop(struct stack *);

Only now do we have to start thinking about exactly how to implement the operations! The method used in this course is to add items at the location indicated by the index top, and then increment top. The first operation then is to write the init function. All this has to do is to set top to zero (the number of items in a newly created stack):

void init(struct stack * a_stack)

{
   a_stack->top=0;
}

Note the use of the "*" and "->" notation to allow us to change the values in the stack rather than copies of the values.

IsEmpty and IsFull

The next function to define is the isEmpty function.

int isEmpty(struct stack a_stack)

{
  if ( a_stack.top <= 0 )
    return TRUE;
  else
    return FALSE;
}

This function returns either true or false, depending on the value of top. If top is less than zero this means that an uncaught underflow has occurred. In theory this should not happen, but it costs us nothing extra to defend against this problem. We could just use the test for equality ( == ) at this point, but badly behaved code could cause a problem if the value of top skips past zero. Similarly, the isFull code looks like this:

int isFull(struct stack a_stack)
{
  if (a_stack.top < STACKSIZE )
    return FALSE;
  else
    return TRUE;
}

The only point to note in this code is the use of the constant STACKSIZE defined earlier. This is the bulk of the supporting code that we need to provide for our implementation of a stack.

Push and Pop

It would now be appropriate to have a closer look at the push and pop operations.

This depicts the stack after the init operation has been executed. If we are programming in C then the contents of each of the elements of the stack will be filled with arbitrary bit patterns left over from the last time that the memory was used. Other programming languages may be kinder.

Push

The first thing that needs to be performed is a push operation. The diagram shows the changes to be made if the value 10 is pushed onto the stack:

After the push operation, the array holds the pushed value in the location that used to be indexed by top, and top has now moved on to point to the next slot in the array, ready for the next push. The next step is to perform a second push. The second value to be pushed in this example is 20:

Before

After

Pop

Starting from the previous position, we will now show the process of popping an item from the stack. The stack pointer top is currently pointing to location 2. Aspop is the reverse operation from push, the activities should be carried out in reverse order. This means that top will be decremented, then the item being selected for the pop operation will be returned to the calling program. After the pop operation the stack will look as shown:

Before

After

Notice that the value 20 remains in the array, as we have not actually changed the value. The next time we call the push function the new value will be placed in the location, overwriting the current contents

Pop

Before

After

Video Lectures :

Push & POP operation

Friday, October 7, 2011