栈和队列是两种特殊的线性表,它们的逻辑结构和线性表相同,只是其运算规则较线性表有更多的限制,故又称它们为运算受限的线性表。
LinkedList数据结构是一种双向的链式结构,每一个对象除了数据本身外,还有两个引用,分别指向前一个元素和后一个元素,和数组的顺序存储结构(如:ArrayList)相比,插入和删除比较方便,但速度会慢一些。
栈的定义
栈(Stack)是限制仅在表的一端进行插入和删除运算的线性表。
(1)通常称插入、删除的这一端为栈顶(Top),另一端称为栈底(Bottom)。
(2)当表中没有元素时称为空栈。
(3)栈为后进先出(Last In First Out)的线性表,简称为LIFO表。
栈的修改是按后进先出的原则进行。每次删除(退栈)的总是当前栈中"最新"的元素,即最后插入(进栈)的元素,而最先插入的是被放在栈的底部,要到最后才能删除。
实现代码:
package com.gc.list;
import java.util.*;
public class MyStack {
private LinkedList ll=new LinkedList();
public void push(Object o){
ll.addFirst(o);
}
public Object pop(){
return ll.removeFirst();
}
public Object peek(){
return ll.getFirst();
}
public boolean empty(){
return ll.isEmpty();
}
public static void main(String[] args){
MyStack ms=new MyStack();
ms.push("zhangsan");
ms.push("lisi");
ms.push("wangwu");
System.out.println(ms.pop());
System.out.println(ms.peek());
System.out.println(ms.pop());
System.out.println(ms.empty());
}
}
队列定义
队列(Queue)是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表
(1)允许删除的一端称为队头(Front)。
(2)允许插入的一端称为队尾(Rear)。
(3)当队列中没有元素时称为空队列。
(4)队列亦称作先进先出(First In First Out)的线性表,简称为FIFO表。
实现代码:
package com.gc.list;
import java.util.*;
public class MyQueue {
private LinkedList ll=new LinkedList();
public void put(Object o){
ll.addLast(o);
}
//使用removeFirst()方法,返回队列中第一个数据,然后将它从队列中删除
public Object get(){
return ll.removeFirst();
}
public boolean empty(){
return ll.isEmpty();
}
public static void main(String[] args){
MyQueue mq=new MyQueue();
mq.put("zhangsan");
mq.put("lisi");
mq.put("wangwu");
System.out.println(mq.get());
System.out.println(mq.get());
System.out.println(mq.get());
System.out.println(mq.empty());
}
}
java 集合类的排序主要是用Collections.sort方法,Collections和Collection是不一样的,前者是类,后者是接口,在这里,我主要是想说明它的sort方法的几种类型,
提示:实现接口的方法时,只需要比较两个数,大的返回1,相等返回0,小于返回-1。简单的说就是在方法里这样写:num>s.num?1:(num==s.num?0:-1); num是被比较的数,s.num是比较的数,
1.Collection.sort(List arg0);
这种是最简单的一种排序方法,只需要实现他的Comparable 接口及实现public int compareTo(Object arg0)方法即可。
2.Collection.srot(List arg0,Comparator arg1);
这种加入了比较器,具有更大的灵活性,便于管理,比较器可作为内部静态类的,以便于管理。比较器必须实现Comparator接口,具体可参照下列代码:
package com.gc.list;
import java.util.*;
public class ArrayListTest {
public static void printElements(Collection c){
Iterator it=c.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
}
public static void main(String[] args){
ArrayList a1=new ArrayList();
/*
a1.add("zhangsan");
a1.add("lisi");
a1.add("wangwu");
*/
/*
a1.add(new Point(1,1));
a1.add(new Point(2,2));
a1.add(new Point(3,3));
for(int i=0;i<a1.size();i++){
System.out.println(a1.get(i));
}
Object[] objs=a1.toArray();
for(int i=0;i<objs.length;i++){
System.out.println(objs[i]);
}
List l=Arrays.asList(objs);
System.out.println(l);*/
//l.add("chuyang");
//l.set(0,new Point(4,4));
/*
Iterator it=a1.iterator();
while(it.hasNext()){
System.out.println(it.next());
}
*/
Student s1=new Student(4,"zhangsan");
Student s2=new Student(2,"lisi");
Student s3=new Student(3,"wangwu");
Student s4=new Student(4,"mybole");
a1.add(s1);
a1.add(s2);
a1.add(s3);
a1.add(s4);
//Collections.sort(a1);
Collections.sort(a1,new Student.StudentComparator());
printElements(a1);
System.out.println(Collections.max(a1));
}
}
class Point{
int x, y;
Point(int x,int y){
this.x=x;
this.y=y;
}
public String toString(){
return ("x="+x+","+"y="+y);
}
}
class Student implements Comparable{
int num;
String name;
Student(int num,String name){
this.num=num;
this.name=name;
}
static class StudentComparator implements Comparator{
public int compare(Object o1,Object o2){
Student s1=(Student) o1;
Student s2=(Student) o2;
int result=s1.num>s2.num?1:(s1.num==s2.num?0:-1);
if (result==0){
result=s1.name.compareTo(s2.name);
}
return result;
}
}
public int compareTo(Object arg0) {
Student s=(Student) arg0;
return num>s.num?1:(num==s.num?0:-1);
}
public String toString(){
return "num:"+num+","+"name:"+name;
}
}