Data Structure:
Definition:
The data structure describes the way the data is organized and stored in memory for the convenience of processing.
OR
A data structure refers to an organized way of arrangement of data, related to each other in the memory which allows the program to handle the data in an efficient way. A data structure can be represented as follows:
Data Structure= organized data + allowed operation
OR
A Data Structure is a logical way of organization data that considers not only the items stored, but also their relationship to each other.
For example consider a single dimensional array in C language declared as follows:
int a[5];
In this structure ‘a’ contains 5 integer values. The index subscripting starts from 0 i.e., a[0] and ends with 4, a[4]. The array elements are accessed by their index positions.
OR
A data structure is a logical method of representing data in memory using the simple and complex data types provided by the language.
Types of Data Structure:
Basically, there are two types of data structures.
· Linear data structure
· Non-linear data structure
Fig: Different types of data structures
Linear Data Structures:
In linear data structures, the elements or items are stored sequentially, i.e., the elements are arranged in a sequence one after the other. These are single level data structures, having their elements in a sequence. Since elements are arranged in particular order, they are easy to implement. In linear data structure, data is stored in memory in a linear fashion.
Examples of linear data structure are: Array, Stack, queue and Linked List.
Array:
An array is a fixed size linear data structure. It is a collection of homogeneous (similar type) data elements. It’s elements are stored in computer memory in a linear fashion. An array is a collection of items stored at contiguous memory locations. The elements of an array can be identified by using its index value. The index value of the starting element of an array will be 0. So if we declare an array of size 6, then the index value of the elements in an array will be from 0 to 5.
Array is a static data structure. A static data structure refers to a data structure whose size and memory allocation are fixed at compile time and do not change during the program’s execution. This is in contrast to dynamic data structures, where the size can be adjusted at runtime.
- Array Index: The location of an element in an array has an index, which identifies the element. Array index starts from 0.
- Array element: Items stored in an array is called an element. The elements can be accessed via its index.
Arrays can of following types:
(i) One Dimensional Array
(ii) Two Dimensional Array
One Dimensional Array:
One-dimensional array is also called as single dimension array. In one dimensional array, each element is represented by one subscript. The elements are stored in consecutive memory locations. E.g. A [1], A [2], ….., A [N].
Two Dimensional Array:
The Two Dimensional array is used for representing the elements of the array in the form of the rows and columns
In two dimensional array, each element is represented by two subscripts. Thus a two dimensional m x n array A has m rows and n columns and contains mxn elements. It is also called matrix array because in it the elements form a matrix. E.g. A [2] [3] has 2 rows and 3 columns and 2*3 = 6 elements. Two-dimensional array will be accessed by using the subscript of row and column index.
Row Major Order:
A two-dimensional array can be stored row wise, in which the elements of the first row are stored first, then the elements of the second row and so on.
Column Major Order:
When the elements of the first column are stored first, then the elements of the second column and so on. This process of storing the elements is called column major order.
Applications of Arrays:
1. Arrays are used to implement stack and queue data structures. Both stack and queue are essential data structures used in various applications. Unlike Linked Lists, arrays are easier to implement the stack and queue data structure.
2. Arrays are also used to implement Vectors and Lists.
3. CPU scheduling algorithm can be implemented using an array. Arrays play an important role in maintaining the efficiency of the operating system. In CPU scheduling, we need to maintain a list of all the processes that need to be scheduled; arrays can be a useful data structure to store this list of processes.
4. Trees also use array implementation whenever possible as arrays are easy to handle compared to pointers. Trees, in turn, are used to implement various other types of data structures.
5. Data structures like a Heap, Map and Set use binary search tree and the balanced binary tree. These trees can also be implemented using arrays.
6. Various mathematical problems like matrices can be easily and efficiently solved with the help of an array data structure.
7. All sorting algorithms use arrays at its core.
8. Two dimensional arrays, commonly known as, matrices, are used in image processing.
9. Arrays can be used in speech processing, where every speech signal is an array.
10. Database records are usually implemented as arrays.
Stack:
It is defined as a list in which all the insertions and deletions operations are performed at one end called the TOP of stack. Stack is an ordered collection of items in which insertion or deletion of items could be done, at one end, that is, at the top. A stack is a list with the restriction that new node can be added to a stack and removed from a stack only at the top.
Fig: Representation of a Stack
In stack, the information is processed in LIFO (Last In First Out) way. For example, stack of dishes, stack of folded towels, Pile of books. Stack is a container, which follows LIFO principle.
Stack has two basic operations:
· The insertion operation is known as PUSH. When the element is added into the stack, the operation is called push.
· The deletion operation is known as POP. When the element is deleted from the stack, the operation is called pop.
Application of Stack:
1. Stacks can be used for Evaluation of Arithmetic Expressions.
2. Stacks can be used for Processing Function (Subprogram) Calls
3. Stacks can be used to check parenthesis matching in an expression.
4. Stacks can be used for systematic Memory Management.
5. Stack data structures are used in backtracking problems. In Backtracking, while finding the every possible solution of a problem, we store the solution of a previously calculated problem in Stack and use that solution to solve the upcoming problems.
6. It can also be used to convert one form of expression to another form. For example, converting Infix to Postfix or Infix to Prefix.
7. String reversal is also another application of stack. We push the characters of string one by one into stack and then pop character from stack.
8. Stack is also heavily used for Syntax Parsing by most of the Compilers.
Queue:
It is defined as a list in which all the insertions (addition) and deletions operations are performed at REAR and FRONT respectively. A queue is an ordered collection of items in which all insertions take place at one end, the rear, where as all deletion takes place at other end, the front.
Fig: Representation of a Queue
In queue, the information is processed in FIFO (First In First Out) or FSFS (First Come First Served) way. For example, line of people waiting to purchase tickets. The process of inserting items in queue is called enqueueing and removing items from a queue is called dequeueing.
Examples of a queue around in the real world- A line at a bank or at a bus stop, a line of people waiting to purchase tickets are all familiar example of queues.
There are four types of queues in data structure: