Week 4: Stack & Queue
1. Stack implementation and STL
Stack is a fundamental data structure which is used to store elements in a linear fashion. Stack follows LIFO (last in, first out) order or approach in which the operations are performed. This means that the element which was added last to the stack will be the first element to be removed from the stack
Today's topics:
Topic 1:
Stack implementation using array.
C++ Program to Implement Stack using array.
- Push - This adds a data value to the top of the stack.
- Pop - This removes the data value on top of the stack.
- Peek - This returns the top data value of the stack.
Code:
#include < bits/stdc++.h>
using namespace std;
class myStack
{
public:
vector v;
void push(int val)
{
v.push_back(val);
}
void pop()
{
v.pop_back();
}
int top()
{
return v.back();
}
int size()
{
return v.size();
}
bool empty()
{
if (v.size() == 0)
return true;
else
return false;
}
};
int main()
{
myStack st;
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
st.push(x);
}
while (st.empty() == false)
{
cout << st.top() << " ";
st.pop();
}
return 0;
}
Topic: 2
Stack using linked list
Assign top and start as the new node. Otherwise, take a new node, add data to it and assign the “previous” pointer of the new node to the “top” node earlier and next as “null”. Further, update the “top” pointer to hold the value of the new node as that will be the top element of the stack now.
Code:
#include < bits/stdc++.h>
using namespace std;
class Node
{
public:
int val;
Node *next;
Node *prev;
Node(int val)
{
this->val = val;
this->next = NULL;
this->prev = NULL;
}
};
class myStack
{
public:
Node *head = NULL;
Node *tail = NULL;
int sz = 0;
void push(int val)
{
sz++;
Node *newNode = new Node(val);
if (head == NULL)
{
head = newNode;
tail = newNode;
return;
}
newNode->prev = tail;
tail->next = newNode;
tail = tail->next;
}
void pop()
{
sz--;
Node *deleteNode = tail;
tail = tail->prev;
if (tail == NULL)
{
head = NULL;
}
else
{
tail->next = NULL;
}
delete deleteNode;
}
int top()
{
return tail->val;
}
int size()
{
return sz;
}
bool empty()
{
if (sz == 0)
return true;
else
return false;
}
};
int main()
{
myStack st;
// st.pop();
// cout << st.top() << endl;
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
st.push(x);
}
while (!st.empty())
{
cout << st.top() << endl;
st.pop();
}
return 0;
}
Topic: 3
Stack using list
Solution:
#include < bits/stdc++.h>
using namespace std;
class myStack
{
public:
list l;
void push(int val)
{
l.push_back(val);
}
void pop()
{
l.pop_back();
}
int top()
{
return l.back();
}
int size()
{
return l.size();
}
bool empty()
{
if (l.size() == 0)
return true;
else
return false;
}
};
int main()
{
myStack st;
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int x;
cin >> x;
st.push(x);
}
while (!st.empty())
{
cout << st.top() << endl;
st.pop();
}
return 0;
}
Probelm: 4
STL stack
Stacks are a type of container adaptors with LIFO(Last In First Out) type of working, where a new element is added at one end (top) and an element is removed from that end only.
Solution:
#include < bits/stdc++.h>
using namespace std;
int main()
{
stack st;
int n;
cin >> n;
// for (int i = 0; i < n; i++)
while (n--)
{
int x;
cin >> x;
st.push(x);
}
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
return 0;
}
Github link here
2. Queue implementation and STL
A queue is an abstract data structure that contains a collection of elements. Queue implements the FIFO mechanism i.e. the element that is inserted first is also deleted first. In other words, the least recently added element is removed first in a queue.
Today's topics:
- Queue using Singly linked list
- Queue using Doubly linked list
- Queue using List
- Queue using STL
- Queue using Stack - Leetcode
- Stack using Queue - Leetcode
Topic 1: Queue using Singly linked list
A queue is a linear data structure that follows the First in, First out principle(FIFO). Queue supports operations like enqueue and dequeue. It can be implemented using an array and linked list.
Solution:
#include < bits/stdc++.h>
using namespace std;
class Node
{
public:
int val;
Node *next;
Node(int val)
{
this->val = val;
this->next = NULL;
}
};
class myQueue
{
public:
Node *head = NULL;
Node *tail = NULL;
int sz = 0;
void push(int val)
{
sz++;
Node *newNode = new Node(val);
if (head == NULL)
{
head = newNode;
tail = newNode;
return;
}
tail->next = newNode;
tail = tail->next;
}
void pop()
{
sz--;
Node *deleteNode = head;
head = head->next;
delete deleteNode;
if (head == NULL)
{
tail = NULL;
}
}
int front()
{
return head->val;
}
int size()
{
return sz;
}
bool empty()
{
if (sz == 0)
return true;
else
return false;
}
};
int main()
{
myQueue q;
int n;
cin >> n;
while (n--)
{
int x;
cin >> x;
q.push(x);
}
while (!q.empty())
{
cout << q.front() << endl;
q.pop();
}
return 0;
}
Topic 2: Queue using Doubly linked list
Using a doubly linked list for implementing a queue provides several advantages. It allows for efficient insertion and removal of elements at both ends of the list, making enqueue and dequeue operations constant time.
Code:
#include < bits/stdc++.h>
using namespace std;
class myQueue
{
public:
list l;
void push(int val)
{
l.push_back(val);
}
void pop()
{
l.pop_front();
}
int front()
{
return l.front();
}
int size()
{
return l.size();
}
bool empty()
{
return l.empty();
}
};
int main()
{
myQueue q;
int n;
cin >> n;
while (n--)
{
int x;
cin >> x;
q.push(x);
}
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
if (!q.empty())
{
cout << q.front();
}
return 0;
}
Topic 3 : Queue using List
Code:
#include < bits/stdc++.h>
using namespace std;
class myQueue
{
public:
list l;
void push(int val)
{
l.push_back(val);
}
void pop()
{
l.pop_front();
}
int front()
{
return l.front();
}
int size()
{
return l.size();
}
bool empty()
{
return l.empty();
}
};
int main()
{
myQueue q;
int n;
cin >> n;
while (n--)
{
int x;
cin >> x;
q.push(x);
}
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
if (!q.empty())
{
cout << q.front();
}
return 0;
}
Topic 4: Queue using STL
Code:
#include < bits/stdc++.h>
using namespace std;
int main()
{
queue q;
int n;
cin >> n;
while (n--)
{
int x;
cin >> x;
q.push(x);
}
cout << q.size() << endl;
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
return 0;
}
Topic 5: Queue using Stack - Leetcode
leetcode link here
Code:
class MyQueue
{
public:
stack st;
MyQueue()
{
}
void push(int x)
{
st.push(x);
}
int pop()
{
stack newSt;
int last;
while (!st.empty())
{
int k = st.top();
st.pop();
if (st.empty())
{
// last element
last = k;
break;
}
newSt.push(k);
}
while (!newSt.empty())
{
st.push(newSt.top());
newSt.pop();
}
return last;
}
int peek()
{
stack newSt;
int last;
while (!st.empty())
{
int k = st.top();
st.pop();
if (st.empty())
{
// last element
last = k;
}
newSt.push(k);
}
while (!newSt.empty())
{
st.push(newSt.top());
newSt.pop();
}
return last;
}
bool empty()
{
return st.empty();
}
};
/**
* Your MyQueue object will be instantiated
and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
Topic 6: Stack using Queue - Leetcode
Leetcode link here
Solution:
class MyStack
{
public:
queue q;
MyStack()
{
}
void push(int x)
{
q.push(x);
}
int pop()
{
queue newQ;
int last;
while (!q.empty())
{
int k = q.front();
q.pop();
if (q.empty())
{
// last element
last = k;
break;
}
newQ.push(k);
}
q = newQ;
return last;
}
int top()
{
queue newQ;
int last;
while (!q.empty())
{
int k = q.front();
q.pop();
if (q.empty())
{
// last element
last = k;
}
newQ.push(k);
}
q = newQ;
return last;
}
bool empty()
{
return q.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
Github link here
Click to the below link and complete the assignment. Don't see the solution before!
Click here to go the assignment
Problem: 1
Problem Statement Welcome to the "Panta Vat" assignment. In this task you just need to print the following lines as it is. Hello, world! I am learning C programming language. ^_^ Programming is fun and challenging. /\/\/\ I want to give my 100% dedication to learn! I will succeed one day. Note: Here you will see 4 spaces in the last line which is a tab, you need to print a tab there. Input Format There is no input Output Format Output the lines. Sample Output 0 Hello, world! I am learning C programming language. ^_^ Programming is fun and challenging. /\/\/\ I want to give my 100% dedication to learn! I will succeed one day.
Solution:
#include< stdio.h>
int main()
{
printf("Hello, world! I am learning C programming
language. ^_^\nProgramming is fun and
challenging. /\\/\\/\\\nI want to give
my 100%% dedication to learn!\tI will
succeed one day.");
return 0;
}
Problem: 2
Problem Statement You will be given two integers A and B. You need to give output their multiplication. Input Format Input will contain A and B Constraints -10^9 <= A,B <= 10^9 Output Format Output the multiplication Sample Input 0 10 50 Sample Output 0 500 Sample Input 1 10000000 10000000 Sample Output 1 100000000000000 Sample Input 2 -100 62 Sample Output 2 -6200
Solution:
#include< stdio.h>
int main()
{
long long a,b;
scanf("%lld %lld",&a,&b);
long long sum = a*b;
printf("%lld", sum);
return 0;
}
Problem: 3
Problem Statement You will be given a non-negative integer N, you need to tell if this number is divisible by 3 or not. If it is divisible by 3 output "YES" otherwise output "NO" without the quotation mark. Input Format Input will contain N. Constraints 0 <= N <= 10^9 Output Format Output "YES" or "NO" without the quotation mark according to the question. Sample Input 0 33 Sample Output 0 YES Sample Input 1 29 Sample Output 1 NO Sample Input 2 0 Sample Output 2 YES
Solution:
#include< stdio.h>
int main()
{
int a;
scanf("%d",&a);
if(a%3==0)
{
printf("YES");
}
else
{
printf("NO");
}
return 0;
}
Problem: 4
Problem Statement
You will be given a non-negative integer
N, you need to print all numbers from 1
to N that are divisible by both 3 and 7.
Input Format
Input will contain N.
Constraints
21 <= N <= 10000
Output Format
Output all numbers from 1 to N that are
divisible by both 3 and 7. Don't forget
to print a new line after every number.
Sample Input 0
30
Sample Output 0
21
Sample Input 1
50
Sample Output 1
21
42
Sample Input 2
100
Sample Output 2
21
42
63
84
Solution:
#include< stdio.h>
int main()
{
int a;
scanf("%d",&a);
for (int i = 1; i <= a; i++)
{
if(i%3==0 && i%7==0)
{
printf("%d\n",i);
}
}
return 0;
}
Problem: 5
Problem Statement Alisa and you have gone out for shopping, and Alisa wants to buy a new pair of shoes for Eid. She has enough money to buy anything. However, Alisa will only buy shoes if you also buy a pair. And you will buy a pair of shoes if you can buy a Punjabi. That means, everything is depending on the Punjabi. You have decided that you will buy a Punjabi only if you have more than 1000 Taka. After purchasing the Punjabi the amount of your money will be reduced by 1000. Suppose you have 1600 taka with you, after buying the Punjabi you will have 600 taka left with you. Then you will only buy shoes if you have 500 Taka or more left with you. That means, if you can't buy your Punjabi you can't buy shoes. Now if I inform you the amount N Taka that your mother will give you, can you tell me what will happen next? If you buy a punjabi print "I will buy Punjabi". If you buy a pair of shoes print "I will buy new shoes" If Alisa buy a pair of shoes print "Alisa will buy new shoes" If no one can buy anything print "Bad luck!" Note: Don't forget to print new line after every line you print. Input Format Input will contain a non-negative integer N. Constraints 1 <= N <= 2^31 Output Format Output the events that will happen as asked in the question. Sample Input 0 1000 Sample Output 0 Bad luck! Sample Input 1 1450 Sample Output 1 I will buy Punjabi Sample Input 2 1500 Sample Output 2 I will buy Punjabi I will buy new shoes Alisa will buy new shoes
Solution:
#include< stdio.h>
int main()
{
int a;
scanf("%d",&a);
if(a<1001)
{
printf("Bad luck!");
}
else if(a>=1500)
{
printf("I will buy Punjabi\nI will buy new shoes\nAlisa will buy new shoes\n");
}
else
{
printf("I will buy Punjabi");
}
return 0;
}
Github link here
message Lorem ipsum dolor sit, amet consectetur adipisicing elit. Nisi enim, ratione impedit doloribus quibusdam quos earum soluta quod?
Lorem ipsum dolor sit amet consectetur adipisicing elit. Ex temporibus velit illum. Aspernatur amet dolorum consectetur hic ipsam ea soluta?