- Queue using Two Stacks
- Discussions

# Queue using Two Stacks

# Queue using Two Stacks

+ 2 comments import sys queue = [] for _ in range(int(input().strip())): q = input() if q[0] == "1": queue.append(int(q.split(" ")[1])) if q[0] == "2": queue.pop(0) if q[0] == "3": print(queue[0])

+ 2 comments Not sure everyone here is understanding the assignment. Here it is in Kotlin:

class Queue2s<T> { val stack1 = Stack<T>() val stack2 = Stack<T>() fun enqueue(value:T) { if (stack2.isEmpty() && stack1.isEmpty()) stack1.push(value) else stack2.push(value) } fun dequeue():T { if (stack1.isEmpty()) moveStack() return stack1.pop() } fun peek():T { if (stack1.isEmpty()) moveStack() return stack1.peek() } fun moveStack() { while (stack2.isNotEmpty()){ stack1.push(stack2.pop()) } } }

+ 1 comment What are the benefits to using two stacks for this as opposed to one? I wrote it with one stack and was able to pass all the tests, but i'm assuming my design is inefficient in some way? Or just not the point of this problem? Just feel like i'm missing something because I didn't expect mine to pass with only one stack, just tried it for fun.

Current complexity with one queue is O(n) complexity for dequeue from popping the first element/shifting the rest, O(1) for both enqueue and print.

+ 0 comments **C++****Enqueue**- if both stack is empty then push s1 otherwise push into s2.**Dequeue**- if s1 is empty, then move all items into s1 from s2's top. Then just pop the s1's top value.**Front Element**- if s1 is empty, then move all items into s1 from s2's top. Then just print the s1's top value.typedef struct { stack<int> s1, s2; void enQueue(int x) { if (s1.empty() && s2.empty()) { s1.push(x); } else { s2.push(x); } } void deQueue() { if (s1.empty()) { while (!s2.empty()) { s1.push(s2.top()); s2.pop(); } } s1.pop(); } void frontEle() { if (s1.empty()) { while (!s2.empty()) { s1.push(s2.top()); s2.pop(); } } cout << s1.top() << "\n"; } } Queue;

+ 1 comment C++

This was a great learning experience and I want to share it with you.

First of all this is an exercise and in practice it is slow as it is O(1) for enqueue and O(n) for dequeuing. A more optimal solution would be to use the linked list data structure.

Second of all please watch this video as it helped me wrap my mind around the core concept: https://www.youtube.com/watch?v=AN0axYeLue0. All rights reserved to the creator.

Thirdly, have fun with it and try to go through my solution step by step. It is by no means the best implementation but it passes the tests in a decent amount of time.

Good luck with your learning!

#include <bits/stdc++.h> using namespace std; template <typename T> class Queue{ private: stack<T> s1; stack<T> s2; public: bool isEmpty(){ return s1.empty() && s2.empty(); } int size(){ return s1.size() + s2.size(); } void enqueue(T x){ s1.push(x); } void dequeue(){ if(s2.empty()) { while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } } s2.pop(); } T front(){ if(s2.empty()) { while (!s1.empty()) { s2.push(s1.top()); s1.pop(); } } return s2.top(); } }; int main(){ int q, type, x; cin >> q; Queue<int> queue; for(int i=0; i<q; ++i){ cin >> type; switch(type){ case 1: cin >> x; queue.enqueue(x); break; case 2: queue.dequeue(); break; case 3: cout << queue.front() << "\n"; break; default: continue; } } return 0; }

Sort 64 Discussions, By:

Please Login in order to post a comment