Introduction to Classic Data Structures - Part 2


A way of organizing data in order to use it efficiently is called a data structure. Read this article for a brief introduction of some classic data structures i.e. queues, trees etc,. and their applications.

Data must be organized in a way such that it can be used efficiently. Such a way is called a data structure. Some of the classic data structures are arrays, linked lists, stack ADT, queue ADT, trees, graphs, tables etc,. The general operations on data structures are insertion of an element, deletion of an element, displaying the data structure, sorting the elements etc,.

For information on the classic data structures like linked lists, stacks etc., refer the article Introduction to Classic Data Structures - Part 1.

Queues


Queue is a data structure which follows First In First Out Principle (FIFO). Insertion operation and deletion operation can be done one at each end of a queue. People standing in a line for movie ticket at a ticket counter is a real life example of a queue. The person who goes first into the line (first in) will come out first from the line (first out). Queues may be linear queues or circular queues. If the end of a linear queue is connected to its start, it is called a circular queue. A priority queue is a variant of a queue such that each element has a priority. A deque is a variant of a queue such that insertion/deletion can be performed at both ends. A queue and its ends at which insertion and deletion are performed:
Queue Abstract Data Type

Technical Terms


REAR : The pointer to the end of the queue at which insertion is done.
FRONT : The pointer to the end of the queue at which deletion is done.
ENQUEUE : To insert an element (at REAR) into the queue.
DEQUEUE : To delete an element (at FRONT) from the queue.

Applications


Queues are used in radix sort i.e. for the ten auxiliary arrays. They can be used for simulation i.e. modeling of a real life problem. A circular queue can be used to implement the Round Robin Scheduling algorithm. In addition, queues can be useful for CPU scheduling in multi programming environments i.e. in scheduling algorithms. Refer these articles for more information on linear queues and circular queues.

Trees


As the name says, elements are represented in a tree form. A binary tree is a tree such that each element has a maximum of two successors. A full binary tree is a binary tree such that there are maximum number of elements in each level. A complete binary tree is a binary tree such that there are maximum number of elements in each level with an exception for last level. A tree can be traversed in pre order or in order or post order (root, left, right or left, root, right or left, right, root respectively). A tree data structure:
Tree

Technical Terms


Node : An element of a tree is called a node.
Root : The node at the top of the tree.
Leaf : A node at the bottom of the tree.
Parent : A node having successor nodes.
Child : A successor node to another node.

Applications


Trees are be used to store data in hierarchical format. In computers, path of any file is like Local Disk C/Krishna/Teja/Y.exe which is a hierarchical format. Due to this, data access becomes easy. Unlike arrays, there is no limit for size. Trees are useful in heap sort, one of the best sorting techniques.

There are many other data structures like graphs, tables etc,. A graph can be defined as a collection of vertices and edges. A graph may or may not be directed (edges with arrows). A directed graph in which traversal from a point through the edges leads to the same point is called a cyclic graph. A table can be defined as a collection of rows and columns. A unique index can be given for every element and the element can be accessed using that index. To generate index, a hash function is used and this procedure is called hashing. Hashing is a very popular technique in the field of network security. Graphs are applied in shortest path problems, construction of minimum spanning trees etc,. All the classic data structures are useful in sorting techniques and search techniques in one way or the other.


Comments

No responses found. Be the first to comment...


  • Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
  • No HTML formatting and links to other web sites are allowed.
  • This is a strictly moderated site. Absolutely no spam allowed.
  • Name:
    Email: