7

老狗啃骨头之数据结构-栈和队列

 2 years ago
source link: http://www.veiking.cn/blog/1013-page.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

老狗啃骨头之数据结构-栈和队列_老狗啃骨头_Veiking百草园-知识点滴,日常分享

栈和队列也是比较常见的数据结构，它们是比较特殊的线性表。相对于数组和链表，栈和队列是一种更具特性的场景应用，栈和队列都可以用数组或链表进行具体的实现。栈和队列都是比较特殊的线性结构，不同但具有典型的模型特点。栈是只有一个出入口，先进后出，后进先出；队列是两头开，一头进一头出，先进先出

  栈和队列也是比较常见的数据结构，它们是比较特殊的线性表。相对于数组和链表，栈和队列是一种更具特性的场景应用，栈和队列都可以用数组或链表进行具体的实现。

  栈是一种特殊的线性表，它只能在表固定的一端进行数据结点的插入和删除。因为只有一个出入口，可以想象一个筒子、罐子，最早进去的都垫在最里边，能拿出来的都是最上层的，所以，我们给栈总结出一个特性：先进后出，后进先出。
  在生活中，其实很多应用场景的原理都是栈，只不过生活太过于具体，很难跟计算机里抽象的栈联系起来，很多容器，比如说吃饭的碗：

  一般来说，吃大米饭，是把大米饭先装进碗里，理想的吃米模型是，装的时候一层一层的装，第一勺肯定是闷在最下边；吃的时候一层一层吃，只能先吃上边，到最后才能吃到下边的。栈就是这种容器的一种结构抽象。

  对于栈，我们需要强调他的特性：先进后出，后进先出！

  队列也是一种特殊的线性表，与栈不同的是，队列在他的两端，有两个口：一端专门负责添加元素，一端专门负责删除元素。
  现实生活中，队列的应用模型也很多，一般像各种管道，比如我们经常喝的这个奶茶，用的这个吸管：

  看到这暗潮汹涌波霸没，当珍珠们纷纷涌入吸管的时候，只能一个接一个，有序的排队挤进管子的一端，另一端被含在嘴里猛吸，这个吸管就是队列。很容易得出结论：相对吸管而言，我们先吸到嘴里的永远是先进入吸管的，所以，我们给队列总结出一个特性：先进先出。

  栈和队列都是比较特殊的线性结构，不同但具有典型的模型特点。栈是只有一个出入口，先进后出，后进先出；队列是两头开，一头进一头出，先进先出。大家可以脑补各种类似现实场景，来加深他们这个概念模型的认识。
  在计算应用上，栈经常用于递归功能的实现；在更高层的计算机应用层面，队列应用会更加普遍，例如消息队列、线程队列等。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK