Queue using Two Stacks Discussions |

Sort 64 Discussions, By:

6 months ago+ 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])

9 months ago+ 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())
        }
    }
}

6 months ago+ 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.

6 months ago+ 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;

8 months ago+ 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.

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;
}

Load more conversations