Queue Using Two Stacks

Preamble

This is a typical challenge where the environment we have to work in is constrained and we have to find a solution under some conditions. Same story when we are not allowed to allocate extra space, or when some basic operation is disabled (e.g. for loop).

Why “constrained” challenges make perfect sense

Although such challenges could seem senseless, they are instead very useful to improve our ability to adapt. In the real life this skill is generally very important. Suppose, for example, our company builds software to view and process data. Our users can create their own analysis tools and post-processing scripts by coding in a custom language (generally called DSL - Domain Specific Language). In this case users cannot use anything but such a custom language. They have to implement their scripts in terms of the available constructs.

Actually, this always applies, even when we code in our favourite fully-fledged programming language. We generally don’t perceive any limitations just because we are very familiar with it. Ability to adapt, that’s the point.

Clearly, another good reason to face with this kind of problems is to challenge ourselves and practice.

Queue using Two Stacks Solutions

The key to solving this problem is to understand that stacks and queues are opposite in terms of their access, and that there is no mechanism by which a single stack alone can implement a queue.

Our solution uses an input stacks and an output stack. The enqueue operation is just a stack push (constant), whereas in the dequeue operation we need to transfer the elements of the input stack into the output. We do transfer only when the output stack is empty.

A common error is to transfer data back to the input stack, this could lead to timeout.

Here is a C++ implementation:

 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


class queue_from_stack
{
public:
  // constant
  void push(int i)
  {
    in.push(i);
  }
  
  // possibly linear (when out is not empty)
  int front() const
  {
    // in -> out logic may be moved out
    if (out.empty())
    {
      while (!in.empty())
      {
        out.push(in.top());
        in.pop();
      }
    }
    return out.top();
  }
  
  // possibly linear (when out is not empty)
  void pop()
  {
    front();
    out.pop();
  }
   
  bool empty() const
  {
    return in.empty() && out.empty();
  }
  
private: 
  mutable std::stack<int> in;
  mutable std::stack<int> out;
};

int main() 
{
    int q; cin >> q;
    int op, arg;
    queue_from_stack queue;
    while (q--)
    {
        cin >> op;
        switch(op)
        {
        case 1:
            cin >> arg;
            queue.push(arg);
            break;
        case 2:
            queue.pop();
            break;
        case 3:
            cout << queue.front() << "\n";
            break;
        }    
    }    
}

In languages like Python you should solve this problem by only using lists, append and pop.

Tradeoffs

In this solution we decided to make pop “expensive” and push “cheap”. We can do the opposite, for example if we know that for our scenario pop is called much more than push.

That’s a typical tradeoff we can play with.

 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


class queue_from_stack
{
public:
    void push(int i)
    {
        // push everything from in to out
        while (!in.empty()) 
        { 
            out.push(in.top()); 
            in.pop(); 
        } 
    
        in.push(x); 
    
        // push everything back to in
        while (!out.empty()) 
        { 
            in.push(out.top()); 
            out.pop(); 
        } 
  }
  
  int front() const
  {
    return in.top();
  }
  
  void pop()
  {
    front();
    in.pop();
  }
   
  bool empty() const
  {
    return in.empty() && out.empty();
  }
  
private: 
  mutable std::stack<int> in;
  mutable std::stack<int> out;
};

constrained stack