Implement a queue data structure given only stacks. What is the time complexity of enqueuing and dequeuing operations?

Question

leonmax · Accepted Answer

for simplicity, here is the pseudo code:

class queue:
    instack
    outstack

    def enqueue(data):
        instack.push(data)

    def dequeue():
        if outstack.size() == 0:
            while instack.size() > 0:
                outstack.push(instack.pop())
        return outstack.pop()

    def size():
        return instack.size()+outstack.size()

time complexity for enqueuing is o(1), time complexity for dequeueing is still o(1) when the out stack is not empty, but is o(n) if the out stack is empty. Totally, there will be n times transfer between two stacks, where n is the number of times dequeue() has been called.

Hussein · Answer

#include

template
struct queue{
	stack s1, s2;
	
	void enqueue(T t) {
		s1.push(t);
	}
	
	void dequeue() {
		fillS2();
		s2.pop();
		fillS1();
	}
	
	T front() {
		fillS2();
		T res = s2.top();
		fillS1();
		
		return res;
	}
	
	int size() {
		return s1.size();
	}
	
private:
	void fillS2() {
		while(!s1.empty()) {
			s2.push(s1.top());
			s1.pop();
		}
	}
	
	void fillS1() {
		while(!s2.empty()) {
			s1.push(s2.top());
			s2.pop();
		}
	}
};

Meta

Pergunta de entrevista da empresa Meta

Respostas da entrevista

Empresas seguidas

Buscas de vagas