排序。
在数据结构中,栈是一种可以实现“先进后出”(或者称为“后进先出”)的存储结构。假设给定栈S=(a0,a1,…,an-1),则称a0为栈底,an-1为栈顶。
进栈则按照a0,a1,…,an-1的顺序进行进栈;而出栈的顺序则需要反过来,按照“后存放的先取,先存放的后取”的原则进行,则an-1先退出栈,然后an-2才能够退出,最后再退出a0。
在实际编程中,可以通过两种方式来实现:使用数组的形式来实现栈,这种栈也称为静态栈;使用链表的形式来实现栈,这种栈也称为动态栈。
相对于栈的“先进后出”特性,堆则是一种经过排序的树形数据结构,常用来实现优先队列等。假设有一个集合K={k0,k1,…,kn-1},把它的所有元素按完全二叉树的顺序存放在一个数组中,并且满足:
则称这个集合K为最小堆(或者最大堆)。
由此可见,堆是一种特殊的完全二叉树。其中,节点是从左到右填满的,并且最后一层的树叶都在最左边(即如果一个节点没有左儿子,那么它一定没有右儿子);每个节点的值都小于(或者都大于)其子节点的值。
数据结构中先进后出的是
后进先出原则组织数据的数据结构是:栈。
栈(Stack)是一种后进先出(Last-In-First-Out,LIFO)的数据结构,就像一叠盘子,只能从最上面取盘子,而在往里放盘子时也只能放在最上面。
栈的特点是只能在栈顶进行插入和删除操作,不能在中间或底部进行操作。
队列(Queue)是一种先进先出(First-In-First-Out,FIFO)的数据结构,就像排队买票一样,先到的先买票,后到的只能排在后面等待。
队列的特点是只能在队尾进行插入操作,在队头进行删除操作,不能在中间或队列尾进行操作。
虽然栈和队列在实现细节上有所不同,但它们的基本原理是相似的。
它们都是将元素按照一定顺序存储,并且支持在特定位置进行插入和删除操作,只是插入和删除的顺序不同。
在某些情况下,栈和队列可以相互转化,例如使用两个栈模拟一个队列,或使用两个队列模拟一个栈。
队列的特点:
把线性链表第1个链结点的指针定义为队头指针front,在链表最后的链结点建立指针rear作为队尾指针,并且限定只能在链头进行删除操作。
在链尾进行插入操作,这个线性链表就构成了一个链接队列。另一个与顺序存储结构队列的不同点是,队头指针与队尾指针都是指向实际队头元素与队尾元素所在的链结点。
队列与堆栈一样,是计算机科学领域中比较简单,然而应用又十分广泛的一种基本数据结构,其应用主要体现在以下两个方面:其一是解决计算机的主机与外部设备之间速度不匹配的问题;其二是解决由于多用户引起的系统资源竞争的问题。
还没有评论,来说两句吧...