目录
栈
栈的API设计
栈代码实现
队列
队列的API设计
队列的实现
栈
栈是一种基于先进后出(FILO)的数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后个数据被第一个读出来)。数据进入到栈的动作为压栈，数据从栈中出去的动作为弹栈。
栈的API设计
栈代码实现
//栈 public class Stack<T> implements Iterable<T> { private Node head; //记录首结点 private int N; //栈中元素的个数 //节点类 private class Node{ public T item; public Node next; public Node(T item, Node next) { this.item = item; this.next = next; } } //初始化头结点和元素个数 public Stack(){ this.head = new Node(null,null); N=0; } //判断当前栈中元素个数是否为0 public boolean isEmpty(){ return N==0; } //获取栈中元素的个数 public int size(){ return N; } //把t元素压入栈 public void push(T t){ //找到首结点指向的第一个结点 Node oldTop = head.next; //创建新结点 Node newTop = new Node(t,null); //让首结点指向新结点 head.next = newTop; //让新结点指向原来的第一个结点 newTop.next = oldTop; //元素个数+1； N++; } //弹出栈顶元素 public T pop(){ Node oldTop = head.next; if(oldTop==null){ return null; //空栈 } //让首结点指向原来第一个结点的下一个结点 head.next = oldTop.next; //元素个数-1； N--; return oldTop.item; } //重写迭代器遍历方法 //实现Iterable接口，重写接口的iterator方法； @Override public Iterator<T> iterator() { return new SIterator(); } //实现Iterator接口，重写hasNext方法和next方法； private class SIterator implements Iterator<T>{ private Node n; public SIterator(){ this.n=head; } @Override public boolean hasNext() { return n.next!=null; } @Override public T next() { n = n.next; return n.item; } } //测试 public static void main(String[] args) { //创建栈对象 Stack<String> stack =new Stack<String>(); //测试压栈 stack.push("a"); stack.push("b"); stack.push("c"); stack.push("d"); //迭代器遍历 for (String item : stack) { System.out.println(item); } System.out.println("------------------------------"); //测试弹栈 String result = stack.pop(); System.out.println("弹出的元素是："+result); System.out.println("剩余的元素个数："+stack.size()); } }
队列
队列是一种基于先进先出(FIFO)的数据结构，是一种只能在一端进行插入,在另一端进行删除操作的特殊线性表，它按照先进先出的原则存储数据，先进入的数据，在读取数据时先读被读出来。
队列的实现
//队列 public class Queue<T> implements Iterable<T> { private Node head; //记录首结点 private Node last; //记录最后一个结点 private int N; //记录队列中元素的个数 //节点类 private class Node{ public T item; public Node next; public Node(T item, Node next) { this.item = item; this.next = next; } } //初始化 public Queue(){ this.head = new Node(null,null); this.last = null; this.N = 0; } //判断队列是否为空 public boolean isEmpty(){ return N==0; } //返回队列中元素的个数 public int size(){ return N; } //向队列中插入元素t 入队 从尾结点入队 public void enqueue(T t){ //空队列 头结点和尾结点都指向null if(last==null){ last = new Node(t,null); //元素t成为尾结点的值 head.next = last; //头结点指向尾结点 }else{ //当前尾结点last不为null Node oldLast = last; last = new Node(t,null); //元素t成为尾结点的值 oldLast.next = last; //旧尾结点指向新尾结点 } //元素个数+1 N++; } //从队列中拿出一个元素 出队 从头结点出队 public T dequeue(){ if(isEmpty()){ //元素个数为 0 return null; } Node oldFirst = head.next; head.next = oldFirst.next; //删除第一个元素 N--; //因为出队列其实是在删除元素，因此如果队列中的元素被删除完了，需要重置last=null; if (isEmpty()){ last=null; } return oldFirst.item; } //重写迭代器遍历方法 //实现Iterable接口，重写接口的iterator方法； @Override public Iterator<T> iterator() { return new QIterator(); } //实现Iterator接口，重写hasNext方法和next方法； private class QIterator implements Iterator<T>{ private Node n; public QIterator(){ this.n=head; } @Override public boolean hasNext() { return n.next!=null; } @Override public T next() { n = n.next; return n.item; } } //测试 public static void main(String[] args) { //创建队列对象 Queue<String> q = new Queue<>(); //测试队列的enqueue方法 q.enqueue("a"); q.enqueue("b"); q.enqueue("c"); q.enqueue("d"); for (String str : q) { System.out.println(str); } System.out.println("-------------------------------"); //测试队列的dequeue方法 String result = q.dequeue(); System.out.println("出队列的元素是："+result); System.out.println("剩余的元素个数："+q.size()); } }
