c++ - 数据结构 : explanation of pop, push, dequeue, enqueue 在这类练习中

Question

我正在尝试更加熟悉这 4 个概念。

所以如果我们有一个数组 {15, 34, 23, 32, 15, 5}

我们有这样的操作

pop();
push(30);
enqueue(40);
dequeue(100);

pop() 只会删除第一个数字，即 15，对吗？ 如果它是 pop(20) 怎么办？

我假设 push(30) 会添加 30 作为最后一个数字。

入队和出队的工作方式是否与弹出和推送相同？

(那么 enqueue(40) 会在行尾添加 40 吗？dequeue(100) 会做什么？)

Answer 1

pop() would just remove the first number, which is 15, right ? what if it was pop(20) ?

我认为如果将操作与特定数据结构相关联，您会更容易理解这些概念。

例如，push(item) 和 pop() 等操作适用于堆栈，而enqueue( item) 和 dequeue() 用于队列，它们都具有特定且定义明确的行为。

堆栈仅适用于顶部的项目，例如一堆煎饼、纸张或任何其他彼此叠加的项目集合。

这意味着您的 {15, 34, 23, 32, 15, 5} 数组可以这样查看:

| 15 |   <--- top
| 34 |
| 23 |
| 32 |
| 15 |
|  5 |
+----+

在这里，pop 会简单地删除顶部的元素，然后让 top 指向紧靠其下方的元素(即 34)。显然，使用 push(8) 会在堆栈顶部添加一个新元素(即 8)，因此它现在看起来像这样:

|  8 |   <--- top
| 34 |
| 23 |
| 32 |
| 15 |
|  5 |
+----+

由于堆栈的定义行为，像 pop(item) 这样的操作没有意义:它不再将自己限制在顶部的项目堆栈。

I'm assuming push(30) would add 30 as the last number.

这是不正确的，或者至少是模棱两可的:您认为“最后”元素在哪里？ “最后”对你来说意味着什么？这里的问题是像“第一个”和“最后一个”这样的术语暗示了顺序，这是队列的意思(见后文)。然而，堆栈在这个意义上并不是有序的集合，因此在堆栈上下文中谈论第一个/最后一个元素没有多大意义。

在pushing 和poping 等堆栈操作方面，您应该始终谈论顶部 或底部 的堆栈。

Do enqueue and dequeue work the same as pop and push?

没有。 enqueue 和dequeue 等操作适用于称为队列 的不同数据结构。队列在行为方式和支持的操作方面与堆栈不同。

例如，堆栈总是在顶部添加或删除元素，而队列总是在后面添加(即入队)项目收集和移除(即 dequeue)前面的元素，按照先进先出 (FIFO) 的顺序。

 +-- front
 v
+--+----+----+----+----+---+
15 | 34 | 23 | 32 | 15 | 5 | 
+--+----+----+----+----+---+
                         ^
                         +-- back

如果您将队列的行为想象成商店中的一条线，那么关联结构的正确行为会更容易。每次您在商店排队时，您都在排队。

Then would enqueue(40) add 40 at the back of the line?

正确。队列现在看起来像这样:

 +-- front
 v
+--+----+----+----+----+---+----+
15 | 34 | 23 | 32 | 15 | 5 | 40 |
+--+----+----+----+----+---+----+
                              ^
                              +-- back

What would dequeue(100) do?

这类似于我用 pop 描述的问题:它没有意义，因为 dequeue 意味着总是删除元素在前面。因此，队列只支持 dequeue() 并且它会自动删除“行”前面的任何内容:

 +-- front
 v
+--+----+----+----+----+---+
34 | 23 | 32 | 15 | 5 | 40 |
+--+----+----+----+----+---+
                         ^
                         +-- back