STACK AND
QUEUE
IN
JAVA
WHAT ?
● What is a stack?
● Introduction
● Internal storage structure
● Methods and some coding examples
● What is queue?
● Discussion about methods
● Common operations of queue(insert,delete)
● Examples of queue
WHY ?
● To know about the LIFO principle and how internally stack functions.
● There are some tricky interview related programming questions, which
can be solved on basis of this concept.
● To know the principles of queue, with knowing queue you can pass the
assessment as 30% of questions come from queue, interviewer also ask
questions on queue, to solve basic problems in queue as per the latest
engineering approach.
HOW ?
● IDE used : Netbeans/Eclipse
● Language used : Java
● Assignment : 3 questions
● Assessment : 30 questions and 45 minutes
STACK
WHAT IS STACK ?
● Java Collection framework provides a Stack class which models and
implements Stack data structure.
● A Stack is a data structure where you add elements to the "top" of the
stack, and also remove elements from the top again (LIFO).
● In addition to the basic push and pop operations, the class provides
three more functions of empty, search and peek.
● The class can also be referred to as the subclass of Vector.
● The class supports one default constructor Stack() which is used to
create an empty stack.
INTERNAL STORAGE STRUCTURE
The JVM divided the memory into following sections.
1. Heap - The Heap section contains Objects (may also contain reference
variables).
2. Stack - The Stack section of memory contains methods, local variables,
and reference variables.
3. Code - The code section contains your bytecode.
4. Static - The Static section contains Static data/methods.
INTERNAL STORAGE STRUCTURE
● Java Stack memory is used for the execution of a thread.
● They contain method-specific values that are short-lived and references to
other objects in the heap that is getting referred from the method.
● Stack memory is always referenced in LIFO (Last-In-First-Out) order.
● Whenever a method is invoked, a new block is created in the stack
memory for the method to hold local primitive values and reference to other
objects in the method.
● As soon as the method ends, the block becomes unused and becomes
available for the next method.
INTERNAL STORAGE STRUCTURE
EXAMPLE
public class Memory {
public static void main(String[] args) {
int i=1;
Object obj = new Object();
Memory mem = new Memory();
mem.foo(obj);
}
private void foo(Object param) {
String str = param.toString();
System.out.println(str);
}
}
METHODS
Apart from the methods inherited from its parent class Vector, Stack defines the
following methods −
Methods Description
boolean empty() Tests if this stack is empty. Returns true if the stack is empty, and
returns false if the stack contains elements.
Object peek( ) Returns the element on the top of the stack, but does not remove
it.
Object pop( ) Returns the element on the top of the stack, removing it in the
process.
Object push(Object element) Pushes the element onto the stack. Element is also returned.
int search(Object element) Searches for element in the stack. If found, its offset from the top
of the stack is returned. Otherwise, -1 is returned.
CREATING A STACK
● To use a Java Stack you must first create an instance of the Stack class.
Here is an example of creating a Java Stack instance:
Stack stack = new Stack();
CREATING A STACK WITH A GENERIC TYPE
● You can set a generic type on a Stack specifying the type of objects the
Stack instance can contain.
● You specify the stack type when you declare the Stack variable.
Here is an example of creating a Java Stack with a generic type:
Stack<String> stack = new Stack<String>();
● The Stack created above can only contain String instances.
PUSH ELEMENT ON STACK
● Once you have a Java Stack instance, you can push elements to the top of
the Stack.
● You push elements onto a Java Stack using its push() method.
Here is an example of pushing an element (object) onto a Java Stack:
Stack<String> stack = new Stack<String>();
stack.push("1");
● This Java example pushes a Java String with the text 1 onto the Stack.
● The String 1 is then stored at the top of the Stack.
POP ELEMENT FROM STACK
● Once an element has been pushed onto a Java Stack, you can pop that
element from the Stack again.
● You pop an element off a Java Stack using the pop() method.
Here is an example of popping an element off a Stack using the pop() method:
Stack<String> stack = new Stack<String>();
stack.push("1");
String topElement = stack.pop();
● Once an element is popped off a Stack, the element is no longer present
on the Stack.
PEEK AT TOP ELEMENT OF STACK
● The Java Stack class has a method called peek() which enables you to
see what the top element on the Stack is, without popping off the element.
Here is an example of peeking at the top of a Java Stack:
Stack<String> stack = new Stack<String>();
stack.push("1");
String topElement = stack.peek();
● After running this Java example the topElement variable will contain the
String object 1 which was pushed onto the Stack just before peek() was
called.
SEARCH THE STACK
● You can search for an object on the stack to get it's index, using the
search() method.
Here is how you search a Stack for an object:
Stack<String> stack = new Stack<String>();
stack.push("1");
stack.push("2");
stack.push("3")
int index = stack.search("3"); //index = 3
EXAMPLE FOR STACK
import java.util.Stack;
public class Main {
public static void main(String a[]){
Stack<Integer> stack = new Stack<>();
System.out.println("Empty stack : " + stack);
System.out.println("Empty stack : " + stack.isEmpty());
stack.push(1001);
stack.push(1002);
stack.push(1003);
stack.push(1004);
System.out.println("Non-Empty stack : " + stack);
System.out.println("Non-Empty stack: Pop Operation : " + stack.pop());
System.out.println("Non-Empty stack : After Pop Operation : " + stack);
System.out.println("Non-Empty stack : search() Operation : " +
stack.search(1002));
System.out.println("Non-Empty stack : " + stack.isEmpty());
}}
OUTPUT
Empty stack : true
Non-Empty stack : [1001, 1002, 1003, 1004]
Non-Empty stack: Pop Operation : 1004
Non-Empty stack : After Pop Operation : [1001, 1002, 1003]
Non-Empty stack : search() Operation : 2
Non-Empty stack : false
QUEUE
WHAT IS QUEUE ?
• The Queue is the interface is available in java.util package and extends
the Collection interface.
• The queue collection is used to hold the elements about to be processed
and provides various operations like the insertion, removal etc.
• The Queue is used to insert elements at the end of the queue and
removes from the beginning of the queue. It follows FIFO concept.
• All Queues except the Deques supports insertion and removal at the tail
and head of the queue respectively. The Deques support element
insertion and removal at both ends.
10 20 30 40 50 60
METHODS
Methods Description
add() This method is used to add elements at the tail of queue.
peek() This method is used to view the head of queue without removing it.
It returns Null if the queue is empty.
element() This method is similar to peek(). It throws
NoSuchElementException when the queue is empty.
remove() This method removes and returns the head of the queue. It throws
NoSuchElementException when the queue is empty.
poll() This method removes and returns the head of the queue. It returns
null if the queue is empty.
size() This method return the no. of elements in the queue.
WHAT IS BLOCKINGQUEUE ?
● BlockingQueues do not accept null elements. If we perform any null
related operation, it throws NullPointerException.
● BlockingQueues are used to implement Producer/Consumer based
applications.
● BlockingQueues are thread-safe.
OFFER() OPERATION
● The offer() operation is used to insert new element into the queue.
● If it performs insert operation successfully, it returns “true” value.
Otherwise it returns “false” value.
● Let us develop one simple example to demonstrate this functionality.
EXAMPLE
import java.util.concurrent.*;
public class QueueOfferOperation {
public static void main(String[] args) {
BlockingQueue<String> queue = new ArrayBlockingQueue<>(2);
System.out.println(queue.offer("one"));
System.out.println(queue.offer("two"));
System.out.println(queue);
System.out.println(queue.offer("three"));
System.out.println(queue);
}
}
OUTPUT
true
true
[one, two]
false
[one, two]
NOTE : As our queue is limited to two elements, when we try to add third element using BlockingQueue.offer()
operation, it returns “false” value as shown above.
REMOVE() OPERATION
● The remove() operation is used to delete an element from the head of
the queue.
● If it performs delete operation successfully, it returns the head element of
the queue. Otherwise it throws java.util.NoSuchElementException.
● Let us develop one simple example to demonstrate this functionality.
EXAMPLE
import java.util.*;
public class QueueRemoveOperation
{
public static void main(String[] args)
{
Queue<String> queue = new LinkedList<>();
queue.offer("one");
queue.offer("two");
System.out.println(queue);
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
}
}
OUTPUT
[one, two]
one
two
Exception in thread "main" java.util.NoSuchElementException
at java.util.LinkedList.removeFirst(LinkedList.java:270)
at java.util.LinkedList.remove(LinkedList.java:685)
at Main.main(Main.java:12)
NOTE : Queue.remove(element) is used to delete a specified element from the queue. If it performs
delete operation successfully, it returns “true” value. Otherwise it returns “false” value.
POLL() OPERATION
● The poll() operation is used to delete an element from the head of the
queue.
● If it performs delete operation successfully, it returns the head element of
the queue. Otherwise it returns “null” value.
● Let us develop one simple example to demonstrate this functionality.
EXAMPLE
import java.util.*;
public class QueuePollOperation
{
public static void main(String[] args)
{
Queue<String> queue = new LinkedList<>();
queue.offer("one");
queue.offer("two");
System.out.println(queue);
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
}
}
OUTPUT
[one, two]
one
two
null
NOTE : As our queue has only two elements, when we try to call poll() method for third time, it returns null
value as shown above.
PEEK() OPERATION
● The peek() operation is used to retrieve an element from the head of the
queue, without removing it.
● If it performs examine operation successfully, it returns the head element
of the queue. Otherwise it returns null value.
● Let us develop one simple example to demonstrate this functionality.
EXAMPLE
import java.util.*;
public class Main {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();
queue.add("one");
System.out.println(queue.peek());
System.out.println(queue);
queue.clear();
System.out.println(queue.peek());
}
}
OUTPUT
one
[one]
null
NOTE : If we try to call peek() method on empty Queue, it returns null value, but does NOT throw an exception
as shown above.
EXAMPLE
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample{
public static void main(String[] args){
Queue<Integer> q = new LinkedList<>();
for (int i=0; i<5; i++)
q.add(i);
System.out.println("Elements of queue-"+q);
int removedele = q.remove();
System.out.println("removed element-" + removedele);
System.out.println(q);
int head = q.peek();
System.out.println("head of queue-" + head);
int size = q.size();
System.out.println("Size of queue-" + size);
}
}
OUTPUT
Elements of queue-[0, 1, 2, 3, 4]
removed element-0
[1, 2, 3, 4]
head of queue-1
Size of queue-4
THANK YOU
