Stack ( ADT ) Data Structure

Stack ( ADT ) Data Structure :

* Stack is an ADT woks on the principle Last In First Out (LIFO)
* The last element add to the stack is the first element to be delete.
* Insertion and deletion can be takes place at one end called TOP.
* It looks like one side closed tube.
* The add operation of the stack is called push operation
* The delete operation is called as pop operation.
* Push operation on a full stack causes overflow.
* Pop operation on an empty stack causes underflow.
* SP is a pointer, which is used to access the top element of the stack.
* If you push elements that are added at the top of the stack;
in the same way when we pop the elements, the element at the top of the stack is deleted.,

For example the following Fig give an idea about the stack.

From the above Fig 01 it is clear that the size of the stack is having 4Locations and sp = -1 indicates that the stack is empty and we can push the new elements into the stack. Now the fig 02 shows how the stack grows, when we push an elements 12, 13, 14 into the stack. The fig 03 shows the status of the stack after popping 2 times. Now performing (one more) pop operation one more time on the above stack causes an error known as "stack under flow". The fig 04 shows the content of the stack after pushing 16, 17, 18, and 19. If you try to add one more element stack generate error "stack over flow".

Operations of stack:

There are two operations applied on stack they are 1 push 2. pop. While performing push & pop operations the following test must be conducted on the stack.

1) Stack is empty or not

2) Stack is full or not


Push:

Push operation is used to add new elements in to the stack. At the time of addition first check the stack is full or not. If the stack is full it generates an error message "stack overflow".

Pop:

Pop operation is used to delete elements from the stack. At the time of deletion first check the stack is empty or not. If the stack is empty it generates an error message "stack underflow".

Assumptions:

SP stack pointer whose initial value is -1

max_stack is the size of the queue

stack [] is an array

Element is the elements to be added or deleted

Algorithm to push elements into the stack :-

step :- 1) start

step :- 2) take the element to push into stack

step :- 3) If (Sp == max_stack)

display "The stack is full"

else

{ Sp = Sp+1

stack [Sp] = item
}

step :- 4) return to main program

Algorithm to pop elements from the stack :-

step :- 1) start

step :- 2) if (Sp == -1)

display "stack is empty"

else

{ element = stack[Sp]

Sp = Sp -1
}

step :- 3) return element

Double Linked List

Doubly linked list (or) Double linked list :-

Double Linked list is a fundamental data structure used in computer programming. It consists of a sequence of nodes connected by two pointers in both directions. Each node is having three parts the first part contains the address of previous node and second part contains data and third part contains address of next node. The first and third part is called address fields and the second part is data field. The start pointer always points to the first node of a list. The graphical representation of a node structure shown in the fig

From the above fig the node is containing 2 pointers.

1. Pointer1 is pointing to the previous node.

2. Pointer2 is pointing to the next node.

Doubly linked list can be represented as above fig. in doubly linked list it is possible to traverse both forward & backward directions. It is also called two way lists.

Operation applied on double linked list:

· Inserting an element

· Delete element from the list

· Find the length of the list

· Read the list from left to right or right to left

· Copy a list

· Sort the elements in either ascending or descending order

· Combine 2 or more list

· Search a list

Algorithm to add an element to an existing list:

It is possible to add element to an existing list in thee ways they are add at the front, add at the end of the list, add after a node of the existing list.

Assumtion start always contains the current list start node address.

>next stands for next node address

Add node at the front of a list

Step1. Create a new node

Step2. n->right = start

Step3. start->left = n

Step4. start = n

dd node at the end of a list

Step1. Create a new node

Step2. t = start where t is a temporary variable.

Step3. Traverse the tree until t->right = null

Step4. t->right = n

Step5. n->left = t

Add node after a particular position or a node

Step1. Create a new node.

Step2. t = start where t is a temporary pointer variable

Step3. Read position p from console.

Step4. Traverse the list until the position p

Step5. if not found the position error “no such node exist “: go to step 9

Step6. n->right = p->right

Step7. n->left = p

Step8. p->right = n

Step9. End

Insert node after second (2) node

Single Linked List

Single linked list: -

Single Linked list is a linear data structure. It is used as a fundamental data structure in computer programming. It contains a collection of nodes which are connected by only one pointer in one direction. Each node is having two parts the first part contains the data and second part contains the address of the next node. The first part is called data field or information field and the second part is called as link field or next address field.

The graphical representation of linked list is

Hear the pointer start always points to the first node of a list and the end node is represented by special value called NULL.

Need for linked representation :-

The following problem arises when it is implemented by using arrays

1. Wastage of storage

2. It is not possible to add or delete in the middle of a list with out rearrangement

3. It is not possible to extend the size of a list

To overcome all the above problem by implementing the list using linked representation. In linear lists insertion and deletion operations are inexpensive.

Operations applied on single linked list:

The basic types of operations applied on single linked list are

.

1. Inserting a new element at the given position

2. Delete the element from the given position

3. Find the length of the list

4. Read the list from left to right

5. Retrieve the ith element

6. Copy a list

7. Sort the elements in either ascending or descending order

8. Combine 2 or more list

Algorithm to add an element to an existing list:

It is possible to add an element to an existing list in three ways they are

1) Add at the front

2) Add at end of list

3) Add at position

Assumptions :

1) start is a pointer which always points to the first node of a list

2) ->next stands for next node address

Add at the front of a list

Step1: create a new node

Step2: newnode->next = start

Step3: start = newnode

Add at the end of a list

Step1: create a new node (newnode)

Step2: t = start

Step3: while (t->next != NULL ) t=t->next;

Step3: t->next = newnode

Add after a node of a list (position)

Step1: create a new node (newnode)

Step2: read the position of the node p;

Step3: t = start

Step4: traverse the list up to position as

for (i=1; inext;

Step4: newnode->next = t->next;

Step5: t->next = newnode

Algorithm for delete an element from the list

it is possible to delete an element from an existing list in three ways

· Delete at front

· Delete at end

· Delete at a position

Delete at front:

Step1: t1 = start

Step2: start = start->next

Step3: delete (t1)

Delete at end :

Step1: t = start;

Step2: traverse the list up to n-1 nodes as

For (I =1; I < t =" t-">next

Step3: t1= t->next;

Step4: t->next = t->next->next;

Step5: delete ( t1 )

Delete at position:

Step1: read the position of the deleted node p

Step2: traverse the list upto p-1as

For (i=1;inext;

Step3: t1 = t->next;

Step4: t->next= t->next->next

Step5: delete (t1)


delete a node at position 2

Drawbacks of a single linked list:

It is having only one pointer so that it is possible to traverse in only one way

Linked Lists

Linked list: -

Linked list is a linear data structure that works on a principle Random in Random out (RIRO). Linked list can be defined as Collection of logically adjacent nodes in which logical adjacency is maintained by pointers.

Ex: The days of the week (Sun, Mon, Tue, Wed, Thu, Fri, Sat)

Linked lists can be represented in memory by two ways they are

· Using array method 2. Using pointer method

Array method :

In array method all the elements are stored in the continuous memory locations. It is having following disadvantages they are

1. It follows static memory allocation.

2. It is not possible to extend the size of the array at runtime

3. Due to static memory allocation some memory space will be wasted.

Pointer method :

In pointer method all the data elements are represented using nodes. Each node is having data item and pointer to the next node. The elements in the list need not occupy continuous memory locations. The advantages of this method are

· Efficient memory management is possible, i.e., due to dynamic memory allocation the memory is not wasted

· It is possible to add or delete an element any ware in the list

· It is dynamic in nature

· It is possible to handle a list of any size

· It is possible to extend the size of a list at runtime

Various operations performed on lists: -

The operations performed on lists are.

1. Inserting a new element at the given position.

2. Delete the element from the given position

3. Find the length of the list

4. Read the list from left to right

5. Retrieve the ith element

6. Copy a list

7. Sort the elements in either ascending or descending order

8. Combine 2 or more list

Circular Queue Data Structure

Circular queue :-

In a standard queue data structure rebuffering problem occurs for each dequeue operation. To solve this problem by joining the front and rear ends of a queue to make the queue as a circular queue

Circular queue is a linear data structure. It follows FIFO principle.

• In circular queue the last node is connected back to the first node to make a circle.
• Circular linked list fallow the First In First Out principle
• Elements are added at the rear end and the elements are deleted at front end of the queue
• Both the front and the rear pointers points to the beginning of the array.
• It is also called as “Ring buffer”.
• Items can inserted and deleted from a queue in O(1) time.

Circular Queue can be created in three ways they are

· Using single linked list

· Using double linked list

· Using arrays

Using single linked list:

It is an extension for the basic single linked list. In circular linked list Instead of storing a Null value in the last node of a single linked list, store the address of the 1st node (root) forms a circular linked list. Using circular linked list it is possible to directly traverse to the first node after reaching the last node.

The following figure shows circular single linked list:

Using double linked list

In double linked list the right side pointer points to the next node address or the address of first node and left side pointer points to the previous node address or the address of last node of a list. Hence the above list is known as circular double linked list.

The following figure shows Circular Double linked list :-

Algorithm for creating circular linked list :-

Step 1) start

Step 2) create anode with the following fields to store information and the address of the next node.

Structure node

begin

int info

pointer to structure node called next

end

Step 3) create a class called clist with the member variables of pointer to structure nodes called root, prev, next and the member functions create ( ) to create the circular linked list and display ( ) to display the circular linked list.

Step 4) create an object called ‘C’ of clist type

Step 5) call C. create ( ) member function

Step 6) call C. display ( ) member function

Step 7) stop

Algorithm for create ( ) function:-

Step 1) allocate the memory for newnode

newnode = new (node )

Step 2) newnode->next=newnode. // circular

Step 3) Repeat the steps from 4 to 5 until choice = ‘n’

Step 4) if (root=NULL)

root = prev=newnode // prev is a running pointer which points last node of a list

else

newnode->next = root

prev->next = newnode

prev = newnode

Step 5) Read the choice

Step 6) return

Algorithm for display ( ) function :-

Step 1) start

Step 2) declare a variable of pointer to structure node called temp, assign root to temp

temp = root

Step 3) display temp->info

Step 4) temp = temp->next

Step 5) repeat the steps 6 until temp = root

Step 6) display temp info

Step 7) temp=temp->next

Step 8) return

Using array

In arrays the range of a subscript is 0 to n-1 where n is the maximum size. To make the array as a circular array by making the subscript 0 as the next address of the subscript n-1 by using the formula subscript = (subscript +1) % maximum size. In circular queue the front and rear pointer are updated by using the above formula.

The following figure shows circular array:

Algorithm for Enqueue operation using array

Step 1. start

Step 2. if (front == (rear+1)%max)

Print error “circular queue overflow “

Step 3. else

{ rear = (rear+1)%max

Q[rear] = element;

If (front == -1 ) f = 0;

}

Step 4. stop

Algorithm for Dequeue operation using array

Step 1. start

Step 2. if ((front == rear) && (rear == -1))

Print error “circular queue underflow “

Step 3. else

{ element = Q[front]

If (front == rear) front=rear = -1

Else

Front = (front + 1) % max

}

Step 4. stop

DeQueue Data Structure

DeQueue (or) Deque (Double ended Queue) :-

DeQueue is a data structure in which elements may be added to or deleted from the front or the rear.

Like an ordinary queue, a double-ended queue is a data structure it supports the following operations: enq_front, enq_back, deq_front, deq_back, and empty. Dequeue can be behave like a queue by using only enq_front and deq_front , and behaves like a stack by using only enq_front and deq_rear. .

The DeQueue is represented as follows.

DeQueue can be represented in two ways they are

1) Input restricted DeQueue 2) output restricted DeQueue

The out put restricted Dequeue allows deletions from only one end and input restricted Dequeue allow insertions at only one end.

The DeQueue can be constructed in two ways they are

2) Using array 2. using linked list

Algorithm to add an element into DeQueue :

Assumptions: pointer f,r and initial values are -1,-1

Q[] is an array

max represent the size of a queue

enq_front

step1. Start

step2. Check the queue is full or not as if (f <>

step3. If false update the pointer f as f= f-1

step4. Insert the element at pointer f as Q[f] = element

step5. Stop

enq_back

step1. Start

step2. Check the queue is full or not as if (r == max-1) if yes queue is full

step3. If false update the pointer r as r= r+1

step4. Insert the element at pointer r as Q[r] = element

step5. Stop

Algorithm to delete an element from the DeQueue

deq_front

step1. Start

step2. Check the queue is empty or not as if (f == r) if yes queue is empty

step3. If false update pointer f as f = f+1 and delete element at position f as element = Q[f]

step4. If ( f== r) reset pointer f and r as f=r=-1

step5. Stop

deq_back

step1. Start

step2. Check the queue is empty or not as if (f == r) if yes queue is empty

step3. If false delete element at position r as element = Q[r]

step4. Update pointer r as r = r-1

step5. If (f == r ) reset pointer f and r as f = r= -1

step6. Stop

Priority Queue

Priority queue :

Priority queue is a linear data structure. It is having a list of items in which each item has associated priority. It works on a principle add an element to the queue with an associated priority and remove the element from the queue that has the highest priority. In general different items may have different priorities. In this queue highest or the lowest priority item are inserted in random order. It is possible to delete an element from a priority queue in order of their priorities starting with the highest priority.

The above figure represents 3 separated Queues each following FIFO behavior. Elements in the 2nd Queue are removed only, when the first Queue is empty and elements from the 3rd Queue are removed only when the 2nd Queue is empty and soon.