adt-overview

What is an abstract data type (ADT)?

• An abstract data type (ADT) is a collection of data and a set of operations on that data

• Three common ADT’s are:

  • Stacks

  • Queues

  • Linked lists

Stack operations

What is a stack?

• A stack is an abstract data type that stores data using the Last In, First Out (LIFO) principle

• A stack is like a pile of plates, the last item you put on is the first one you take off

  • PUSH: Add an item to the top of the stack

  • POP: Remove the item from the top

• The first item pushed onto the stack will be the last one popped off

• A stack uses two pointers:

  • A base pointer – points to the first item in the stack

  • A top pointer – points to the last item in the stack

Main operations

• Stacks use a pointer which points to the top of the stack, where the next piece of data will be added (pushed) or the current piece of data can be removed (popped)

Pushing data to a stack

• When pushing (adding) data to a stack, the data is pushed to the position of the pointer

• Once pushed, the pointer will increment by 1, signifying the top of the stack

• Since the stack is a static data structure, an attempt to push an item on to a full stack is called a stack overflow

• This would push ‘Bunny’ onto the empty stack

  

• This would push ‘Dog’ to the top of the stack

  

• This would push ‘Ant’ to the top of the stack

  

Popping data from a stack

• When popping (removing) data from a stack, the data is popped from the position of the pointer

• Once popped, the pointer will decrement by 1, to point at the new top of the stack

• Since the stack is a static data structure, an attempt to pop an item from an empty stack is called a stack underflow

• This would pop ‘Ant’ from the top of the stack

• The new top of the stack would become ‘Dog’

• Note that the data that is ‘popped’ isn’t necessarily erased

• The pointer ‘top’ moves to show that ‘Ant’ is no longer in the stack and depending on the implementation, ‘Ant’ can be deleted or replaced with a null value, or left to be overwritten

Queue operations

What is a queue?

• A queue is an abstract data type that stores data in the order it arrives, using the First In, First Out (FIFO) principle

• A queue works like a line of people waiting at a shop, the first one in is the first one served

  • ENQUEUE: Add an item to the back of the queue

  • DEQUEUE: Remove the item from the front

• The first item added to the queue is the first one removed

Main operations

Linear queues

• A linear queue is a data structure that consists of an array

• Items are added to the next available space in the queue starting from the front

• Items are then removed from the front of the queue

• Before adding an item to the queue you need to check that the queue is not full

• If the end of the array has not been reached, the rear index pointer is incremented and the new item is added to the queue

• In the example below, you can see the queue as the data Adam, Brian and Linda are enqueued.