1

I was asked in an interview to implement queue using single stack and I was able to do it, but I was wondering if the same can be achieved by using yield as well?

  • 1
    yield is syntactic sugar, not an algorithmic concept (you can always rewrite an enumeration using yield without it). It would be helpful if you gave an idea on how you solved that problem. I can't quickly think of a way of inversing a stack (which is required for the task) without a second memory structure of the same size. – PMF Dec 13 '17 at 20:23
  • Addition: There's a bunch of answers here (i.e this one: https://stackoverflow.com/questions/69192/how-to-implement-a-queue-using-two-stacks?rq=1 ) giving an explanation on how to implement a queue using two stacks, but with just one? – PMF Dec 13 '17 at 20:27
  • 1
    @PMF usually people who ask this question wait for you to use recursion. Of course you still store popped items in second memory structure with the same size as stack - call stack. – Evk Dec 13 '17 at 20:28
  • @PMF I did using recursion, pop the stack till it has one element left then return it and store that element in some variable, after that push that element back in stack and the last value in the temp variable will have our first entry in Queue –  Dec 13 '17 at 20:35
  • @PrashantJain: Ah, ok. That's even a worser solution than the double stack, because it uses even more memory (in addition to the values themselves also the return addresses) and because the size limit of the runtime stack is much smaller than the size limit of a stack data structure. – PMF Dec 13 '17 at 20:39
  • I had no other option, it has restriction of using only one stack. –  Dec 13 '17 at 20:41

1 Answers1

0

Based on the comments above, I would say no, It is not possible to use a single stack and yield for this.

As the OP stated, he used recursion to inverse the stack (get the bottom of it). So this is basically the same as what is being given as solution in questions asking to implement a queue using two stacks: How to implement a queue using two stacks? because the runtime stack is used as the second stack.

While it is always possible to rewrite a recursive method to use iteration instead (see any books on theoretical computer science), this is just what is forbidden for the solution of this task, because it would require another datastructure of the same size to keep the data. We need to use iteration to be able to use yield.

PMF
  • 14,535
  • 3
  • 23
  • 49
  • Since this is contrieved quiestion, you can always return `IEnumerable` with 1 value inside and just do `yield return something` once. And then recursively call this. – Evk Dec 13 '17 at 20:56
  • Just an interesting side note, something's have to be recursive, check out Ackerman's function. – Dave Dec 13 '17 at 22:09
  • What should I do in this situation if I am asked the same question? I got your point that I will be creating a new stack at run time, but I need to give a satisfactory answer otherwise I will loose my chance of getting job, please advice. –  Dec 13 '17 at 22:10
  • 1
    @Dave: Correct, but you can always replace a recursive function call using a data structure, such as a stack. Algorithmically, it is still a recursion, but technically it is not. – PMF Dec 14 '17 at 14:41
  • @PrashantJain; I would give the answer you did (use recursion), but indicate that it is a bad solution. Even implementing a queue using two stacks is just a theoretical experiment, nothing you would do in the real world. Use the right tools for the job. – PMF Dec 14 '17 at 14:44
  • @PMF: Thank you. –  Dec 14 '17 at 17:49