登录后台

页面导航

本文编写于 258 天前,最后修改于 242 天前,其中某些信息可能已经过时。

算法(二)来啦!
最近一直在新家忙着归置东西,加上我都在玩(狗头)。所以最近没怎么学习。只看了一点点数据结构方面的东西:队列、栈、链表。

一、队列

队列是一种特殊的线性结构,它只能在队列首进行删除操作,队列尾进行插入操作。由于LinkedList继承了 Queue接口,所以Java中队列可以用LinkedList来实现。

 LinkedList<String>queue=new LinkedList<>();
    queue.offer("a");//向队列中插入元素
    queue.offer("b");
    queue.offer("c");
    queue.offer("d");
    queue.offer("e");
    System.out.println(queue.peek());//返回第一个元素
    System.out.println("----");
    for (String s:queue){
        System.out.println(s);
    }
    System.out.println("----");
    System.out.println(queue.poll());//返回并删除队列的第一个元素
    System.out.println("----");
    for (String s:queue){
        System.out.println(s);
    }
输出:  a abcde a bcde

很简单对吧,没错我也这么想。

二、栈

接下来是一个很有意思的东西,栈。栈的特点就是后进先出,只能在一端进行插入和删除操作。比如有一个箱子,先放进去的书在最底部,要最后才能拿出来。后放进去的书在最上部,却可以最先拿出来。
在Java中,栈的实现如下:

class Stack {
private int maxsize;
private int top;
private char[] a = new char[101];

public Stack(int s) {
    top = -1;
    maxsize = s;
}

public void push(char i) {
    top++;
    a[top] = i;
}

public char pop() {
    return a[top--];
}

public char peek() {
    return a[top];
}

public boolean isempty() {
    return (top == -1);
}

public boolean isFull() {
    return (top == maxsize - 1);
}

利用栈的特性,我们可以完成一个有趣的操作:反转字符串。
代码如下:

public class RevString {
private String input;
private String output;
public RevString(String in) {
    input = in;
}
public String  rev(){
    int size=input.length();
    Stack ss=new Stack(size);
    for (int i=0;i<size;i++){
        char a=input.charAt(i);
        ss.push(a);
    }
    output="";
    while(!ss.isempty()){
        char b=ss.pop();
        output+=b;
    }
    return output;
}
public static void main(String args[]) {
    String input="Google";
    String output;
    RevString r=new RevString(input);
    output=r.rev();
    System.out.println(input);
    System.out.println(output);
}
输出:elgooG

三、链表

在Java中,链表同样可以通过LinkedList实现。

LinkedList<String> l=new LinkedList<>();
    l.add("aaa");
    l.add("bbb");
    l.add("ccc");
    l.add("ddd");
    l.add("eee");
    l.add("aaa");
    System.out.println(l.getFirst());
    System.out.println(l.getLast());
    System.out.println(l.indexOf("aaa"));
    System.out.println(l.lastIndexOf("aaa"));
    System.out.println(l);
    l.set(2,"cccc");
    System.out.println(l);

上面是通过数组方式来模拟链表。还有一种方式是用指针(java中可以用类的引用代替)来实现,由于我对指针十分厌恶,这里就先不写了,等哪天心情好再补充吧。