java数据结构系列之栈
手写栈
1.利用链表做出栈，因为栈的特殊，插入删除操作都是在栈顶进行，链表不用担心栈的长度，所以链表再合适不过了，非常好用，不过它在插入和删除元素的时候，速度比数组栈慢，因为它要维护自己的指针(Next)引用。
package com.rsc.stack;
import java.util.LinkedList;
/**
* 利用链表实现的栈
* @author 落雨
* http://ae6623.cn
* @param <T>
*/
public class LinkedListStack<T> {
LinkedList<T> list;
public LinkedListStack() {
list = new LinkedList();
}
/**
* 出栈
*
* @return
*/
public T pop() {
return list.removeLast();
}
/**
* 入栈
*
* @param t
*/
public void push(T t) {
list.add(t);
}
public T getTop() {
return list.getLast();
}
public boolean isEmpty() {
return list.size() == 0;
}
public int getSize() {
return list.size();
}
public static void main(String[] args) {
LinkedListStack<String> ls = new LinkedListStack<String>();
System.out.println(ls.getSize());
ls.push("2");
ls.push("我");
ls.push("你");
ls.push("他");
ls.push("1");
ls.push("3");
ls.push("5");
System.out.println(ls.getSize());
System.out.println(ls.getTop());
ls.pop();
System.out.println(ls.getSize());
System.out.println(ls.getTop());
ls.push("嘿嘿");
System.out.println(ls.getSize());
System.out.println(ls.getTop());
}
}
打印结果:
0
7
5
6
3
7
嘿嘿
2.利用数组实现的栈，好处是速度快，坏处是要考虑数组的扩容，既然要扩容，肯定就涉及数组元素的拷贝，一对一的一个萝卜一个坑的塞过去，相对链表来说，它的插入和删除就比链表要快，因为它不用维护指针(Next),不懂这个指针next的同学，自行脑补链表的实现方式，下节会说到链表的实现。
package com.rsc.stack;
import java.util.Arrays;
/**
* 利用数组实现的栈的数据结构
*
* @author
* 落雨 2015年6月5日 http://ae6623.cn
*
*/
public class ArrayStack {
public Object[] t;// 存数的数据数组
int top = 0;// 默认Top为0
public ArrayStack(int size) {
t = new Object[size];
}
public boolean isEmpty() {
return top == 0;
}
public boolean clean() {
top = 0;
return true;
}
public void pop() {
if (top > 0) {
t[--top] = null;
}
System.out.println(getTop());
}
public void push(Object o) {
// 检测扩容
if (top >= t.length) {
int newCapacity = (t.length * 3) / 2 + 1; // 增加50%+1
Object[] newObject = new Object[newCapacity];
int k = 0;
for (Object i : t) {
newObject[k++] = i;
}
t = newObject;
}
t[top++] = o;
System.out.println(getTop());
}
public Object getTop() {
System.out.println("top:" + top);
printStack();
return top <= 0 ? null : "当前栈顶元素:" + t[top - 1];
}
public int getSize() {
return top;
}
public void printStack() {
System.out.println(Arrays.toString(t));
}
public static void main(String[] args) {
ArrayStack as = new ArrayStack(5);
as.push("1");
as.push("2");
as.push("3");
as.push("4");
as.push("5");
as.push("我");
as.push("6");
as.push("7");
as.printStack();
as.pop();
as.pop();
as.pop();
as.pop();
as.pop();
as.pop();
as.pop();
as.pop();
as.pop();
}
}
打印结果:
top:1
[1, null, null, null, null]
当前栈顶元素:1
top:2
[1, 2, null, null, null]
当前栈顶元素:2
top:3
[1, 2, 3, null, null]
当前栈顶元素:3
top:4
[1, 2, 3, 4, null]
当前栈顶元素:4
top:5
[1, 2, 3, 4, 5]
当前栈顶元素:5
top:6
[1, 2, 3, 4, 5, 我, null, null]
当前栈顶元素:我
top:7
[1, 2, 3, 4, 5, 我, 6, null]
当前栈顶元素:6
top:8
[1, 2, 3, 4, 5, 我, 6, 7]
当前栈顶元素:7
[1, 2, 3, 4, 5, 我, 6, 7]
top:7
[1, 2, 3, 4, 5, 我, 6, null]
当前栈顶元素:6
top:6
[1, 2, 3, 4, 5, 我, null, null]
当前栈顶元素:我
top:5
[1, 2, 3, 4, 5, null, null, null]
当前栈顶元素:5
top:4
[1, 2, 3, 4, null, null, null, null]
当前栈顶元素:4
top:3
[1, 2, 3, null, null, null, null, null]
当前栈顶元素:3
top:2
[1, 2, null, null, null, null, null, null]
当前栈顶元素:2
top:1
[1, null, null, null, null, null, null, null]
当前栈顶元素:1
top:0
[null, null, null, null, null, null, null, null]
null
top:0
[null, null, null, null, null, null, null, null]
null