-
Notifications
You must be signed in to change notification settings - Fork 523
/
Copy pathImplement Queue using Linked List.cpp
99 lines (89 loc) · 1.84 KB
/
Implement Queue using Linked List.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/*
Implement Queue using Linked List
=================================
Implement a Queue using Linked List.
A Query Q is of 2 Types
(i) 1 x (a query of this type means pushing 'x' into the queue)
(ii) 2 (a query of this type means to pop an element from the queue and print the poped element)
Example 1:
Input:
Q = 5
Queries = 1 2 1 3 2 1 4 2
Output: 2 3
Explanation: n the first testcase
1 2 the queue will be {2}
1 3 the queue will be {2 3}
2 poped element will be 2 the
queue will be {3}
1 4 the queue will be {3 4}
2 poped element will be 3.
Example 2:
Input:
Q = 4
Queries = 1 2 2 2 1 3
Output: 2 -1
Explanation: In the second testcase
1 2 the queue will be {2}
2 poped element will be {2} then
the queue will be empty.
2 the queue is empty and hence -1
1 3 the queue will be {3}.
Your Task:
Complete the function push() which takes an integer as input parameter and pop() which will remove and return an element(-1 if queue is empty).
Expected Time Complexity: O(1).
Expected Auxiliary Space: O(1).
Constraints:
1 <= Q <= 100
1 <= x <= 100
*/
/* Structure of a node in Queue
struct QueueNode
{
int data;
QueueNode *next;
QueueNode(int a)
{
data = a;
next = NULL;
}
};
And structure of MyQueue
struct MyQueue {
QueueNode *front;
QueueNode *rear;
void push(int);
int pop();
MyQueue() {front = rear = NULL;}
}; */
//Function to push an element into the queue.
void MyQueue::push(int x)
{
QueueNode *nN = new QueueNode(x);
if (!front && !rear)
{
front = nN;
rear = nN;
}
else
{
rear->next = nN;
rear = nN;
}
}
//Function to pop front element from the queue.
int MyQueue ::pop()
{
if (front == NULL)
return -1;
int ans = front->data;
if (front == rear)
{
front = NULL;
rear = NULL;
}
else
{
front = front->next;
}
return ans;
}