Data Structures : Data Structures Stacks & Queues
Stack : Stack Stack is a list in which insertion and deletion takes place only at one end called top.
Stack is LIFO (Last In First Out) structure and can be implemented as an array or linked list Stack of satays Stack of CDs
STACK : STACK Inserting an element in an array is known as PUSH
Deleting an element from an array is known as POP
Pushing new node onto stack : Pushing new node onto stack newNode 1 2 top If(stack is empty)
top = newNode
else
newNode.next = top
top = newNode
Pop the top node : Pop the top node Return to client if(stack is not empty)
temp = top.data
top = top.next
return temp
QUEUE : QUEUE Queue is First In First Out (FIFO) structure and can also be implemented as an array or a linked list
Insertion is done at the end and deletion is done from the front of the queue
Placing new node on queue : Placing new node on queue Placing new node on the queue Boolean put(DataObject newObj) {
if(currNode == maxNode)
return false; //queue is full
else {
if(front==null)
front =temp
rear=temp
return true
rear.next = temp // (1)
rear=temp // (2)
currNode++
return true
}
} front rear
Circular Queue : Circular Queue A Circular Queue is a special type of queue which is very useful
It has a fixed size
Useful for communication between two processes – sender and receiver
Creating an empty queue : Creating an empty queue Rear after front indicates empty queue
The END : The END Thank you for attending this lecture
Soon after this lecture a test will be posted. You are encouraged to try it
Victoria Portelli (tutor)