Stack and Queue (reading code)

Question

I want to solve this problem WITHOUT putting it into an Java IDE. (If it came up in an exam I would not be able to solve it.)

So what I know so far.

I know that stack is referred to as LIFO and queue is referred to as FIFO. But I do not understand what this code would pop out (Or if I'm correct).

 public static void main (String[] args) {
    Queue<String> q = new Queue<String> ();
    q.enqueue ("one");
    q.enqueue ("two");
    q.enqueue ("four");
    q.enqueue ("six");
    String s = "";
    int i = 0;
    while (!q.isEmpty()) {
      s = s + q.dequeue().substring(i);
      i++; 
    }
    StdOut.print (s);
  }

Since it is a queue it would be FIFO and the substring would cause the output to be: onewour? Since s.substring() for six would be (3) so no value would be present.

And lastly I found two problems in a Princeton CS class but do not know how the answer came to be

Suppose that a client performs an intermixed sequence of (queue) enqueue and dequeue operations. The enqueue operations put the integers 0 through 9 in order onto the queue; the dequeue operations print out the return value. Which of the following sequence(s) could not occur?

(a)  0 1 2 3 4 5 6 7 8 9

(b)  4 6 8 7 5 3 2 9 0 1 

(c)  2 5 6 7 4 8 9 3 1 0

(d)  4 3 2 1 0 5 6 7 8 9

Answer: (b), (c), and (d).

Suppose that an intermixed sequence of (stack) push and pop operations are performed. The pushes push the integers 0 through 9 in order; the pops print out the return value. Which of the following sequence(s) could not occur?

(a)  4 3 2 1 0 9 8 7 6 5

(b)  4 6 8 7 5 3 2 9 0 1

(c)  2 5 6 7 4 8 9 3 1 0

(d)  4 3 2 1 0 5 6 7 8 9

(e)  1 2 3 4 5 6 9 8 7 0

(f)  0 4 6 5 3 8 1 7 2 9

(g)  1 4 7 9 8 6 5 3 0 2

(h)  2 1 4 3 6 5 8 7 9 0

Answer: (b), (f), and (g).

peter.petrov · Accepted Answer · 2014-04-25 22:05:45Z

3

question 3)

Look at b)

4 6 8 7 5 3 2 9 0 1

When it popped and printed 9, it means all push operations were finished at that point
(due to the ordering of pushes 0,1,...,9). OK, now it is reading 9. Then it is reading 0,
this means it is reading the very first number which was ever pushed to the stack.
Then there's no way it could pop and print 1 because it already popped the last
possible number (there's no way 1 was pushed after 0 was popped because as said
all push operations were done at the time 9 was popped).

You need to use similar logical observations to see why f) and g) are not possible too.
When reading all these sequences of popped numbers just try to imagine the sequence
of pushes which happens in between the pops (i.e. what was pushed since the last pop).
Whichever sequence of pops leads to a hiccup: that one is not possible i.e. could not occur.

question 2) This one is trivial, anything but a) is not possible. Right?
Because as with a queue in a shop, the customers are served in the
order in which they came to the cash desk. Otherwise it would not be a queue.

question 1) You will learn more if you actually type this one, compile it and run it.

edited Apr 25, 2014 at 22:05

answered Apr 25, 2014 at 22:00

peter.petrov

39.6k23 gold badges114 silver badges193 bronze badges

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

4 Comments

user3395013 Over a year ago

For Queue: there is only one way then, right? but I'm still having trouble for the Stack. Does order not matter because the order is push pop push...etc right?

peter.petrov Over a year ago

No, the order is not push, pop, push, pop, etc. It could be: push, push, push, push, pop, push, push, pop, pop, etc. Meaning, it is not an alternating sequence of pushes and pops. As the problem text says: it is an "intermixed sequence of (stack) push and pop operations".

peter.petrov Over a year ago

For the queue, the sequence of enqueue, dequeue operations is also not alternating, it is still intermixed. But due to the nature of this structure, the sequence of dequeues can only give one result: 0, 1, 2, 3, ..., 9.

user3395013 Over a year ago

Ahh thank you for a thorough explanation, it helped me a lot!

user3427320 · Accepted Answer · 2016-09-25 16:38:04Z

Ques 3) "Intermixed push and pop operations of integers 0 through 9 in order" I think this means the order is maintained starting anywhere from 0 and 9. Rotation is allowed. Ie: for example: pushing 8,9,0,1,2 in the same order, is valid. Otherwise the option 'e' is not possible. The option 'g' here is also possible. Here are the operations you have to perform to get the sequence given in option 'g'

Stack r = new Stack(); 
//Not providing the implementation details of stack here. 
r.push(1);
System.out.print(r.pop());
r.push(2);
r.push(3);
r.push(4);
System.out.print(r.pop());
r.push(5);
r.push(6);
r.push(7);
System.out.print(r.pop());
r.push(8);
r.push(9);
System.out.print(r.pop());
System.out.print(r.pop());
System.out.print(r.pop());
System.out.print(r.pop());
System.out.print(r.pop());
r.push(0);
System.out.print(r.pop());
System.out.print(r.pop());

Only 'b' and 'f' cannot occur. Correct me if I am wrong.

Collectives™ on Stack Overflow

Stack and Queue (reading code)

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related