Module-01

Linked List , Stack , Queue

Data Structures
• Organized ways to store and manipulate data.

• Real-Time Applications
• Databases: Efficient storage and retrieval.
• Operating Systems: Process scheduling.
• Networking: Routing and data packet management.
• Web Development: Session and state management.
• AI/ML: Data preprocessing and model representation.
Arrays
• Collection of elements of same type , identified by index.

❑ Characteristics:
✓ Fixed size.

✓ Random access.

✓ Homogeneous data.

❑ Syntax

• int[] numbers = {1, 2, 3, 4};

[Link](numbers[2]);
• Advantages:
• Fast access.

• Disadvantages:
• Static size.
• Insertion/Deletion is costly.
Linked Lists
• Sequence of nodes, where each node points to the next.
❑ Advantages:
❑ Dynamic size.
❑ Easier insertion/deletion.

❑ Disadvantages:
❑ No random access.
❑ Higher memory usage.
Components of a Linked List

• Node Structure:
• Data: Holds the value.
• Next: Pointer/reference to the next node.

• Head:
• Points to the first node.

• Tail:
• (Optional) Points to the last node.
Node Creation
1. class Node

2. {

3. int data;

4. Node next;

5. Node(int data) {

6. [Link] = data;

7. [Link] = null;

8. }

9. }
Insertion in linked list

[Link] at the Beginning

[Link] a Node after a Given Node in the Linked List

[Link] a Node at the End of Linked List

Insertion in the beginning of the LL
1. void insert(int data) {

2. Node newNode = new Node(data);

3. if (head == null) {

4. head = newNode;

5. }

6. else {

7. [Link]=head;

8. head=newnode;

9. }}
Insertion at the end of the linkedlist
1. void insert(int data) {

2. Node newNode = new Node(data);

3. if (head == null) {

4. head = newNode;

5. } else {

6. Node temp = head;

7. while ([Link] != null) {

8. temp = [Link];

9. }

10. [Link] = newNode;

11. }
Insertion at some position in a linkedlist
9. else {
1. static void InsertatPositon(int value, int pos) {
10. ListNode curr = head;
2. ListNode newnode = new ListNode(value);
11. while (--pos != 0)
3. int len = Length();
12. curr = [Link];
4. if (pos <= len) {
13. [Link] = [Link];
5. if (pos == 0) {
14. [Link] = newnode;
6. [Link] = head;
15. }
7. head = newnode;
16. } else
8. }
17. [Link]("Invalid Positon");

18. }
Displaying Linked List
1. void display() {

2. Node temp = head;

3. while (temp != null) {

4. [Link]([Link] + " -> ");

5. temp = [Link];

6. }

7. [Link]("null");

8. }
Loop Detection
1. public static boolean detectloop()
2. {
3. Node5 slow=head;
4. Node5 fast=head;
5. while(fast!=null && [Link]!=null)
6. {
7. slow=[Link];
8. fast=[Link];
9. if(slow==fast)
[Link] true;
11.}
[Link] false;
13.}
Form Cycle
1. public static boolean formcycle(int a,int b)
2. {
3. int x=1;
4. Node5 p1=head;
5. Node5 p2=head;
6. while([Link]!=a || x!=b)
7. {
8. if([Link]!=a)
9. {
10.p1=[Link];
[Link]([Link]==null)return false;
12.}
[Link](x!=b)
14.{
15.p2=[Link];
16.x++;
17.} }
[Link]=p1;
[Link] true;
20.}
Doubly Linked List
1. class Node {
2. int data;
3. Node next;
4. Node prev;
5. public Node(int data) {
6. [Link] = data;
7. [Link] = null;
8. [Link] = null;
9. }
10. }
11. public void addNode(int data) {

12. Node newNode = new Node(data);

13. if(head == null) {

14. head = tail = newNode;

15. [Link] = null;

16. [Link] = null;

17. }

18. else {

19. [Link] = newNode;

20. [Link] = tail;

21. tail = newNode;

22. [Link] = null;

23. }

24. }
Sort the bitonic DLL
1. static Node sortBitonicDLL(Node head) {
2. if (head == null || [Link] == null) return head;

3. Node last = head;

4. while ([Link] != null) {
5. last = [Link];
6. }

7. Node front = head;

8. Node result = null;
9. Node tail = null;
10. while (front != null && last != null && front != last && [Link] != front) {
11. Node newNode;
12. if ([Link] < [Link]) {
13. newNode = new Node([Link]);
14. front = [Link];
15. } else {
16. newNode = new Node([Link]);
17. last = [Link];
18. }
19. if (result == null) {
20. result = newNode;
21. tail = result;
22. } else {
23. [Link] = newNode;
24. [Link] = tail;
25. tail = [Link];
26. }
27. }
28. while (front != null && front != [Link]) {
29. Node newNode = new Node([Link]);
30. front = [Link];
31. [Link] = newNode;
32. [Link] = tail;
33. tail = [Link];
34. }

35. while (last != null && [Link] != front) {

36. Node newNode = new Node([Link]);
37. last = [Link];
38. [Link] = newNode;
39. [Link] = tail;
40. tail = [Link];
41. }

42. return result;

43. }
Segregate even and odd nodes in a LL
1. public static void segregate()
2. {
3. Node6 even_start=null;
4. Node6 even_end=null;
5. Node6 odd_start=null;
6. Node6 odd_end=null;
7. Node6 curr=head;
8.
9. while(curr!=null)
10. {
11. int ele=curr.d;
12. if(ele%2==0)
13. {
14. if(even_start==null)
15. {
16. even_start=curr;
17. even_end=curr;
18. }
19. else
20. {
21. even_end.next=curr;
22. even_end=even_end.next;
23. }
24. }
25. else
26. {
27. if(odd_start==null)
28. {
29. odd_start=curr;
30. odd_end=curr;
31. }
32. else
33. {
34. odd_end.next=curr;
35. odd_end=odd_end.next;
36. }
37. }
38. curr=[Link];
39. }
40. if(odd_start==null || even_start==null)
41. return;
42. even_end.next=odd_start;
43. odd_end.next=null;
44. head=even_start;
45. }
Merge Sort Principle
• Divide: Split the list into two halves using a mid node. The first half
runs from the head to just before mid, and the second half starts at
mid and runs to the end.

• Recursively Sort: Apply MergeSort recursively on both halves.

• Merge: Merge the two sorted halves into one sorted list and return the
new head node.
Merge Sort for Doubly Linked List

• Input: 10 <-> 8 <-> 4 <-> 2

• Output: 2 <-> 4 <-> 8 <-> 10

• Input: 5 <-> 3 <-> 2

• Output: 2 <-> 3 <-> 5

1. static Node MergeSort(Node head) {
2. if (head == null || [Link] == null) {
3. return head;
4. }

5. Node second = split(head);

6.
7. Node first = MergeSort(head);
8. second = MergeSort(second);

9. return merge(first, second);

10. }
Dividing
1. static Node split(Node head) {
2. Node fast = head,slow = head;
3. while (fast != null && [Link] != null && [Link] != null) {
4. fast = [Link];
5. slow = [Link];
6. }
7. Node temp = [Link];
8. [Link] = null;
9. if (temp != null) {
10. [Link] = null;
11. }
12. return temp;
13. }
 Merging
1. static Node merge(Node first, Node 15. else {
second) { 16. [Link] = merge(first,
2. if (first == null) return second; [Link]);
3. if (second == null) return first; 17. if ([Link] != null) {
18. [Link] = second;
4. if ([Link] < =[Link]) { 19. }
5. [Link] = merge([Link], second); 20. [Link] = null;
6. if ([Link] != null) { 21. return second;
7. [Link] = first; 22. }
8. } 23. }
9. [Link] = null;
10. return first;
11. }
 Stack
• Stack is a linear data structure that follows LIFO (Last In First Out) Principle.
• It means both insertion and deletion operations happen at one end only.
• Basic Operations on Stack:
• In order to make manipulations in a stack, there are certain operations provided to us.
• push() to insert an element into the stack

• pop() to remove an element from the stack

• top() Returns the top element of the stack.

• isEmpty() returns true if stack is empty else false.

• isFull() returns true if the stack is full else false.

Types of Stack

• Fixed Size Stack (using arrays)

• Dynamic Size Stack (using linkedlist)

Stack using arrays
[Link] class Stack_Array {

[Link] int top=-1;

[Link] int maxcap=1000;
[Link] int arr[]=new int[maxcap];

[Link] boolean isfull()

6.{
[Link] top==maxcap-1;
8.}
[Link] boolean isempty()
10.{
[Link] top==-1;
12.}

[Link] void push(int e)

14.{
15. if(isfull())
16. [Link]("can't insert element");
17. else
18. arr[++top]=e;
19.}
[Link] void pop()
21.{
[Link](isempty())
[Link]("can't perform deletion");
[Link]
[Link]--;
26.}
[Link] void top()
28.{
[Link](isempty())
[Link]("No peek element");
[Link]
[Link](arr[top]);
33.}
[Link] static void display()
35.{
[Link](isempty())
[Link]("no elements to display");
[Link]
39.{
[Link]("stack contains:");
[Link](int i=top;i>=0;i--)
42.{
[Link](arr[i]+" ");
44.}
45.}
46. }
[Link] static void main(String[] args) {
[Link] sc=new Scanner([Link]);
[Link] n=[Link]();
[Link](int i=0;i<n;i++)
51.{
[Link] m=[Link]();
[Link](m);
54.}
[Link]();
[Link]();
[Link]();
[Link]();
[Link]();
60.}}
Stack using LinkedList
1. class Node3
2. {
3. int data;
4. Node3 next;
5. Node3(int e)
6. {
7. [Link]=e;
8. [Link]=null;
9. }
10.}
[Link] class StackLL {
[Link] Node3 top;

[Link] static void push(int e)

14.{
15.Node3 newnode=new Node3(e);
[Link](top==null)
[Link]=newnode;
[Link] {
[Link]=top;
[Link]=newnode;
21.}
22.}
[Link] static void pop()
24.{
[Link](top==null)
26.{
[Link](“No elements Stack Empty");
28.}
[Link]
30.{
[Link]=[Link];
32.}
33.}
[Link] static void display()
35.{
36.Node3 temp=top;
[Link](temp!=null)
38.{
[Link]([Link]+" ");
[Link]=[Link];
41.}
42.}
[Link] sc=new Scanner([Link]);
[Link](true)
45.{
[Link] n=[Link]();
47. if(n!=-1)
48. push(n);
49. else
50. break;
51.}
[Link]();
53.}
54.}
Stack Implementation using Collections
1. import [Link];
[Link] class Main{
[Link] static void main(String[] args)
4.{
5. Stack<Integer> stk= new Stack<>();
[Link] result = [Link]();
7. [Link]("Is the stack empty? " + result);
[Link](78);
[Link](113);
[Link](90);
[Link](120);
[Link]("Elements in Stack: " + stk);
[Link] = [Link]();
[Link]("Is the stack empty? " + result);
15.}
16.}
Minimum Stack
• Problem: Design and implement a stack that supports push(),pop(), top() and
retrieving the minimum element in constant time.
•
Implement a Stack class, which supports the following methods in O(1) time
complexity.
•
void push() : Insert element onto the stack.
• void pop() : Remove the top element from the stack.
• int top() : Retrieve the top element in the stack.
• int getmin() : Retrieve the minimum element in the stack.
1. public class Minimum_Stack
2. {

3. Stack<Integer> st;
4. Stack<Integer> mst;

5. Minimum_Stack()
6. {
7. st=new Stack<Integer>();
8. mst=new Stack<Integer>();
9. }
[Link] getmin()
11.{
[Link]([Link]())
[Link]("Stack is Empty");
[Link]
[Link]([Link]());
16.}

[Link] peek()
18.{
[Link]([Link]())
[Link]("Stack is Empty");
[Link]
[Link]([Link]());
23.}
[Link] pop() {

[Link] t=[Link]();

26. if(t==[Link]())

27. [Link]();

28.}
[Link] push(int x)
25.{
[Link]([Link]())
27.{
[Link](x);
[Link](x);
30.}
[Link]
32.{
[Link](x);
[Link](x<=[Link]())
[Link](x);
36.}
37.}
[Link] static void main(String[] args) {
39.Minimum_Stack m=new Minimum_Stack();
[Link] sc=new Scanner([Link]);
[Link] n=[Link]();
[Link](int i=0;i<n;i++)
43.{
[Link] l=[Link]();
[Link](l);
46.}
[Link]();
48.}
49.}
The Celebrity Problem
• Problem: You are given a number n, representing the number of people in a
party.
• A celebrity is defined as somebody who knows no other person but
everybody else knows him.
• Print the index of the celebrity in the party, and there is no celebrity, then
print "none".
• Example:
• Consider a party of 4 people: with the array of strings as:
• 0101
0000
1101
1110
• In this scenario, the person with index 1 is the celebrity as everybody knows
him but he does not know anybody else.
• Hence, the answer will be 1.
Code
1. public class celebrity_problem
2. {
3. static boolean knows(int a,int b,int r[][])
4. {
5. return r[a][b]==1;
6. }
7. static int findcelebrity(int n,int m[][])
8. {
9. Stack<Integer> st=new Stack<>();
10. int c;
11. for(int i=0;i<n;i++)
12. [Link](i);
13. while([Link]()>1)
14. {
15. int a=[Link]();
16. int b=[Link]();
17. if(knows(a,b,m))
18. [Link](b);
19. else
20. [Link](a);
21. }
22.c=[Link]();
[Link](int i=0;i<n;i++)
24.{
[Link]((i!=c) &&( knows(c,i,m) || !knows(i,c,m)))
[Link] -1;
27.}
[Link] c;
29.}
Tower of Hanoi
• Tower of Hanoi is a mathematical puzzle where we have three rods (A, B,
and C) and N disks. Initially, all the disks are stacked in decreasing value of
diameter i.e., the smallest disk is placed on the top and they are on rod A.
The objective of the puzzle is to move the entire stack to another rod (here
considered C), obeying the following simple rules:
1. Only one disk can be moved at a time.

2. Each move consists of taking the upper disk from one of the stacks and
placing it on top of another stack i.e. a disk can only be moved if it is the
uppermost disk on a stack.

3. No disk may be placed on top of a smaller disk

Examples
• Input: 2

• Output: Disk 1 moved from A to B

Disk 2 moved from A to C
Disk 1 moved from B to C

• Input: 3
Output: Disk 1 moved from A to C
Disk 2 moved from A to B
Disk 1 moved from C to B
Disk 3 moved from A to C
Disk 1 moved from B to A
Disk 2 moved from B to C
Disk 1 moved from A to C
Algorithm
• Calculate the total number of moves required i.e. "pow(2, n) - 1" here n is number of
disks.
• 2. If number of disks (i.e. n) is even then interchange destination pole and auxiliary pole.
• 3. for i = 1 to total number of moves:
• if i%3 == 1:
• legal movement of top disk between source pole and destination pole
• if i%3 == 2:
• legal movement top disk between source pole and auxiliary pole
• if i%3 == 0:
• legal movement top disk between auxiliary pole and destination pole
1. public class TowerOfHanoiUsingStack {
2. public static void main(String[] args) {
3. Scanner sc = new Scanner([Link]);

4. [Link]("Enter the number of disks: ");

5. int numOfDisks = [Link]();

6. if (numOfDisks <= 0)
7. [Link]("The number of disks must be greater than
0.");
8. else
9. towerOfHanoi(numOfDisks);
10.
11. }
12. public static void towerOfHanoi(int numOfDisks) {
13. Stack<Integer> source = new Stack<>();
14. Stack<Integer> auxiliary = new Stack<>();
15. Stack<Integer> destination = new Stack<>();

16. char s = 'S', a = 'A', d = 'D';

17. for (int i = numOfDisks; i >= 1; i--) {

18. [Link](i);
19. }

20. int totalMoves = (int) [Link](2, numOfDisks) - 1;

21. if (numOfDisks % 2 == 0) {
22. char temp = d;
23. d = a;
24. a = temp;
25. }
26. for (int i = 1; i <= totalMoves; i++) {
27. if (i % 3 == 1) {
28. moveDisks(source, destination, s, d);
29. } else if (i % 3 == 2) {
30. moveDisks(source, auxiliary, s, a);
31. } else if (i % 3 == 0) {
32. moveDisks(auxiliary, destination, a, d);
33. }
34. }
35. }
36. private static void moveDisks(Stack<Integer> source, Stack<Integer> destination,
char s, char d) {
37. if ([Link]()) {
38. int disk = [Link]();
39. [Link]("Move disk " + disk + " from " + d + " to " + s);
40. [Link](disk);
41. } else if ([Link]()) {
42. int disk = [Link]();
43. [Link]("Move disk " + disk + " from " + s + " to " + d);
44. [Link](disk);
45. }
36. else if ([Link]() > [Link]()) {
37. int disk = [Link]();
38. [Link]("Move disk " + disk + " from " + d + " to " + s);
39. [Link](disk);
40. } else {
41. int disk = [Link]();
42. [Link]("Move disk " + disk + " from " + s + " to " + d);
43. [Link](disk);
44. }
45. }
46. }
Stock Span Problem
• Problem Statement
• The stock span problem is a financial problem where we have a series of N daily
price quotes for a stock and we need to calculate the span of the stock's price for
all N days.

• The stock span problem can be solved efficiently using stack data structure.

• The idea is to use a stack to maintain the prices in monotonically decreasing order.
We will iterate over the price array and for each price we will find the price just
greater than the current price, lying on the left side of the array.
Example
Input:
size = 6
arr[]={97,64,32,11,22,56}

• Step 1: Traversing the given input span for 97 will be 1

• Step 2: 64 is smaller than 97, so span will be 1
• Step 3: 32 is smaller than 64 & 97, so span will be 1
• Step 4: 11 is smaller than 97,64 & 32, so span will be 1
• Step 5: 22 is greater than 11, so the span is 2
• Step 6: 56 is greater than 32,11,22, so the span is 4
Stock Span Problem Code
1. public class StockSpanProblem {
2. public static void main(String[] args) {
3. Scanner sc=new Scanner([Link]);
4. int n=[Link]();
5. int a[]=new int[n];
6. for(int i=0;i<n;i++)
7. a[i]=[Link]();
8. int s[]=new int[n];
9. stockspan(n,a,s);
[Link](s);
11.}
[Link] static void stockspan(int n,int a[],int s[])
13.{
[Link]<Integer> st=new Stack<>();
[Link](0);
16.s[0]=1;
[Link](int i=1;i<n;i++)
18.{
[Link](![Link]()&&a[[Link]()]<=a[i]) {
[Link]();
21.}
22.s[i]=([Link]()?(i+1):[Link]());
[Link](i);
24.}
25.}
[Link] static void printarr(int s[])
27.{
[Link]([Link](s));
29.}
30.}//class closing
Stack Permutations
• You have been given two arrays having an equal number of
elements. You have to find whether one array is the valid stack
permutation of the other. An array is said to be a valid stack
permutation of the other if and only if after applying some push
and pop operations onto the sequence of elements in that
array, will result in the other array.
• Example:

• Input:
• arr1[] = [ 1, 2, 3 ]
• arr2[] = [ 2, 1, 3 ]
•
Output:
• YES
Code
1. public class StackPermutations {
2. public static boolean check(int x[],int y[],int n)
3. {
4. Stack<Integer> s=new Stack<Integer>();
5. int j=0;
6. for(int i=0;i<n;i++)
7. {
8. [Link](x[i]);
9. while(![Link]()&&y[j]==[Link]())
10.{
[Link]();
12.j++;
13.}
14.}
[Link] [Link]();
16.}
[Link] static void main(String[] args) {
[Link] sc=new Scanner([Link]);
[Link] n=[Link]();
[Link] a[]=new int[n];
[Link] b[]=new int[n];
[Link](int i=0;i<n;i++)
23.a[i]=[Link]();
[Link](int j=0;j<n;j++)
25.b[j]=[Link]();
[Link](check(a,b,n))
[Link]("Yes");
[Link]
[Link]("No");
30.}}
Queue
• A Queue Data Structure is a fundamental concept in computer
science used for storing and managing data in a specific order.
• It follows the principle of "First in, First out" (FIFO), where the
first element added to the queue is the first one to be removed.
Queue using Arrays
1. public class Queue_Array {
2. static int maxcap = 1000;
3. static int[] a = new int[maxcap];
4. static int rear = -1, front = -1;

5. public static boolean isempty() {

6. return front == -1;
7. }

8. public static boolean isfull() {

9. return rear == maxcap - 1;
10.}
[Link] static void enqueue(int e) {

[Link] (isfull()) {

[Link]("Queue is full! Can't insert.");

14.} else {

[Link] (front == -1) {

[Link] = 0;

17.}

18.a[++rear] = e;

19.}}
[Link] static void dequeue()
11. {
[Link] (isempty())
13. {
[Link]("Queue is empty! Can't delete.");
15.}
[Link]
17.{
[Link]("Dequeued: " + a[front]);
[Link]++;
[Link] (front > rear) {
[Link] = -1;
[Link] = -1;
23.}}}
[Link] static void display()
25.{
[Link] (isempty()) {
[Link]("No elements to display!");
28.}
[Link]
30.{
[Link]("Queue elements: ");
[Link] (int i = front; i <= rear; i++) {
[Link](a[i] + " ");
34.}
35.}
36.}
[Link] static void main(String[] args) {
[Link] sc = new Scanner([Link]);
[Link]("Enter the number of elements to enqueue: ");
[Link] n = [Link]();
[Link]("Enter the elements:");
[Link] (int i = 0; i < n; i++) {
[Link] m = [Link]();
[Link](m);
45.}
[Link]();
[Link]("Performing two dequeue operations...");
[Link]();
49. display();
50.}}
Queue using LinkedList
1. class Node{
2. int data;
3. Node next;
4. Node(int v)
5. {
6. data=v;
7. next=null;
8. }
9. }
[Link] class Queue_LinkedList {
[Link] Node rear,front;

[Link] static boolean isempty(){

[Link] rear==null;
14.}

[Link] static void enqueue(int ele){

[Link] newnode=new Node(ele);
[Link](rear==null)
18. front=rear=newnode;
[Link]
20.{
21. [Link]=newnode;
22. rear=newnode;
23.}}
[Link] static void dequeue(){
[Link](isempty())
26. [Link]("no elements to delete");
[Link]
28. front=[Link];
29.}

[Link] static void display(){

[Link] temp=front;
[Link](temp!=rear)
33.{
[Link]([Link]+" -> ");
[Link]=[Link];
36.}
[Link]();
38.}
[Link] static void main(String[] args) {
[Link] sc=new Scanner([Link]);
[Link] n=[Link]();
[Link](int i=0;i<n;i++)
43.{
[Link] ele=[Link]();
[Link](ele);
46.}
[Link]();
[Link]();
[Link]();
[Link]();
51.}}
Priority Queue
• A priority queue is an abstract data type that behaves similarly to the normal queue
except that each element has some priority, i.e., the element with the highest
priority would come first in a priority queue.

• The priority of the elements in a priority queue will determine the order in which
elements are removed from the priority queue.

• The priority queue supports only comparable elements, which means that the
elements are either arranged in an ascending or descending order.

• For example, suppose we have some values like 1, 3, 4, 8, 14, 22 inserted in a

priority queue with an ordering imposed on the values is from least to the greatest.
Therefore, the 1 number would be having the highest priority while 22 will be
having the lowest priority.
Characteristics of a Priority queue
• A priority queue is an extension of a queue that contains the following
characteristics:

1. Every element in a priority queue has some priority associated with

it.
2. An element with the higher priority will be deleted before the
deletion of the lesser priority.
3. If two elements in a priority queue have the same priority, they will
be arranged using the FIFO principle.
Priority Queue using DLL
• Priority queue is abstract data type which behave similar to the linear
queue except that each element has priority.

Example:
Hospital Emergency Queue
The patients will be treated according to their medical condition. (i.e: Person
in pain – High priority).
Priority Queue using DLL
Example:
Priority 1 2 3 4 5

Front Rear
Deletion Insertion

The priority of the elements in the priority queue will determine the
order of removal of the data elements.
1 import [Link].*;
2 class Main {
3
4 static class Node {
5 int data;
6
7 int priority;
8 Node next, prev;
9 public Node(int data, int priority) {
10
11 [Link] = data;
12 [Link] = priority;
13
14 }
15 }
16
private static Node head = null;
17
18
19
20
21
22
1 private static void push(int data, int priority) {
2 if (head == null) {
3
4 Node newNode = new Node(data, priority);
5 head = newNode;
6
7 return;
8 }
9 Node node = new Node(data, priority);
10
11 Node temp = head, parent = null;
12 while (temp != null && [Link] >= priority) {
13
14 parent = temp;
15 temp = [Link];
16
}
17
18 if (parent == null) {
19 [Link] = head;
20
21 [Link] = node;
22 head = node; }
1 else if (temp == null) {
2 [Link] = node;
3
4 [Link] = parent;
5 }
6
7 else {
8 [Link] = node;
9 [Link] = parent;
10
11 [Link] = temp;
12 [Link] = node;
13
14 }
15 }
16
private static int peek() {
17
18 if (head != null) {
19 return [Link];
20
21 }
22 return -1; }
1 private static int pop() {
2 if (head != null) {
3
4 int curr = [Link];
5 head = [Link];
6
7 if (head != null)
8 [Link] = null;
9 return curr;
10
11 }
12 return -1;
13
14 }
15 public static void main(String[] args) {
16
Scanner sc=new Scanner([Link]);
17
18 int n=[Link]();
19 for(int i=0;i<n;i++)
20
21 {
22 int data=[Link]();
1 int pri=[Link]();
2 push(data, pri);
3
4 }
5 [Link](peek());
6
7 [Link](pop());
8 [Link](pop());
9 [Link](peek());
10
11 }
12 }
13
14
15
16
17
18
19
20
21
22
Sort without extra space
Problem:

Sort the given queue without using any extra space

10 1 90 107 5
Code
1. import [Link].*;
2. public class Queue_Sort {
3. public static void main (String[] args)
4. {
5. Queue<Integer> q = new LinkedList<Integer>();
6. [Link](3);
7. [Link](1);
8. [Link](4);
9. [Link](2);
10. [Link](5);
11. sortQueue(q);
12. [Link](q);
13. }
14)public static void sortQueue(Queue<Integer> q)
15){
16)for(int i = 1; i <= [Link](); i++)
17){
18)int min_index = minInd(q,[Link]() - i);
19)insertMinToRear(q, min_index);
20)}
21)}
22) public static int minInd(Queue<Integer> list, int sortIndex) {
23) int min_index = -1;
24) int min_value = Integer.MAX_VALUE;
25) int s = [Link]();
26) for (int i = 0; i < s; i++) {
27) int current = [Link]();
28) [Link]();
29) if (current <= min_value && i <= sortIndex) {
30) min_index = i;
31) min_value = current;
32) }
33) [Link](current);
34) }
35) return min_index;
36) }
37)public static void insertMinToRear(Queue<Integer> list,
int min_index)
38){
39)int min_value = 0;
40)int s = [Link]();
41)for (int i = 0; i < s; i++) {
42)int current = [Link]();
43)[Link]();
44)if (i != min_index)
45)[Link](current);
46)else
47)min_value = current;
48)}
49)[Link](min_value);
50)}