当前位置：首页 > news >正文

Android 开发数据结构理解队列和栈分析及实现

news 来源：原创 2024/5/19 13:27:27

队列是一种（先进先出）的数据结构，栈（先进后出）的数据结后

回顾JDK提供的集合类

　　容器（集合）框架如下：

　　集合类存放于java.util包中。集合类存放的都是对象的引用，而非对象本身。

　　集合类型主要有3种：set(集）、list(列表）和map(映射)。

　　Collection接口

　　├List 接口

　　│├LinkedList 链表

　　│├ArrayList 顺序结构动态数组类

　　│└Vector 向量

　　│ └Stack 栈

　　Map接口

　　├Hashtable

　　├HashMap

　　└Set接口

　　Collection<--Set<--HashSet

　　Collection<--Set<--HashSet<--LinkedHashSet

　　Collection<--Set<--SortedSet（也是接口）<--TreeSet

　　LinkedList 双端队列

我们就来实现基于 LinkedList 的队列和栈

队列实现：

import java.util.LinkedList;
import java.util.Queue;

public class MyQueue<T> {
private Queue<T> storage = new LinkedList<T>();

/** 将指定的元素插入队尾 */
public void offer(T v) {
        storage.offer(v);
    }

/** 检索，但是不移除队列的头，如果此队列为空，则返回 null */
public T peek() {
return storage.peek();
    }

/** 检索，但是不移除此队列的头 */
/** 此方法与 peek 方法的惟一不同是，如果此队列为空，它会抛出一个异常 */
public T element() {
return storage.element();
    }

/** 检索并移除此队列的头，如果队列为空，则返回 null */
public T poll() {
return storage.poll();
    }

/** 检索并移除此队列的头 */
/** 此方法与 poll 方法的不同在于，如果此队列为空，它会抛出一个异常 */
public T remove() {
return storage.remove();
    }

/** 队列是否为空 */
public boolean empty() {
return storage.isEmpty();
    }

/** 打印队列元素 */
public String toString() {
return storage.toString();
    }
}

栈实现：

import java.util.LinkedList;

public class Stack<T> {
private LinkedList<T> storage = new LinkedList<T>();

/** 入栈 */
public void push(T v) {
       storage.addFirst(v);
    }

/** 出栈，但不删除 */
public T peek() {
return storage.getFirst();
    }

/** 出栈 */
public T pop() {
return storage.removeFirst();
    }

/** 栈是否为空 */
public boolean empty() {
return storage.isEmpty();
    }

/** 打印栈元素 */
public String toString() {
return storage.toString();
    }
}