c – 什么是堆栈,队列,向量,数组和列表？

这些是您正在谈论的不同数据结构.那我们为什么要使用不同的呢？这样做的原因是不同的数据结构在不同的东西上都很好.

数据结构因其元素之间的关系以及可以对数据结构执行的操作而不同.

对不同数据结构的不同操作可能具有不同的复杂性.复杂性是衡量操作数量随着数据量的增加而增长的程度.

由于您的问题是关于C,我将讨论2个数据结构：向量和列表.
还有一个顺序容器–deque,类似于矢量,主要区别在于在前面插入元素等操作要快得多.

向量

这是一个非常有用的数据结构,它是一个自动增长的数组.由于数组存储在连续的内存块中,因此某些操作的计算密集程度低于其他操作.

让我们看看我们可以对向量进行的操作.

元素访问

由于所有元素都在连续的内存块中,因此获取第n个元素是O(1).

添加到最后

如果我们剩下空间,并且我们知道向量的大小,则此操作为O(1).如果我们没有空间,我们需要分配更多空间,并将所有数据复制到新空间.这是O(n),但很少发生这种情况.

插入和删除

这涉及将插入位置之后的所有元素移动到右侧.这是O(n)

名单

该结构比矢量具有一些优点.元素不在连续的内存块中,这使插入操作更快.

元素访问

要到达第n个元素,您必须从头开始遍历每个列表节点,直到到达第n个元素.这个操作是O(n)

添加到最后

如果我们有一个指向最后一个元素的指针,则此操作为O(1).

插入和删除

这包括找到插入的位置 – O(n)并修复指针.这似乎是相同的复杂性,但是向量必须复制元素,而列表只查找正确的位置.如果我们想在一开始就插入一个元素,就会看到很大的不同.一个列表,必须看不到任何东西,而一个向量必须移动几乎所有的元素.

堆栈和队列

这些是容器适配器.它们包装上面的容器,实现更强的关系,并添加新的操作.

这两者之间的区别在于堆栈是LIFO – 后进先出,而队列是FIFO – 先进先出.不同的算法使用不同的数据结构,因为可用的操作更快.