0

我只是在我的数据结构 C++ 课程中学习有关 Stack 的所有基本知识。但是,它们之间变得有些混乱。谁能告诉我def是什么?arrayStack 和arrayQueue、stackQueue 和它们的区别?而且教科书根本没有真正的帮助。

4

5 回答 5

4
Firstly you need to understand the fundamentals, lets take a ride thorough the basics again.

We begin with stack empty:

-----
stack
Now, let's perform Push(stack, A), giving:

-----
| A |  <-- top
-----
stack
Again, another push operation, Push(stack, B), giving:

-----
| B |  <-- top
-----
| A |
-----
stack

堆栈

堆栈的概念图是这样的:

Now let's remove an item, letter = Pop(stack), giving:

-----              -----
| A |  <-- top     | B |
-----              -----
stack              letter
And finally, one more addition, Push(stack, C), giving:

-----
| C |  <-- top
-----
| A |
-----
stack
You'll notice that the stack enforces a certain order to the use of its contents, i.e., the Last thing In is the First thing Out. Thus,

我们说堆栈强制执行 LIFO 顺序。

Now we can see one of the uses of a stack...To reverse the order of a set of objects.


Like a stack, a queue usually holds things of the same type. We usually draw queues horizontally. Here's a queue of characters with 3

要素:

queue
-------------
| a | b | c |
-------------
  ^       ^
  |       |
front    rear


Queues are useful because they produce a certain order in which the contents of the queue are used. Let's see what order that is by

看着一排字符。现在,特定的 Enter 和 Delete 序列将对该队列执行什么操作:

queue
-------------
| a | b | c |
-------------
  ^       ^
  |       |
front    rear
Now, Enter(queue, 'd')...

queue
-----------------
| a | b | c | d |
-----------------
  ^           ^
  |           |
front        rear
Now, ch = Delete(queue)...

queue           ch
-------------   -----
| b | c | d |   | a |
-------------   -----
  ^       ^
  |       |
front    rear
于 2013-09-25T09:28:43.363 回答
1

堆栈和队列都是随着您添加元素而自然增长的数据结构。

  • 堆栈中,元素被添加(推送)到堆栈的一侧,然后从堆栈的同一侧检索(弹出)。换句话说,您插入的最后一个元素是您可以检索的第一个元素。这种类型的数据结构称为 LIFO(后进先出)。
  • 队列中,元素被添加到队列的后面并从前面检索。换句话说,您插入的第一个元素是您可以检索的第一个元素。这种类型称为 FIFO(先进先出)。

在各种语言中(不是特别是 C++ 或其库),可以通过多种方式实现自然增长的数据结构。一种方法是保留一个简单的内部数组:元素存储在数组中,添加/删除操作负责扩大或缩小该内部数组,而不会打扰您。通常,当一个结构被称为ArraySomething时,它应该意味着这些方面的东西。

于 2013-09-25T09:28:20.867 回答
1

AnArrayStack是基于数组的实习生。

它们之间最重要的区别是,aStack是基于LIFO (Last In First Out)系统的,因此您将元素添加到顶部(push),如果您想从堆栈中取出一个元素(pop),您也可以从顶部取出它。如果添加一些元素:

stack.push(1), stack.push(2), stack.push(3)

然后弹出一个:

stack.pop() //returns 3

AQueue基于FIFO (First In First Out)系统,因此您在队列的“后部”添加元素,然后从队列的“前部”获取元素。这意味着如果您添加三个元素:

queue.add(1), queue.add(2), queue.add(3)

然后想从队列中获取一个元素:

queue.get() //returns 1

ArrayStack、ArrayQueue 的意思是,它们被实现为一个数组。StackQueue 是两者的结合。您可以从正面和背面获取元素。

于 2013-09-25T09:29:37.157 回答
1

数组是一种组织数据(及其存储分配)的方式,而堆栈队列对数据或数据的策略。insertremoveaccess

可以根据自己的需要policies结合不同的数据结构来构建不同的数据结构。organizations

例如:

  • 使用数组堆叠
  • 使用数组排队
  • 使用链表堆叠
  • 使用数组等的树。
于 2013-09-25T09:36:29.193 回答
0

C++ Standard 没有说明您提到的结构(std::stack容器适配器除外)。因此,您必须再次阅读该章。

很可能你也可以把这本书扔掉,开始使用标准容器。

于 2013-09-25T09:27:49.317 回答