队列、栈、链表简要介绍

队列 、栈、链表简要介绍拂晓队列、栈是两种编程中常用的线性数据结构，在某些问题中适时地使用队列或栈可以使问题的思路变得非常简单、清晰，下面分别介绍这两种数据结构。一 队列：队列，就如其名字所表述的意思，就是排队，比如我们在食堂打饭排的队，第一个人在队头买饭，后面的人都在后面排着，第一个人走了，第二个人就变成队的头部，而如果有其他的同学过来打饭，那么他就要成为新的队尾，同时队伍长度也相应变长。如果我们把打饭排的队用一个整型数组aN表示，第一个学生是a1,第i个学生是ai，一开始第一个学生是队头，也就是a1为头，当第一个学生走了之后第二个学生就成了队头，也就是a2变成了头，所以我们可以定义一个变量int head，并将其初值赋成1，当一个学生走了之后就把它加1，这样就实现了一个学生走了之后后面的学生为新的队头，如果现在有m个学生，那么现在的队尾就是am，如果来了下一个学生，那么队尾就要变成am+1,所以可以再定义一个变量int tail，并赋初值0，因为最初是没有学生来买饭的，每当有一个学生到来，就将tail+1，这样就可以表示队伍的尾部又向后移了一位，由于head和tail都是随时变化的，所以想要判断一个队伍是否为空，需要判断head与tail的关系，如果它们相等，说明队首和队尾是同一个人，也就说明队伍里只有一个人，如果这个人走了，那么head要加1，这时队伍里就正好没有人了，这时head和tail的关系为headtail，这样我们就可以判断队伍是否为空了。二 栈：栈表示一种后进先出的数据结构，类似于生活中“一摞”的东西，比如一摞盘子，最先放的在最下面，要最后才能取出，最后放的在最上面，可以直接取出并且每次只能取出最上面的那个，再比如一个乒乓球粗细的小筒，往里面放乒乓球，我们每次可以取出的是我们之前放入的最后一个球，如果同样用一个数组 aN 来表示这些筒中的乒乓球， a1表示第1个乒乓球，a2表示第二个乒乓球， ，用一个变量top来表示最上面的那个球，那么 atop就指向最上面的乒乓球，如果只有一个top，我们就只能找到最上面的乒乓球，这样就符合了栈的要求，这样我们就用一个数组表示了“一摞”乒乓球，也就是一个栈，当一个新的元素到来时，我们就将top加1，并将atop赋为新元素的值，当一个元素失去利用价值后，我们就将top减1，这样就等价于将这个元素从栈中删除了，为了防止意外修改栈中除栈顶以外的元素从而破坏逻辑，我们一般除了top外不使用其他变量去作为下标访问栈。再看一个例子：假设现在咱们的大校长为了知道计算机系学生算法的学习情况，那么他需要去问计算机的院长，计算机的院长大人又要去问院书记，书记又要去问系主任，系主任又要去问导员，最后导员了解了学生算法的学习情况后，才能去把结果汇报给主任大人，主任这里才能把结果反馈给书记同志，书记再反馈给院长，最后院长才能把这个情况告诉校长同志。如果我们将上级给下级下达任务的过程看成这个下级领导入栈的过程，而下级向上级交任务的过程看成一个出栈的过程，就可以完全使用一个栈来模拟了上面的这个过程。在计算机中，这个过程其实就是函数调用的过程，当一个函数调用另一个函数的时候，被调用的函数的参数需要入栈，而当这个被调用函数再调用别的函数的时候，被它调用的函数的参数也要入栈，当一个函数完成它的任务需要返回的时候，在栈中存储的它的参数就出栈，这个栈由系统提供，在我们使用递归函数的时候，如果递归层次太深，可以很容易的就将这个栈给填满，从而造成栈溢出的错误，所以有时我们可以自己分配一个栈，来模拟递归函数的过程，从而避免这样的错误。三 链表：大家都学过数组，在定义数组的时候，系统为我们的数组分配了一块连续的空间，数组中相邻的元素，在内存中它们也是相邻的，可是这样有两个局限，一：是我们需要事先知道我们需要多少个元素的位置，才能定义一个数组，不便于内存的有效利用；二：相邻的两个元素在数组中的位置也必须相邻。如果我们定义一个结构体：struct nodeint param;int next;这里param是我们需要存储的变量值，next作为指向与一个node型变量相邻的下一个变量的位置，比如定义一个node n100，如果n0.next=20，就是说与第0个变量相邻的是第20个变量，而不必须是与它紧挨着的第1个，这样这个结构体数组中的这些结构体变量就形成了一个逻辑上的链，避免了a0的下一个必须是a1的限制，使其使用更加灵活，这样的逻辑上抽象出来的链就叫做链表。使用数组实现逻辑上可以实现一个链表的功能，而且具有速度快、实现简单的优点，但有时链的长度不能确定，如果数组定义的很大，可能就会造成空间浪费，定义小了，又可能会不够用，这时就可以使用指针来实现一个链表，即将指向相邻元素的位置的变量定义成一个指针。struct nodeint param;node* next;我们可以只定义一个node型的指针变量，命名为head并为其分配一个空间，当有了下一个的时候，我们只需要给它的next指针申请一个内存空间，这样就有了第二个，并且可以通过第一个的next找到第二个，它们之间形成了一个逻辑上的链，每一个变量叫做一个节点。节点中的数据分为两类，一种是指向其它节点的指针，在链表中我们将实现这个功能的变量统一称为指针域，而不管它是指针型变量还是整变量，另一种是表示我们需要的数据的变量，我们把这些变量称为数据域。在对链表进行插入元素的操作的时候，我们可以直接使用node* tem=new node（C语言使用(node*)malloc(sizeof(node)）申请一个node型的空间，并通过tem-next=head-next使新分配的node的next指向链表头元素的下一个元素，再将链表头元素的next指向刚刚分配的空间，即head-next=tem这样就在常数的时间内实现了一个元素的插入，而如果使用普通的数组在某个位置实现一个元素的插入，则需要先将其后面的元素分别向后移一个位置，才能将新的元素放在第二个位置上，而且如果是元素很多的结构体数组，这个操作所需要的时间就和结构体的元素个数成正比，而使用链表则只需改变指针，在C和C+中，指针的大小是固定的，与类型无关。同理，当我们要删除一个元素的时候，链表也可以在很短的时间内实现，首先定义一个node*tem=head,然后检查它的下一上元素的数据即tem-next-param是否为要删除的那个，如果不是，就将tem=tem-next，直到找到或者tem-next为null了为止，如果找到了，就再定义一个node*t=tem-next,然后tem-next=t-next; delete t（C语言使用free语句），就实现了一个删除操作。而普通的数组在删除某个元素之后需要将之后的元素分别前移一位。将以上所说的链表操作总结一下，可以大致写出三个函数：/查找与其相邻的下一个节点的关键字值为p的节点node* find(node* head, int p)node* t=head;while(t!=null& t-next-param!=p)t=t-next;return t;/添加一个新的节点void add(node* head, int p)node* t=new node;/C语言使用malloc语句t-param=p;t-next=head-next;head-next=t;/删除关键字值为p的节点void del(node* head, int p)node* t=find(head, p);if(t!=null)node* q=t-next;t-next=q-next;delete q;如果我们将以上所说的三种结构所对应的操作分别写成函数，就实现了数据与操作的分离，因为三种结构都是逻辑思维上抽象出来的结构，而且都有对应的操作，所以我们将一种抽象出来的数据结构与其对应的操作整体叫做一种抽象数据类型，即ADT。四 链表实现的队列和栈：在使用队列和栈的时候，有时也会遇到无法确定队列或栈的大小的问题，这时我们依然可以使用链表来解决这个问题，首先说栈：在栈中我们需要一个变量top，来表示栈顶元素，这里top就是一个node*型的变量，即node型的指针，我们将它的指针域指向它下面的那个元素，即栈顶下面第二个，在新元素入栈的时候，只需要分配一个node型的空间，并将其指针域指向top，再将top的值赋为新分配的空间的地址。将其写成函数：（假设该栈存储的是整型变量）void push(node*& top, int p )node* t=new node;t-param=p;t-next=top;top=t;这里我们使用了&表示引用型的参数，为的是在函数中改变top的值，使其依然指向栈顶。在将栈顶元素弹出的时候，只需要将栈顶元素指向下一个，然后将原来栈顶的空间释放void top(node*&top)node*t=top;top=top-next;delete t;这样我们就实现了用链表来实现一个栈，在定义一个栈的时候，只是一句简单的node*top=NULL; 就可以了。再说一下链表队列的实现:队列需要两个变量，一个表示头，一个表示尾，即node*head, node*tail，最初将它们都初始化成null，当有新的元素进队时，就分配空间并将tail的nex指向后面的元素然后将新队尾的指针赋给tail，当一个元素出队的时候，就将head指向其后面的元素并释放head原来所在的空间，下面两个是队列的主要操作：/将一个新的元素p压入队列void push(node*& head, node*& t