AS/A Computer Science: Fundamentals of data structures

Stacks

A stack is a LIFO (i.e. last in, first out) data structure. A good analogy for a stack is the dirty dishes in a restaurant. As dishes are returned from the front of house they are stacked one on top of the next, beside the sink where the dishwasher is hard at work. New dirty dishes can only be added to the top of the stack. Dishes being removed to be washed can also only be taken from the top of the stack.

Uses of stacks

When you browse websites each site you visit is added to the stack. When you press the back button the last site is popped off the stack.

When you edit a document each instruction is added to the stack. Pressing undo removes this instruction and returns the document to its previous state.

Implementing a stack

A stack can be implemented using either a static data structure e.g. an array or a dynamic data structure e.g. a linked list. As memory is not infinite, either way it will have a maximum size. It will also have a pointer to the top of the stack. A stack has 5 methods:
* push( ) is used to add an item to the stack
* pop( ) removes and returns the last element in the stack
* peek( ) returns without removing, the last element in the stack
* isEmpty( ) tests if the stack is empty
* isFull( ) tests if the stack is full

Creating a stack class

The constructor

The constructor defines our stack, it's maximum size and a pointer to the top of the stack.
The value None is a placeholder in Python so we can have a variable that will store the pointer to the head of the stack but that currently has no value because there is nothing in the stack. Technically we could implement this without the need for a pointer using Python's built in pop( ) function which by default removes the last item added to a list.

Is empty

isEmpty( ) is a method to check if a stack is currently empty. It would be used before attempting to remove an item from a stack to ensure no error is received.

Is full

isFull( ) is a method to check if a stack is currently full. It would be used before attempting to push an item to a stack to ensure no error is received.

Push

push( ) is a method to add an item to a stack. Before attempting to push we check that the queue is not already full. If we add something to the queue then the pointer must be adjusted to point to the location of the last item in the queue.

Pop item

pop_item( ) is a method to remove an item from a stack. Before attempting to pop_item we check that the queue is not already empty. If we remove something from the queue then the pointer must be adjusted to point to the location of the last item in the queue.

Peek

peek( ) is a method to look at the item on the top of a stack without removing it. This can be achieved by referencing the item the pointer identifies.

Getters

These getters allow us to view the stack from top to bottom or view the pointer. They are mainly for the purpose of demonstrating the stack in use.

Example of a stack in use

Knowledge check

Questions:

Correct:

Question text