Java数据结构 |
您所在的位置：网站首页 › 判断结构是什么 › Java数据结构 |
Java数据结构
|
目录 1.什么是栈？ 2.栈的基本功能和结构 3.栈的基本功能详细代码实现 1. 判断栈是否为空 2.获取栈中元素的个数 3.压栈（向栈顶放入元素） 4.出栈（拿出栈顶元素，并得到它的值） 5.获取栈顶元素（未拿出） 6.判断栈中是否包含该元素 1.什么是栈？假如有一天你下课去小店，买了一条曼妥思准备回去上课的时候偷偷吃，你的同桌看见你的嘴巴一直在嚼，这时你小心翼翼的拿出一颗递给他，这时你就完成了一组出栈功能。如下图，右边就像你的曼妥思，你拿给同桌的肯定是从上往下的第一颗，也就是最上面的这颗糖，如果你下课还要给其他同学那你肯定是顺着往下继续给直到吃完为止。
这种只能从一端进行元素的添加和删除的操作受限的线性表，我们就称之为栈。当然这只是简易的单纯从数据结构的说法，我们的计算机内存中还有栈区，如果你想了解更多当然可以去自己了解。这里我只以最快的方式告诉你栈的逻辑结构 PS：栈的实现可以通过顺序表或链表实现，刚开始接触数据结构的同学不要思维定式，看着图里好像元素都靠在一起就像数组就得用顺序表，栈只要求我们只能在一端进行操作，保存数据的方式无论你选顺序表还是链表都是可以的。这里我更推荐使用链表实现，因为能用链表实现肯定也能用顺序表实现，我也以链表来演示。对于顺序表和链表不熟的同学推荐看看我的前三篇文章 1、java数据结构---顺序表 2、java数据结构---单链表 3、 java数据结构---双向链表 2.栈的基本功能和结构 public class Stack implements Iterable { //记录首节点 private Node head; //记录栈中元素个数 private int N; private class Node{ public T item; private Node next; public Node(T item, Node next) { this.item = item; this.next = next; } } public Stack(){ this.head=new Node(null,null); this.N=0; }因为是以链表存储，同样需要一个内部类Node表示结点，栈成员属性有Node头结点head以及一个int类型变量N计算存储元素个数。构造方法中，new出一个stack（栈）时，需要初始化一个值为空（头结点不存储元素），next也为空，因为我们此时栈还是空的。千万别写成this.head=null，这是完全不同的，这样写代表根本没有头结点。 ps：在这我们要注意，因为栈的操作都是在一端，所以为了我们操作方便，我们的头结点是在进行操作的这一端，而且栈顶的元素不是头结点，而是我们头结点的next。有人说这样头结点不是好像一直随着压栈出栈的操作一直动吗？我把头结点放栈底那它不是不用动更好吗。但是我们数据结构追求的是效率呀，如果你的头结点是在栈低，那每次对栈顶进行操作，你都要通过遍历去找到栈顶的结点，这耗费的时间是巨大的。 解析：因为我们有N统计栈中元素的个数，所以判断是否为空时，我们只需要返回N是否等于0即可。 2.获取栈中元素的个数 public int getLength(){ return N; }解析：同样是设计到元素的个数，需要获得栈中元素的个数，我们只需要返回N即可。感觉到这个N的好处了吗？ 3.压栈（向栈顶放入元素） /压栈 public void push(T t){ if(N==0){ Node newNode = new Node(t, null); head.next=newNode; }else { //获取栈顶元素 Node a = head.next; //创建新结点 Node newNode = new Node(t, a); head.next = newNode; } N++; }解析：首先对于压栈操作，我们需要有两种情况区分，第一种情况此时栈中是否有元素，如果此时N==0，代表无元素，那我们需要new出一个新结点，保存T的值，然后将其放在head的next，因为是第一个进入的所以为栈顶元素。第二种情况此时栈中有元素，即head的next是存在结点的，因为压栈是在栈顶加入元素，这就需要我们在头结点和原栈顶元素之间插入新元素，所以我们先获取原栈顶元素a。new出的新结点保存T的值，同时next指向原栈顶元素，这时再让头结点不指向a转而指向新结点newNode，这样我们就成功压栈。最后不要忘了无论第一种还是第二种情况我们都需要让N加1。 4.出栈（拿出栈顶元素，并得到它的值） //出栈 public T pop(){ if(head.next==null){ return null; } Node a=head.next; Node b=head.next.next; head.next=b; N--; return a.item; }解析：同样需要进行对栈是否为空的判断，如果为空，我们返回null就好。如果不为空，我们首先获取栈顶结点并命名为a。再获取栈顶第二结点b，因为如果a出栈以后，b就变为栈顶元素了。我们直接让头结点head不指向a转而转向b即可，然后让N--，最后别忘记返回a.item，返回原栈顶结点的值。 ps:不难发现，出栈和压栈都与链表的插入和删除操作几乎一样，大家可以去对比一下，熟悉链表操作，对我们后续的各种数据结构的学习都是必要的 5.获取栈顶元素（未拿出） //获取栈顶元素 public T getHeadNext() { return head.next.item; }解析：因为只需要得到栈顶元素不需要拿出，所以直接返回即可。注意不是返回head.next，我们需要的是值而不是结点。 6.判断栈中是否包含该元素 //判断栈中是否包含该元素 public boolean contains(T t){ Node a=head; while (a.next!=null){ a=a.next; if(a.item==t) return true; } return false; }解析：因为栈是只能在一端进行操作的操作受限的线性表，所以想实现这个功能，我们只能通过循环遍历判断是否有需要找的元素，有则返回true，循环遍历结束还没找到，说明栈中没有，返回false即可 总结：栈的逻辑结构比较简单，实现也容易，如果成功用链表实现了，那么也请用顺序表去实现栈结构，栈用的虽然少，但也是我们必须掌握的基础数据结构。 水平尚欠，有错误请指出，多谢
|
【本文地址】
今日新闻 |
推荐新闻 |