Implement stack using queue - the best complexity

Question

I am wondering if there is a way to implement a stack using as many queues as needed that pushes and pops data in O(1). If there is not any O(1) algorithm , what is the best complexity then?

I mean the time taken by the algorithm should not be dependent to n-the size of the stack. It has to be constant — Feri
– Feri, Commented Oct 30, 2014 at 1:27
I don't think so. Why would you want to? Intuitively, I'm inclined to say O(n) would be best case. — RJinman
– RJinman, Commented Oct 30, 2014 at 1:39
Well if you can implement a O(1) stack using an array, you could just as well use an array of 1-element queues, but that would be pointless. Could you define the problem better? Are you permitted to use arrays or variables, or must the solution consist entirely of queues? — RJinman
– RJinman, Commented Oct 30, 2014 at 1:53

Nuclearman · Accepted Answer · 2014-10-31 02:08:29Z

2

If recursively defined queues in queues are allowed then O(1) pushes/pops is possible using the following:

Code:

STACK:
  QUEUE q

PUSH (S, x):
  QUEUE temp
  ENQUEUE(temp, x)
  ENQUEUE(temp, S.q)
  S.q = temp


POP (S):
  ANY x := DEQUEUE(S.q) # Error here if queue is empty
  QUEUE S.q := DEQUEUE(S.q)
  return x

The result is a recursively formed stack.

If [1,2] represents a stack where dequeue([1,2]) would return 1. Then the data structure if 1 then 3 then 6 were pushed onto the stack would look like this:

[6,[3,[1,[]]]]

edited Oct 31, 2014 at 2:08

answered Oct 30, 2014 at 8:22

Nuclearman

5,4042 gold badges21 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Feri Over a year ago

First I thought it's O(1), but then noticed that copying S.q when enqueuing it is still O(n).

Nuclearman Over a year ago

Pass by reference not value there's no need to actually copy it. Modify the code as needed to ensure that the queues are not actually copied. My bad if the code implies that they are.

Feri Over a year ago

Then S.q will contain only x and a reference. And the reference points to nothing more because it points to itself.

Nuclearman Over a year ago

Hmmm, perhaps assign a pointer to the queue then enqueue the pointer instead of the queue. Maybe I shouldn't have copied Rob's pseudocode (or at least I treated it as pseudocode). Not sure offhand how it can be made to work in the language you are using but I know for a fact that it should be possible to make it work somehow. The code above would work in Python for example without modification.

Feri Over a year ago

Oh yes... I was misunderstood! Excellent algorithm. Thank you very much :D

RJinman · Accepted Answer · 2014-10-30 03:04:21Z

1

You can make a stack with linear-time PUSH and constant-time POP.

Given a queue with functions ENQUEUE and DEQUEUE:

STACK:
  QUEUE q


PUSH (S, x):
  r := new QUEUE
  ENQUEUE(r, x)

  while S.q not empty:
    v := DEQUEUE(S.q)
    ENQUEUE(r, v)

  S.q := r


POP (S):
  RETURN DEQUEUE(S.q)

EDIT: Alternative solution that doesn't require temporary queue r:

STACK:
  QUEUE q


PUSH (S, x):
  ENQUEUE(S.q, x)

  n := SIZE(S.q) - 1

  repeat n times:
    v := DEQUEUE(S.q)
    ENQUEUE(S.q, v)


POP (S):
  RETURN DEQUEUE(S.q)

edited Oct 30, 2014 at 3:04

answered Oct 30, 2014 at 2:42

RJinman

6335 silver badges16 bronze badges

1 Comment

Feri Over a year ago

Well.. It's O(n). But I can't imagine anything better! Thank you for answer :)

RJinman · Accepted Answer · 2014-10-30 14:41:38Z

Here is a C++ implementation of a stack with O(1) push and pop functions.

The interface is similar to std::stack:

void push(const T& val);
void pop();
const T& top() const;
bool empty() const;

Here is the full code. I couldn't think of a way of avoiding the messy type-casts.

#include <iostream>
#include <stack>
#include <queue>
#include <stdexcept>


#define ASSERT(x) \
  if (!(x)) { \
    std::cout << "Assertion failed at line " << __LINE__ << "\n"; \
  } \


template <typename T>
class Stack {
  public:
    Stack()
      : m_head(NULL), m_tail(NULL) {}

    void push(const T& val) {
      std::queue<void*>* tail = new std::queue<void*>();
      tail->push(reinterpret_cast<void*>(m_head));
      tail->push(reinterpret_cast<void*>(m_tail));

      m_head = new std::queue<T>();
      m_head->push(val);

      m_tail = tail;
    }

    void pop() {
      if (m_head) {
        delete m_head;

        m_head = reinterpret_cast<std::queue<T>*>(m_tail->front());
        m_tail->pop();

        std::queue<void*>* tail = reinterpret_cast<std::queue<void*>*>(m_tail->front());
        delete m_tail;
        m_tail = tail;
      }
    }

    const T& top() const {
      if (!m_head) {
        throw std::runtime_error("Error retrieving top element; stack empty");
      }

      return m_head->front();
    }

    bool empty() {
      return !m_head;
    }

  private:
    std::queue<T>* m_head;
    std::queue<void*>* m_tail;
};


int main() {
  Stack<int> s;

  s.pop();

  s.push(0);
  ASSERT(s.top() == 0);

  s.push(1);
  ASSERT(s.top() == 1);

  s.push(2);
  ASSERT(s.top() == 2);

  s.push(3);
  ASSERT(s.top() == 3);

  s.pop();
  ASSERT(s.top() == 2)

  s.push(4);
  ASSERT(s.top() == 4);

  s.push(5);
  ASSERT(s.top() == 5);

  s.push(6);
  ASSERT(s.top() == 6);

  s.pop();
  ASSERT(s.top() == 5)

  s.pop();
  ASSERT(s.top() == 4)

  s.push(7);
  ASSERT(s.top() == 7);

  s.pop();
  ASSERT(s.top() == 4)

  s.pop();
  ASSERT(s.top() == 2)

  s.pop();
  ASSERT(s.top() == 1)

  s.pop();
  ASSERT(s.top() == 0)

  s.pop();

  ASSERT(s.empty())

  s.pop();

  int error = false;
  try {
    int x = s.top();
  }
  catch (std::exception&) {
    error = true;
  }

  ASSERT(error == true);

  return 0;
}

+1: Interesting to see it implemented in C++. Dynamic typing certainly makes things like this easier to implement.

Collectives™ on Stack Overflow

Implement stack using queue - the best complexity

3 Answers 3

5 Comments

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related