1.栈（stack）
栈是后进先出的（LIFO） 策略的集合类型。
基本API
push(item) 添加一个元素
item pop(item)) 删除并返回一个元素
isEmpty 栈是否为空
size 栈中的元素数量
让我们创建一个用数组来实现栈的代码，并且支持可变数组大小 而且使用率永远不低于1/4
package com.qing.algorithms;
//一个可变的数组实现栈的方法
public class FixedCapacityStack<T> {
/***
* 一种表示泛型定容栈的数组实现
* FixedCapacityStack(int cap) 创建一个容量为cap的空栈
* push(item) 添加一个元素
*item pop(item)) 删除并返回一个元素
* isEmpty 栈是否为空
* size 栈中的元素数量
*
*/
private T[] a;
private int N = 0; //有效数量
/***
*
* @param cap 最大存储数量
*/
public FixedCapacityStack(int cap) {
a = (T[]) new Object[cap];
}
public boolean isEmtry() {
return N == 0;
}
//添加
public void push(T t) {
//如果数组没有空间 添加两倍数组长度给它
if (N == a.length) resize(2 * a.length);
a[N++] = t;//先赋值 然后++
}
//推出
public T pop() {
if(isEmtry()){
return null;
}
T item = a[--N];//从0开始
a[N] = null;
//如果数组太大，只用到1/4的空间，将数组减半
if (N > 0 && N == a.length / 4) resize(a.length / 2);
return item;
}
/***
* 创建一个数组赋值给a
* @param max
*/
private void resize(int max) {
T[] temp = (T[]) new Object[max];
for (int i = 0; i < N; i++) {
temp[i] = a[i];
}
a = temp;
}
public void showStack() {
StringBuilder sb = new StringBuilder();
System.out.println("数组大小为 "+ a.length);
for (int i=0 ;i<N;i++) {
T item = a[i];
if (item != null) sb.append(" "+i + item.toString());
else sb.append(" "+i +"null");
}
System.out.println(sb.toString());
}
public static void main(String args[]) {
FixedCapacityStack<String> stack = new FixedCapacityStack<>(2);
stack.push("a");
stack.push("b");
stack.push("c");
stack.push("d");
stack.showStack();
stack.pop();
stack.pop();
stack.pop();
stack.showStack();
}
}
/**
数组大小为 4
0a 1b 2c 3d
数组大小为 2
0a
**/
使用单向链表实现栈代码
为什么使用单向链表？
- 因为单向列表已经满足上面的栈基本api了，但有个缺点，任意位置删除和插入与链表的长度成正比（因为删除的时候要遍历链表来判断是否等于要删除元素），实现任意插入和删除操作应该使用 双向链表
基本数据类型
private class Node{
T item; //当前元素
Node next; //上一个元素 ， 因为后添加压在上面所以取名为next
}
下面是完整代码
package com.qing.algorithms;
import java.util.Iterator;
/***
* 使用链表实现的栈
* 实现Iterable 可遍历
* @param <T>
*/
public class Stack<T> implements Iterable<T> {
private Node first; //栈顶(最近添加的元素)
private int N =0; //元素数量
private class Node{
T item;
Node next;
}
public int getSize(){
return N;
}
public boolean isEmpty(){
return first==null;
}
/***
* 向栈顶添加元素
* @param item
*/
public void push(T item){
Node oldFirst =first;//第一次push first为null
first = new Node();
first.item = item;
first.next = oldFirst; //指向上一个元素
N++;
}
/***
* 向栈顶删除元素
*/
public T pop(){
T item = first.item;
first =first.next;
N--;
return item;
}
@Override
public Iterator<T> iterator() {
return new StackIterator();
}
private class StackIterator implements Iterator<T>{
private Node current = first;
@Override
public boolean hasNext() {
return current!=null;
}
@Override
public T next() {
T item = current.item;
current = current.next;
return item;
}
}
private void showStack() {
int i =0;
StringBuilder sb = new StringBuilder();
for (T t : this) {
sb.append(" " + i + t);
i++;
}
System.out.println(sb.toString());
}
public static void main(String args[]) {
Stack<String> stack = new Stack<>();
stack.push("a");
stack.push("b");
stack.push("c");
stack.push("d");
stack.showStack();
stack.pop();
stack.pop();
stack.pop();
stack.showStack();
}
}
/***
0d 1c 2b 3a
0a
**/
1.队列（Queue）
- void enqueue(Item item) 添加一个元素
- Item dequeue() 删除最早添加的元素
- booean isEmtry() 队列是否为null
- int size() 队列中的元素数量
