printing issue for empty case?
Problem
Submissions
Hints & solutions
Discuss
Implement Queue using Arrays
Easy
0/40
Contributed by
50 upvotes
Asked in company
Problem statement
Queue is a linear data structure that follows the idea of First In First Out. That means insertion and retrieval operations happen at opposite ends.
Implement a simple queue using arrays.
You are given 'query' queries which are either of the 2 types:
1 'e': Enqueue (add) element ‘e’ at the end of the queue.
2: Dequeue (retrieve) the element from the front of the queue. If the queue is empty, return -1.
Input: Queries:
[ 1 2,
1 7,
2,
1 13,
2,
2,
2 ]
Output:
[ 2,
7,
13,
-1 ]
Explanation: After each operation, our queue is equal to the following:
1 2: {2}
1 7: {2, 7}
2: {7} and 2 is printed
1 13: {7, 13}
2: {13} and 7 is printed
2: {} and 13 is printed
2: {} and -1 is printed since the queue is empty.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line contains an integer ‘query’, the number of queries.
The next ‘query’ lines each contain a query.
If the first integer in the line is equal to 1, then it is an enqueue query and is followed by the integer 'e'.
Otherwise, if the first integer is equal to 2, then it is a dequeue query.
Solve the queries and print the appropriate dequeued values.
You need not consider the queries. You are given the structure of the queue. It consists of an array ‘a’ of size 100001 and 2 variables ‘rear’ and ‘front’, storing the index of the rear and the front elements, respectively. Both ‘rear’ and ‘front’ are initially equal to 0.
Implement the enqueue() and the dequeue() functions which add and retrieve the elements from the queue.
Sample Input 1:
7
1 2
1 7
2
1 13
2
2
2
Sample Output 1:
2 7 13 -1
Explanation Of Sample Input 1 :
After each operation, our queue is equal to the following:
1 2: {2}
1 7: {2, 7}
2: {7} and 2 is printed
1 13: {7, 13}
2: {13} and 7 is printed
2: {} and 13 is printed
2: {} and -1 is printed since the queue is empty.
Sample Input 2 :
4
2
2
1 2
1 4
Sample Output 2 :
-1 -1
Explanation Of Sample Input 2 :
After each operation, our queue is equal to the following:
2: {} and -1 is printed since the queue is empty.
2: {} and -1 is printed since the queue is empty.
1 2: {2}
1 4: {2, 4}
Expected time complexity :
Both the enqueue() and dequeue() functions should solve in constant time, that is O(1) time complexity.
Constraints:
1 <= ‘query’ <= 10^5
1 <= ‘e’ <= 10^6
Approaches (1)
Approach 1
Implementation
The elements currently in the queue are defined using the variables ‘rear’ and ‘front’.
When the array ‘a’ is empty, both ‘rear’ and ‘front’ are 0. This means the range of the queue can be defined from index ‘front’ to ‘rear’ - 1 (both inclusive).
This means there is an element in the queue if ‘front’ < ‘rear’. Therefore our queue is empty if ‘front’ >= ‘rear’. In our implementation, ‘front’ should never exceed ‘rear’. So the condition ‘front’ = ‘rear’ is sufficient for checking if the queue is empty.
For enqueue operation, place the element at ‘a[rear]’ and then increase ‘rear’ by 1.
For dequeue operation, check if the queue is empty. If it is not empty, return ‘a[front]’ and increase ‘front’ by 1. Don’t write the increase statement after the return statement, else it will become unreachable. Either store the value to be returned or use postfix increment.
Since the maximum value of ‘query’ is 10 ^ 5, and the given length of ‘a’ is more than 10 ^ 5, we can implement a simple queue. Otherwise, we can also implement a Circular Queue using the array. It has a fixed size, but we can use the entire array.
The steps are as follows:
void enqueue(int ‘e’)
- ‘a[rear]’ = ‘e’
- ‘rear’ = ‘rear’ + 1
int dequeue()
- If ‘front’ = ‘rear’:
- Return -1.
- Return ‘a[front++]’.
Time Complexity
O(1)
The enqueue and dequeue operations take constant time each because we are doing constant operations on ‘a’, ‘front’ or ‘rear’.
Hence the time complexity is O(1).
Space Complexity
O(1).
The enqueue and dequeue operations are taking up constant auxiliary space.
Hence the space complexity is O(1).
Code Solution
(100% EXP penalty)
Implement Queue using Arrays
All tags
Sort by
Interview problems
java solution using concept of linear queue
public class Solution {
class Queue {
int front, rear;
int []arr;
Queue() {
front = 0;
rear = 0;
arr = new int[100001];
}
// Enqueue (add) element 'e' at the end of the queue.
public void enqueue(int e) {
// Write your code here.
if(rear==arr.length-1){
return ;
}
arr[rear]=e;
rear=rear+1;
}
// Dequeue (retrieve) the element from the front of the queue.
public int dequeue() {
// Write your code here.
if(front==rear){
return -1;
}
return arr[front++];
}
}
}
137 views
0 replies
0 upvotes
Interview problems
java solution using concept of circular queue
public class Solution {
class Queue {
int front, rear;
int []arr;
int n;
int count;
Queue() {
front = 0;
rear = 0;
arr = new int[100001];
n=arr.length;
count=0;
}
// Enqueue (add) element 'e' at the end of the queue.
public void enqueue(int e) {
// Write your code here.
if(count==n){
return ;
}
arr[rear%n]=e;
rear++;
count++;
}
// Dequeue (retrieve) the element from the front of the queue.
public int dequeue() {
// Write your code here.
if(count==0){
return -1;
}
int p=arr[front%n];
front++;
count--;
return p;
}
}
}
46 views
0 replies
0 upvotes
Interview problems
C++ Easy solution
class Queue {
int front, rear;
vector<int> arr;
public:
Queue()
{
front = 0;
rear = 0;
arr.resize(100001);
}
// Enqueue (add) element 'e' at the end of the queue.
void enqueue(int e)
{
// Write your code here.
if (rear < arr.size()) {
arr[rear] = e;
rear++;
}
}
// Dequeue (retrieve) the element from the front of the queue.
int dequeue()
{
// Write your code here.
if (front==rear){
return -1;
}
else{
int deqval=arr[front];
front++;
return deqval;
}
}
};
798 views
0 replies
0 upvotes
Interview problems
java solution
public class Solution {
class Queue {
int front, rear;
int []arr;
Queue() {
front = 0;
rear = 0;
arr = new int[100001];
}
// Enqueue (add) element 'e' at the end of the queue.
public void enqueue(int e) {
// Write your code here.
arr[rear]=e;
rear=rear+1;
}
// Dequeue (retrieve) the element from the front of the queue.
public int dequeue() {
// Write your code here.
if(rear==front){
return -1;
}
int k=arr[front];
front=front+1;
return k;
}
}
}
524 views
0 replies
3 upvotes
Interview problems
Cpp solution with tc O(1) and sc O(1)
class Queue {
int front, rear;
vector<int> arr;
public:
Queue()
{
front = 0;
rear = 0;
arr.resize(100001);
}
// Enqueue (add) element 'e' at the end of the queue.
void enqueue(int e)
{
// Write your code here.
arr[rear]=e;
rear=rear+1;
}
// Dequeue (retrieve) the element from the front of the queue.
int dequeue()
{
// Write your code here.;
if(rear==front)
return -1;
else{
return arr[front++];
}
}
};
698 views
0 replies
1 upvote
Interview problems
using java
public void enqueue(int e) {
// Write your code here.
// queue is full
if(rear==arr.length-1){
return;
}
arr[rear]=e;
rear=rear+1;
}
// Dequeue (retrieve) the element from the front of the queue.
public int dequeue() {
// Write your code here.
//when queue is empty
if(rear==0){
return rear -1;
}
//other rest condtions
front=arr[0];
for(int i=0;i<rear;i++){
arr[i]=arr[i+1];
}
rear=rear-1;
return front;
}
}
227 views
0 replies
1 upvote
Interview problems
c++ soln
void enqueue(int e)
{
// Write your code here.
if(rear == arr.size()) return ;
arr[rear% arr.size()]=e;
rear++;
}
// Dequeue (retrieve) the element from the front of the queue.
int dequeue()
{
// Write your code here.
if(front == rear)return -1 ;
int x = arr[front%arr.size()];
front++;
return x;
}
627 views
1 reply
1 upvote
Interview problems
Solution in java
public class Solution {
class Queue {
int front, rear;
int []arr;
int count =0;
Queue() {
front = 0;
rear = 0;
arr = new int[100001];
}
// Enqueue (add) element 'e' at the end of the queue.
public void enqueue(int e) {
// Write your code here.
if(count ==arr.length)
{
return;
}
arr[rear] = e;
rear++;
count++;
}
// Dequeue (retrieve) the element from the front of the queue.
public int dequeue() {
int x ;
// Write your code here.
if(count == 0)
{
return -1;
}
x = arr[front];
front++;
count --;
return x;
}
}
}
149 views
0 replies
0 upvotes
Interview problems
Java Solution || Easy to understand
public class Solution {
class Queue {
int front, rear;
int []arr;
Queue() {
front = 0;
rear = 0;
arr = new int[100001];
}
// Enqueue (add) element 'e' at the end of the queue.
public void enqueue(int e) {
if(rear==arr.length-1){
//System.out.println("queue full");
return;
}
arr[rear]=e;
rear++;
}
// Dequeue (retrieve) the element from the front of the queue.
public int dequeue() {
if(front==rear){
//System.out.println("Queue is empty");
return -1;
}
return arr[front++];
}
}
} 273 views
0 replies
0 upvotes
1
2
3
4
C++ (g++ 5.4)
Console