how can I implement stack with one queue?
the queue only can enqueue and dequeue

What does your instructor and text book say? Aside from that, what language are you coding with? What have you done so far?

Okay?!? So what have you done so far? Have you made any methods like the push and pop methods?

The pop function generally is just removing the most recently added (push) member of the queue/stack and returning it to the caller.

How to pop from a queue that just supports enqueue/dequeue:

Hint:
You can extract any arbitrary member of a queue,eg nth member, by cycling the queue, ie dequeing and immediately re-enqueing n-1 members, then the next dequeue is the desired member. (If that wasn't the last member then you also need to keep dequeing/re-enquening until all the members have been processed so as to leave the queue in its original order.)

You can use a similar cyclic rotation of the queue to insert new members at the head of the queue instead of the tail, if you prefer.

Edited 1 Year Ago by JamesCherrill

@JamesCherrill
thank you very much for yor hint but my problem is I do not have the size of the queue

 int pop()
{
for(i = 0 ; i < n-1 ; i++){
element = queue.dequeue;
queue.enqueue(element);
}
element = queue.dequeue
return element
}

I mean I do not have n

Oh wow, if you can't query the size of the queue that makes it harder.
Maybe you could keep your own counter of the number of elements in the queue?
Alternatively you could use the second approach (add new items at the front of the queue by adding it at the end and cycling the queue until it reaches the front). In that maybe case you could use a sentinal value, so you would know when you have reached the front while cycling the queue. Something like:

add(item) {
  enqueue sentinal value
  enqueue item
  dequeue entries and re-enque them until you find the sentinel value
  // item is now the first entry in the queue
}

Edited 1 Year Ago by JamesCherrill

This article has been dead for over six months. Start a new discussion instead.