[ Overview ]

The following tutorial presents an introduction to the basic data strucures used in Computer Science. We will examine some fundamental data structures: stacks, queues, deque, priority queues and dictionaries.They are among the simplest of all data strucures, but are also the most important.

[ Stack ]

A stack is a data strucure that stores a set of elements in a particular order. It is accessed in a LAST-IN-FIRST-OUT (LIFO) fashion. An object can be inserted into a stack at any time but only the most-recently inserted (ie. last) object can be removed at any time. The stack is an abstract data type (ADT) that supports the following fundamental methods:

push(o): insert o on top of the stack
pop (): remove object from top of the stack
size (): Return the number of objects on the stack
top(): look at object on top of the stack (but don't remove it)
isEmpty(): Return a boolean indicating if the stack is empty

Stack can be implemented by arrays, linked list, to name a few.

[ Queue ]

A queue is a data structure that is very similar to the stack. It is accessed in a FIRST-IN-FIRST-OUT(FIFO) fashion. An object can be inserted at any time but only the element that has been in the queue the longest can be removed at any time. The Queue abstract data type supports the following methods:

enqueue(o): insert object o at rear of queue
dequeue(): remove object from front of queue
size(): return the number of objects in the queue
front(): look at objects at front of queue
isEmpty(): Return a boolean incdicating if the queue is empty

Just like stack, queue can be implemented by arrays, linked list, to name a few.

[ Double-ended Queue / Deque ]

A double-ended queue behaves like a queue but with additional property that it supports insertion and deletion of object at both the front and rear of the queue. It is also called deque (pronouced as "deck") The Deque abstract data type is richer that that of the stack and queue ADTs and support the following methods:

insertFirst(e): insert element at first
insertLast(e): insert element at rear
removeFirst(e): remover first element
removeLast(e): remove element at rear
first(): examine first element
last():examine last element
size(): return the number of elements in the deque
isEmpty(): return a boolean indicating if the deque is empty

Deque can be implemented with a doubly linked list.

Interestingly, the Stack and Queue we discussed earlier can actually be implemented with deques. There is a simple mapping that takes the method of stack and queue and implements them with the Deque operations. For the stack & queue ADT:

[ Priority Queue ]

A Priority Queue is a data structure that stores prioritized element with no notion of storing at a particualr position, unlike the stack and queue. The PQ returns elements in priority order, which is determined by a key. The key may be part of the element data or a separate element. The PQ ADT includes method as follows:

insertItem (k,e): insert element e with key k
extractMin(): return element with minimum key and remove from queue
minElement(): look at min element
minKey(): look at minimum key
size(): return number of elements
isEmpty(): return boolean indicating if queue is empty

The key type needs comparison operator with the following properties to ensure consistent, total ordering:

1) Reflexive: k <= k
2) Antisymmetric: (k1<=k2) && (k2<=k1) --> k1=k2
3) Transitive: (k1<=k2) && (k2<=k3) --> k1<=k3

Priority queues can be implemented by Sequence or a heap.

[ Dictionary ]

A dictionary is a data structure that stores key-element pairs (k,e), which is called an item. There are 2 types of dictionary: ordered vs. unordered. An ordered dictionary determines the relative order of 2 keys by means of a comparator; whereas in an unordered dictionary, no order relation is assumed on the keys and only equality testing between keys is used. As an ADT, dictionary supports the following methods for an unordered dictionary:

size(): return the number of items in Dictionary
isEmpty(): return a boolean indicating if Dictionary is empty
elements(): return the elements stored in Dictionary
keys(): return the keys stored in Dictionary
findElement(k): If D contains the item with key equal k, then return the element, else return NO_SUCH_KEY
findAllElements(k): Return an iterator of all elements with
keys equal to k
insertItem(k,e): Insert an item with element e and key k into Dictionary
removeElement(k): Remove from Dictionary an item with key equal to k and return its element. If D has no such item, return NO_SUCH_KEY
removeAllElements(k): Remove from Dictionary all items with key equal to k and return an iterator of their elements.

For an Ordered Dictionary, we have the following extra methods:

closestKeyBefore(k): Return the key of the item with the largest key less than or equal to k
closestElemBefore(k): Return the element for the item with largest key less than or equal to k
closestKeyAfter(k): Return the key of the item with the smallest key less than or equal to k
closestElemAfter(k): Return the element for the item with smallest key less than or equal to k

An unordered Dictionary can be implemented using Hash Tables or Log File, while an ordered one can be implemented with look up Tables and Skip List.

This is the end of the tutorial to the very basic data structures that are commonly used and seen in Computer Science. Hope this helps. If you need additional resources, check out the links below.