java - 堆栈和队列(阅读代码)

Question

我想在不将它放入 Java IDE 的情况下解决这个问题。 (如果它出现在考试中，我将无法解决它。)

到目前为止我所知道的。

我知道堆栈被称为后进先出队列称为 FIFO。但我不明白这段代码会弹出什么(或者如果我是正确的)。

 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);
  }

因为它是一个队列，所以它是 FIFO并且子字符串会导致输出为:onewour？由于 6 的 s.substring() 将是 (3)，因此不会存在任何值。

最后我在普林斯顿CS课上发现了两个问题，但不知道答案是怎么来的

假设客户端执行(队列)入队和出队操作的混合序列。入队操作将整数 0 到 9 按顺序放入队列；出队操作打印出返回值。以下哪个序列不会发生？

(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

答案:(b)、(c)和(d)。

假设执行(堆栈)推送和弹出操作的混合序列。压入顺序压入整数 0 到 9； pops 打印出返回值。以下哪个序列不会发生？

(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

答案:(b)、(f) 和 (g)。

Answer 1

问题 3)

看b)

4 6 8 7 5 3 2 9 0 1

当它弹出并打印出9时，表示此时所有的push操作都已完成
(由于推送 0,1,...,9 的顺序)。 OK，现在读9，然后读0，
这意味着它正在读取曾经被压入堆栈的第一个数字。
那么它就不可能弹出并打印 1 因为它已经弹出了最后一个
可能的数字(没有办法在弹出 0 之后插入 1，因为如前所述
所有推送操作都在弹出 9 时完成。

您需要使用类似的逻辑观察来了解为什么 f) 和 g) 也不可能。
当阅读所有这些弹出数字序列时，只需尝试想象序列
在弹出之间发生的推送(即自上次弹出以来推送的内容)。
无论哪种爆破声序列都会导致打嗝:那个是不可能的，即不可能发生。

问题 2)这是微不足道的，除了 a) 之外的任何事情都是不可能的。对吧？
因为就像商店里的队列一样，顾客在
他们来到收银台的顺序。否则就不是队列了。

问题 1)如果您实际键入、编译并运行它，您将学到更多。