Queue

Queue with front==-1 and rear==-1

import java.io.*;
class Queue
{
int que[ ];
int size,front,rear;

Queue(int n)
{
size=n;
que = new int[size];
front=-1;
rear=-1;
}

void insert(int x)
{
if(rear == size-1)
System.out.println("Overflow");
else if(front==-1 && rear==-1)
{
front++;
rear++;
que[rear]=x;
}
else
{
rear++;
que[rear]=x;
}
}

int delete()
{
if(front==-1 && rear==-1)
{
System.out.println("Underflow");
return -9999;
}
else if(front==rear)
{
int temp=que[front];
front=-1;
rear=-1;
return temp;
}
else
{
int temp=que[front];
front++;
return temp;
}
}

public void display()

{
if(front==-1 && rear==-1)
System.out.println("Empty queue");

else
{
System.out.println("The queue is…");
for(int i=front;i<=rear;i++)
System.out.print(que[i]+" | ");
}
System.out.println("\n");
}

public static void main()throws IOException

{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter the queue size");
int s=Integer.parseInt(br.readLine());
int t;
Queue obj=new Queue(s);
int k,ch,element;

do
{
System.out.println("1. Add");
System.out.println("2. Remove");
System.out.println("3. Display");
System.out.println("4. Quit");
System.out.println("Enter choice ?");
ch=Integer.parseInt(br.readLine());

switch(ch)
{
case 1:
System.out.println("Enter the new element to be added at rear");
element=Integer.parseInt(br.readLine());
obj.insert(element);
break;

case 2:
t=obj.delete();
if(t!=-9999)
System.out.println("Deleted "+t);
break;

case 3:
obj.display();
break;

case 4:
System.exit(0);
 default:
System.out.println("Wrong choice… Re enter your choice");
}

System.out.println("Press 1 to continue and any other number to

terminate");
k=Integer.parseInt(br.readLine());

} while(k==1);
}
}

Stack
class Stack
{
int st[];
int size;
int top;

Stack(int n)
{
size = n;
st = new int[size];
top = -1;
}

void push(int n)
{
if(top == size-1)
{
System.out.println("OVERFLOW");
}
else
{
top = top + 1;
st[top] = n;
}
}

int pop()
{
if(top == -1)
{
System.out.println("UNDERFLOW");
return -999;
}
else
{
int val = st[top];
top = top - 1;
return val;
}
}

void display()
{
if(top == -1)
{
System.out.println("The stack is empty");
}
else
{
System.out.println("The elements in the stack are : ");
for(int i = top; i>=0; i--)
{
System.out.println(st[i]);
}
}
}

Practice questions of stack

/*A bookshelf is designed to store the books in a stack with LIFO(LastInFirstOut)
operation. Define a class Book with the following specifications:
Classname:Book
Data members/instance variables:
name[ ]:stores the names of the books
point:stores the index of the top most book
max:stores the maximum capacity of the bookshelf
Methods/Member functions:
Book(int cap):constructor to initialise the data members max=cap and point=-1
void tell():displays the name of the book which was last entered in the shelf.If
there is no book left in the shelf,displays the message”SHELF EMPTY”
void add(String v):adds the name of the book to the shelf if possible,otherwise
displays the message”SHELF FULL”
void display():displays all the names of the books available in the shelf
Specify the class Book giving the details of ONLY the functions void tell( ) and void
add(String). Assume that the other functions have been defined.
The main function need not be written.*/
public class Book
{
String name[];
int point,max;
Book(int cap)
{
max=cap;
point=-1;
name=new String[max];
}

void tell()
{
if(point==-1)
System.out.println("SHELF EMPTY");
else
System.out.println(name[point]);
}

void add(String v)
{
if(point==max-1)
 System.out.println("SHELF FULL");
else
name[++point]=v;
}

void display()
{
for(int i=point;i>=0;i--)
{
System.out.println(name[i]);
}
}
}
public class Stack1
{
char cha[];
int size,top;

public Stack1(int mm)

{
size=mm;
top=-1;
cha=new char[size];
}

public void push_char(char v)

{
if(top==size-1)
System.out.println("OVERFLOW");
else
cha[++top]=v;
}

public char pop()

{
if (top ==-1)
{
 System.out.println("UNDERFLOW");
return '$';
}
else
{
char c=cha[top];
top=top-1;
return c;
}
}

public void display()

{

for(int i=top;i>=0;i--)
{
System.out.println(cha[i]);
}
}
}
/*A stack is a linear data structure which enables the user to add and remove
integers from one end only,using the concept of LIFO(LastInFirstOut).An array
containing the marks of 50 students in ascending order is to be pushed into the
stack.
Define a class Array_to_Stack with the following details:

Classname:Array_to_Stack
Data members / instance variables:
m[ ]:to store the marks

st[]:to store the stack elements

cap:maximum capacity of the array and stack
top:to point the index of the top most element of the stack
Methods/Member functions:
Array_to_Stack(int n):parameterized constructor to initialize cap=n and top=-1
void input_marks():to input the marks from user and store it in the array m[ ] in
ascending order and
simultaneously push the marks into the stack st[ ] by invoking the function
pushmarks()
void pushmarks(int v):to push the marks into the stack at top location
if possible,otherwise,display “not possible”
int popmarks():to return marks from the stack if possible,otherwise, return -999
void display():To display the stack elements
Specify the class Array_to_Stack, giving the details of the constructor(int), void
input_marks( ), void pushmarks(int), int popmarks() and void display().
The main function and algorithm need not be written*/
import java.util.Scanner;
public class Array_to_Stack
{
int m[],st[];
int cap,top;

Array_to_Stack(int n)
{
cap=n;
top=-1;
st=new int[cap];
m=new int[cap];
}
void input_marks()
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter "+cap+" elements in ascending order");
for(int i=0;i< cap;i++)
{
m[i]=sc.nextInt();
pushmarks(m[i]);
}
}
void pushmarks(int v)
{
if(top==cap-1)
System.out.println("not possible stack is full");
else
 st[++top]=v;
}

int popmarks()
{
if(top==-1)
{
System.out.println("UNDERFLOW");
return -999;
}
else
{
int temp=st[top];
top=top-1;
return temp;
}
}

void display()
{
for(int i=top;i>=0;i--)
{
System.out.println(st[i]);
}
}
}
/*Register is an entity which can hold a maximum of 100 names. The register
enables the user to add and remove names from the top most end only.
Define a class Register with the following details:
Class name:Register
Data members / instance variables:
stud[ ]:array to store the names of the students
cap:stores the maximum capacity of the array
top: to point the index of the top end
Member functions:
Register (int max):constructor to initialize the data member cap = max, top = -1
and create the string array
void push(String n):to add names in the register at the top location if possible,
otherwise display the message “OVERFLOW”
String pop():removes and returns the names from the top most location of the
register if any, else returns “$”
void display():displays all the names in the register
(a)Specify the class Register giving details of the functions void push(String) and
String pop( ). Assume that the other functions have been defined .
The main function and algorithm need NOT be written .*/
public class Register
{
String stud[];
int cap,top;
Register(int max)
{
cap=max;
top=-1;
stud=new String[cap];
}
void push(String n)
{
if (top==cap-1)
System.out.println("OVERFLOW");
else
stud[++top]=n;
}

String pop()
{
if (top==-1)
{
System.out.println("UNDERFLOW");
return " $$";
}
else
{
String temp=stud[top];
top=top-1;
 return temp;
}
}
}
/*WordPile is an entity which can hold maximum of 20 characters .The restriction
is that a character can be added or removed from one end only.Some of the
members of classes are given below:
Classname:WordPile
Data members/instance variables:
ch[ ]:character array to hold the character elements
capacity:integer variable to store the maximum capacity
top:to point to the index of the top most element
Methods / Member functions:
WordPile( int cap):constructor to initialise the data member capacity=cap , top=-1
and create the WordPile
void pushChar(char v):adds the character to the top of WordPile if
possible,otherwise output a message ”WordPile
is full”
char popChar():returns the deleted character from the top of the WordPile if
possible,otherwise it returns ‘\\’
(a)Specify the class WordPile giving the details of the constructor, void
pushChar(char) and char popChar().
THE MAIN() FUNCTION AND ALGORITHM NEED NOT BE WRITTEN.*/
public class WordPile
{
char ch[]=new char[20];
int capacity,top;
WordPile(int cap)
{
capacity=cap;
top=-1;
ch=new char[capacity];
}

void pushChar(char v)
{
if(top==capacity-1)
 System.out.println("WordPile is full");
else
ch[++top]=v;
}

char popChar()
{
if(top==-1)
return'\\';
else
{
char temp=ch[top];
top=top-1;
return temp;
}
}
}
/*Stack is a kind of data structure which can store elements with the restriction
that an element can be added or removed from the top only.
The details of the class Stack is given below:
Classname:Stack
Data Members/ instance variables:
st[]: the array to hold the names
size:the maximum capacity of the string array
top: the index of the top most element of the stack
ctr: to count the number of elements of the stack

Member functions:

Stack( ): default constructor

Stack(int cap):constructor to initialize size=cap and top=-1
void pushname(String n):to push a name into the stack. If the stack is full, display
the message”OVERFLOW’
String popname( ):removes a name from the top of the stack and returns it. If the
stack is empty,display the message “UNDERFLOW”
void display():Display the elements of the stack.
(a) Specify class Stack giving details of the constructors( ), void pushname (String
n), String popname() and void display().
THE MAIN() FUNCTION AND ALGORITHM NEED NOT BE WRITTEN*/
public class Stack
{
String st[]=new String[50];
int size,top,ctr;

public Stack(int cap)

{
size=cap;
top=-1;
st=new String[size];
}

public void pushname(String n)

{
if(top==size-1)
System.out.println("OVERFLOW");
else
st[++top]=n;

}
public String popname()
{
String temp;
if(top==-1)
{
System.out.println("UNDERFLOW");
return " ";
}
else
{
temp=st[top];
top=top-1;
return temp;
}
 }
public void display()
{

for(int i=top;i>=0;i--)
{
System.out.println(st[i]);
}
}
}

Queue practice questions

/*Define a class Repeat which allows the user to add elements from one end(rear)
and remove elements from the other end(front)only.
The following details of the class Repeat are given below:

Classname:Repeat

Data Members/ instance variables:

st[]:an array to hold a maximum of

100 integer elements

cap:stores the capacity of the array

f:to point the index of the front

r:to point the index of the rear

Member functions:

Repeat(int m):constructor to initialize the data members cap=m, f=0,r=0 and to

create the integer array

void pushvalue(int v):to add integers from the rear index if possible else display
the message(“OVERFLOW”)
int popvalue():to remove and return element from the front.If array is empty then
return -9999

void disp():Displays the elements present in the list

a) Specify.the class Repeat giving details of the constructor(int), member function

void pushvalue(int) , int popvalue() and void disp() . The main() function need not
be written.*/
public class Repeat
{
int st[]=new int[100];
int cap,f,r;

public Repeat(int m)
{
cap=m;
f=0;
r=0;
st=new int[cap];
}

public void pushvalue(int v)

{
if(r==cap)
System.out.println("OVERFLOW");
else
st[r++]=v;
}
public int popvalue()
{

int temp;
if(f==0 && r==0)
{
System.out.println("Underflow");
return -9999;
}
 else if(f==r-1)
{
temp=st[f];
f=0;
r=0;
return temp;
}
else
{
temp =st[f];
f=f+1;
return temp;
}

public void display()

{
if(r==0 && f==0)
System.out.println("Queue is empty");
else
{
for(int i=f;i<r;i++)
{
System.out.println(st[i]+"|");
}
}
}
}
/*Link is an entity which can hold a maximum of 100 integers . Link enables the
user to add elements from the rear end and remove integers from the front end
of the entity. Define a class Link with the following details:
Classname:Link
Data members / instance variables:
lnk[ ]: entity to hold the integer elements
max:stores the maximum capacity of the entity
begin: to point to the index of the front end
end: to point to the index of the rear end
Member functions:
Link(int mm):constructor to initialize,max=mm,begin=0,end=0
void addlink(int v):to add an element from the rear index if possible otherwise
display the message “OUT OF SIZE…”
int dellink():to remove and return an element from the front index , if possible
otherwise display the message “EMPTY…” and return -99
void display():displays the elements of the entity

(a) Specify the class Link giving details of the constructor(int) void addlink(int), int
dellink() and void display().
THE MAIN() FUNCTION AND ALGORITHM NEED NOT BE WRITTEN.*/
public class Link
{
int lnk[]=new int[100];
int max,begin,end;
Link(int mm)
{
max=mm;
begin=0;
end=0;
lnk=new int[max];
}

void addlink(int v)
{
if(end==max-1)
System.out.println("OUT OF SIZE...");
else
lnk[end++]=v;
}
int dellink( )
{
int temp;
if(begin==0 && end==0)
{
System.out.println("EMPTY...");
 return -99;
}
else if(begin==end-1)
{
temp=lnk[begin];
begin=0;
end=0;
return temp;
}
else
{
temp=lnk[begin];
begin=begin+1;
return temp;
}
}
void display()
{
if(begin==0 && end==0)
System.out.println("Empty queue");

else
{
System.out.println("The queue is…");
for(int i=begin;i<end;i++)
{
System.out.print(lnk[i]+" | ");
}
}
}
}
/*Queue is an entity which can hold a maximum of 100 integers . The queue
enables the user to add integers from the rear and remove integers from the
front.
Define a class Queue with the following details:
Class name Queue
Data Members / instance variables:
Que[] :array to hold the integer elements
size : stores the size of the array
front:to point the index of the front
rear:to point the index of the rear
Member functions:
Queue (int mm):constructor to initialize the data size = mm, front = 0, rear = 0
void addele(int v ):to add integer from the rear if possible else display the
message “Overflow”
int delele( ):returns elements from front if present, otherwise displays the
message “Underflow ” and return -9999
void display ( ):displays the array elements
Specify the class Queue giving details of ONLY the functions void addele(int) and
int delele( ). Assume that the other functions have been defined.
The main function and algorithm need NOT be written.*/
public class Queue1
{
int Que[];
int size;
int front,rear;
Queue1(int mm)
{
size=mm;
front=0;
rear=0;
Que=new int[size];
}
void addele(int v)
{
if(rear==size-1)
System.out.println(" Overflow");
else
Que[rear++]=v;
}

int delele()
{ int temp;
if(front==0 && rear==0)
 {
System.out.println("UnderFlow");
return -9999;
}
if(front==rear-1)
{
temp=Que[front];
front=0;
rear=0;
return temp;
}
else
{
temp=Que[front];
front++;
return temp;
}
}
void display()
{
if(front==0 && rear==0)
System.out.println("Empty queue");
else
{
System.out.println("The queue is…");
for(int i=front;i<rear;i++)
{
System.out.println(Que[i]+"|");
}
}
}
}
/*A linear data structure enables the user to add address from rear end and
remove address from front. Define a class Diary with the following details:
Class name:Diary
Data members / instance variables:
Q[ ]:array to store the addresses
size:stores the maximum capacity of the array
start: to point the index of the front end
end:to point the index of the rear end
Member functions:
Diary (int max):constructor to initialize the data member size=max, start=0 and
end=0
void pushadd(String n):to add address in the diary from the rear end if possible,
otherwise display the message “NO
SPACE”
String popadd( ):removes and returns the address from the front end of the diary
if any, else returns “?????”
void show( ):displays all the addresses in the diary
(a)Specify the class Diary giving details of the functions void pushadd(String) and
String popadd( ).Assume that the other functions have been defined.
The main function and algorithm need NOT be written.*/
class Diary
{
String Q[];
int size, start, end;

void pushadd(String n)
{
if(end==size)
System.out.println(" NO SPACE");
else
{
Q[end]=n;
end=end+1;
}
}

String popadd()
{
String temp;
if(start==0 && end==0)
return "?????";
else if(start==end-1)
 {
temp=Q[start];
end=0;
start=0;
return temp;
}
else
{
temp=Q[start];
start++;
return temp;
}
}
void show()
{
if(start==0 && end==0)
System.out.println("Empty queue");
else
{
System.out.println("The queue is…");
for(int i=start;i<end;i++)
{
System.out.print(Q[i]+" | ");
}
}
}
}