Data Structure

2010-08-19T22:22:00.000-07:00

-:Array:-

Definition:-

An array is simply a number of memory locations, each of which can store an item of data of the same data type and which are all referenced through the same variable name.

How to declare an array in C?

The general form of declaring a simple (one dimensional) array is

array_type variable_name[array_size];

in your C/C++ program you can declare an array like

int Age[10];

Here array_type declares base type of array which is the type of each element in array. In our example array_type is int and its name is Age. Size of the array is defined by array_size i.e. 10. We can access array elements by index, and first item in array is at index 0. First element of array is called lower bound(lb) and its always 0. Highest element in array is called upper bound(ub).If lb is the smallest index called the lower bound and ub is the largest index called upper bound,then size of array is given by:-
Size of Array= ub-lb+1

-:Stack:-

Stack:-

Stack is finite sequence of same type defined by the two end of referred to as top and bottom. Where bottom is fixed, and all stack operations are done at top end. In a stack, the element deleted from the set is most recently inserted; the stack implements a last-in-first-out or LIFO policy.

Stack ADT:-

Stack S is finite sequence of same type and all operations are carried out at one end called top.

Operations on Stack

1. Push(item x, Stack S) ! Stack S0 ; Insert an item x into top of the stack and returns new stack S0 with top pointing to the x.

2. Pop(Stack S) ! Stack S0 ; Delete the item x pointed by the the top of the stack and returns new stack S0 with top is pointing to the item next down to the deleted item.

3. isEmpty(Stack S) ! TRUE/FALSE; Returns TRUE when S is empty else FALSE.

4. isFull(Stack S) ! TRUE/FALSE; Returns TRUE when S is Full else FALSE

4. Top(Stack S) ! Returns top item;

Representation of A Stack Using Array:-

To implement a stack we need a variable, called top that holds the index of the top element of the stack and an array to hold the elements of the stack. For example the size of Stack is 20 (MAXSTK=20) and stack holds integers type values.

It may be developed using following code:-

#define MAXSTK=20;

typedef struct

{

int top;

int elements[MAXSTK];

} stack;

We have defined our own data type named stack, which is structure and whose first element top will be used as an index to the top elements, and an array elements of size MAXSTK whose elements are of integer type, to holds the elements of the stack.

If top=0 or top=NULL then stack is empty (means there is no item in STACK) and in this case we can not traverse or delete item form stack. If we try to do something (delete or traverse) then this case known as Underflow.

If top=MAXSTK then stack is full (means there is no space for new item in STACK) and in this case we can not insert item in stack. If we try to insert item in Stack then this case known as Overflow.

Figure:---------------

Representation of A Stack Using Linked List:-

A stack represented using a linked list is also known as linked stack. The array-based representation of stack suffers from following limitation.

Ø Size of the stack must be known in advance.

Ø We may come across situation when an attempt to push an element causes overflow, it is always possible to push an element onto stack.

Therefore, representing stack as an array prohibits the growth of stack beyond the finite number elements. The linked list representation allows a stack to grow to a limit of the computer’s memory.

Following Code helps to develop Stack using linked list:-

typedef struct nodetype

{

int info’

struct nodeType *next;

} stack;

We have defined our own data type named stack, which is a self-referential structure and whose first element info holds the elements of the stack and the second element next holds the address of the elements under it in the stack.

Eg.

Figure:---------------

Applications of Stack:-

A) Parenthesis matching

The dynamic structure stack can be used checking for balanced parenthesis in an expression. For example expression given below

(1+(3×5)-(2+((4-2)×8)+100)-22×(2+4))

We can check both left and right parenthesis is balanced or not using stack structure. The following pseudo-code explains how it can be done.

Check parenthesis (expression)

Step:1. while (not end of expression)

Step:2. for each character in expression

if(character = ’(’ ) then

push(’(’,s)

if(character=’)’) then

pop(s)

[End of Step 2 For loop]

[End of while loop]

Step:3. Exit or Return

Algorithm above works as for every open parenthesis push them into the stack and closing parenthesis pop from the stack. Finally the empty stack shows the parenthesis balanced expression.

b) Polish Notation:-

A notation system for digital-computer or calculator logic in which there are no parenthetical expressions and each operator is a binary or unary operator in the sense that it operates on not more than two operands. Also known as Lukasiewicz notation; parenthesis-free notation. The version of this notation in which operators precede the operands with which they are associated. Also known as prefix notation.

Infix Expression :Any expression in the standard form like "2*3-4/5" is an Infix(Inorder) expression.
Postfix Expression :The Postfix(Postorder) form of the above expression is "23*45/-".

Infix to Postfix Conversion :In normal algebra we use the infix notation like a+b*c. The corresponding postfix notation is abc*+. The algorithm for the conversion is as follows :

Scan the Infix string from left to right.
Initialize an empty stack.
If the scanned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty Push the character to stack.

If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack (topStack). If topStack has higher precedence over the scanned character Pop the stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.

Repeat this step till all the characters are scanned.

(After all characters are scanned, we have to add any character that the stack may have to the Postfix string.) If stack is not empty add topStack to Postfix string and Pop the stack. Repeat this step as long as stack is not empty.
Return the Postfix string.

Queue

A queue is an ordered list in which all insertions take place at one end, the rear, while all deletions take place at the other end, the front.

Representation of A Queue Using Array:-

To implement a queue we need two variables, called front and rear, that holds the index of the first and last element of the queue and an array to hold the elements of the queue. For example the size of Queue is 20 (MAXQ=20) and queue holds integers type values.

It may be developed using following code:-

#define MAXQ=20;

typedef struct

{

int front,rear;

int elements[MAXQ];

} queue;

We have defined our own data type named queue, which is structure and the first element of the structure is front, that will be used to hold the index of first element of the queue.The second element of the structure is rear, and it will be used to hold the last element of the queue.An array named elements of size MAXFQ whose elements are of integer type, to holds the elements of the queue.

Algorithm to insert an element in Queue:-

QInsert(Queue,Front,Rear,N,Item)

Step1.[Check for full ?]

If Front=1 and Rear=N

or If Front= Rear+1 then

WRITE Overflow and return.

Step2.[Calculate the new value of Rear]

If Front = Null then [Queue initially Empty]

Set Front=1 and Rear=1

Else if Rear=N then

Set Rear=1

Else

Set Rear= Rear+1

[End of If Structure]

Step3. Set Queue[Rear]=ITEM

Step4. Return or Exit

Algorithm to Delete element from Queue:-

QDelete(Queue,Front,Rear,N,Item)

Step1.[Check for Null ?]

If Front=NULL then

WRITE Overflow and return.

Step2.[Save Element]

Item=Queue[Front]

Step3.[Calculate the new value of Front]

If Front = Rear then [Queue has only one element]

Set Front=Null and Rear=Null

Else if Front=N then

Set Front=1