Back

Stacks

How the stack works
Stacks are another example of a dynamic data structure, and like queues, they can be implemented within an array. Unlike queues, however, data is put into the structure and removed from the structure at the same end of the structure.

Like queues, the data cannot be accessed directly in a stack - you cannot go straight to the middle of a set of data items and retrieve it. You have to remove other data items first. You can think of a stack as lots of CDs stored on a spindle. You put CDs on the spindle, and to remove them you take them off in reverse order. In fact, this kind of device is known as a Last In First Out (LIFO) device because unlike a queue, the last item put into the stack is the first item to be removed. To implement a stack in an array, you need a TOP pointer to point to the top of the stack. An empty stack has TOP = 0. When you put a data item on to the stack, you talk about it being ‘pushed’ onto the stack. When you remove an item, you say it is ‘popped’ from the stack. We will use an array that can hold up to 6 data items as before. 

Step 1: The stack is empty. TOP = 0

Step 2: Firstly, The data item Sheep is pushed onto the stack. Then Cow is pushed onto the stack. TOP = 2

Step 3: The data item Goat is then pushed onto the stack. Then Chicken is pushed onto the stack. TOP = 4

Step 4: The data item Chicken is then popped from the stack. TOP = 3

Step 5: The data item Horse is pushed onto the stack. Then Duck is pushed onto the stack. TOP = 5

Step 6: We want to now remove three items. Remember that items are removed from the stack in the reverse order that they were put onto the stack. So Duck comes off first, then Horse, and finally Goat. TOP = 2

Of course, if the stack becomes full, you can't store any more data in it! If you tried to store another data item in a structure that was full you would get an overflow error message. An overflow happens when you try to store data in a data structure that is full. It can also be used to describe the error that occurs when you try to store a number that is too big for the space reserved for it. For example, if you try to store 452 in one byte you will get an overflow error message because the maximum number that can be stored in one byte is 255.

Algorithms for adding and removing items to and from a stack
So far, we have simply added and removed items from our queue and stack. If we wanted to use a programming language to actually program these operations, we would first want to describe what needs to happen using an algorithm. We will use some pseudo-code to describe how to push an item onto a stack, and how to remove an item from the stack.

Algorithm for pushing an item on to the stack

Check if the stack is full (pointer = maxSize)
IF the stack is full, THEN
   REPORT full and STOP
ELSE
   INCREMENT pointer
   INSERT Data into position pointed to by the pointer
ENDIF
STOP

Algorithm for popping an item from the stack

Check if stack is empty (pointer=0)
IF empty, THEN
   REPORT empty and STOP
ELSE
   Temp := data pointed to by pointer {Temp is a variable to hold the popped data}
   DECREMENT pointer
ENDIF
STOP

The use of the stack when an interrupt happens
A CPU might be working on a program when an interrupt happens. An interrupt is a signal from a piece of software or hardware to the CPU that tells it that it needs some processing time. For example, if the floppy disk drive unit has a problem, an interrupt will be sent to the CPU to say "There is a problem - can you run some software to deal with the problem?"

The CPU, then, is in the middle of something when it receives an interrupt. If it decides to deal with this interrupt immediately, it needs to stop processing its current program (a CPU can only do one thing at a time) but does need to remember where it left off. This is so that it can return to the correct place in the program after it has serviced the interrupt. The way it does this is to push all of its important information (held in ‘registers’) onto the stack. It then jumps to the interrupt handling routine and runs the software to deal with the interrupt. When it has finished dealing with the interrupt, it pops all of the information it stored in the stack back into the CPU’s registers, and the CPU carries on from where it was before. The use of the stack when an interrupt happens is dealt with in much more detail in a later section.

Using the stack for calculations
Calculations in computers are done using the stack, using a technicque known as Reverse Polish. You can find out about Reverse Polish Notation and how it works just in 3.3.7.

The use of a stack to reverse a queue

Mango is at the front of the queue and banana is at the back. In a queue, new items must join the back of the queue and must leave from the front (like a supermarket queue). Suppose you wanted to reverse the order of the queue, so that banana was at the front and mango at the back. You could use a stack to do this.

1. Push all the items onto the stack, starting with the front of the queue, mango, then kiwi fruit etc until you push banana. This gives you a stack that looks like this:

 2. Now pop all of the items out of the stack back into the queue again! Banana is popped first and is now at the head of the queue. Then orange is popped and that joins the queue at the back, behind banana. Then apple, coconut, kiwi fruit and mango are popped in turn. The queue now looks like this:

We have now completely reversed the order of the queue.

Back