栈和队列：
通常是作为程序猿的工具，用于辅助构思算法。生命周期较短，执行时才被创建
訪问受限。在特定时刻，仅仅有一个数据可被读取或删除
是一种抽象的结构。内部的实现机制。对用户不可见。比方用数组、链表来实现栈
栈：
同一时候，仅仅同意一个数据被訪问，后进先出
对于入栈和出栈的时间复杂度都为O(1),即不依赖栈内数据项的个数，操作比較快
例，使用数组作为栈的存储结构
public class StackS<T> {
private int max;
private T[] ary;
private int top; //指针，指向栈顶元素的下标
public StackS(int size) {
this.max = size;
ary = (T[]) new Object[max];
top = -1;
}
// 入栈
public void push(T data) {
if (!isFull())
ary[++top] = data;
}
// 出栈
public T pop() {
if (isEmpty()) {
return null;
}
return ary[top--];
}
// 查看栈顶
public T peek() {
return ary[top];
}
//栈是否为空
public boolean isEmpty() {
return top == -1;
}
//栈是否满
public boolean isFull() {
return top == max - 1;
}
//size
public int size() {
return top + 1;
}
public static void main(String[] args) {
StackS<Integer> stack = new StackS<Integer>(3);
for (int i = 0; i < 5; i++) {
stack.push(i);
System.out.println("size:" + stack.size());
}
for (int i = 0; i < 5; i++) {
Integer peek = stack.peek();
System.out.println("peek:" + peek);
System.out.println("size:" + stack.size());
}
for (int i = 0; i < 5; i++) {
Integer pop = stack.pop();
System.out.println("pop:" + pop);
System.out.println("size:" + stack.size());
}
System.out.println("----");
for (int i = 5; i > 0; i--) {
stack.push(i);
System.out.println("size:" + stack.size());
}
for (int i = 5; i > 0; i--) {
Integer peek = stack.peek();
System.out.println("peek:" + peek);
System.out.println("size:" + stack.size());
}
for (int i = 5; i > 0; i--) {
Integer pop = stack.pop();
System.out.println("pop:" + pop);
System.out.println("size:" + stack.size());
}
}
}
上面的样例。有一个maxSize的规定。由于数组是要规定大小的，若想无限制，能够使用其它结构来做存储，当然也能够new一个新的长度的数组。
例。使用LinkedList存储来实现栈
/**
* 使用LinkedList存储来实现栈
* @author stone
*
* @param <T>
*/
public class StackSS<T> {
private LinkedList<T> datas; public StackSS() {
datas = new LinkedList<T>();
} // 入栈
public void push(T data) {
datas.addLast(data);
} // 出栈
public T pop() {
return datas.removeLast();
} // 查看栈顶
public T peek() {
return datas.getLast();
} //栈是否为空
public boolean isEmpty() {
return datas.isEmpty();
} //size
public int size() {
return datas.size();
} public static void main(String[] args) {
StackS<Integer> stack = new StackS<Integer>(3);
for (int i = 0; i < 5; i++) {
stack.push(i);
System.out.println("size:" + stack.size());
}
for (int i = 0; i < 5; i++) {
Integer peek = stack.peek();
System.out.println("peek:" + peek);
System.out.println("size:" + stack.size());
}
for (int i = 0; i < 5; i++) {
Integer pop = stack.pop();
System.out.println("pop:" + pop);
System.out.println("size:" + stack.size());
} System.out.println("----");
for (int i = 5; i > 0; i--) {
stack.push(i);
System.out.println("size:" + stack.size());
}
for (int i = 5; i > 0; i--) {
Integer peek = stack.peek();
System.out.println("peek:" + peek);
System.out.println("size:" + stack.size());
}
for (int i = 5; i > 0; i--) {
Integer pop = stack.pop();
System.out.println("pop:" + pop);
System.out.println("size:" + stack.size());
}
}
}
例，单词逆序，使用Statck结构
public class WordReverse {
public static void main(String[] args) {
reverse("株式会社");
}
static void reverse(String word) {
if (word == null) return;
StackSS<Character> stack = new StackSS<Character>();
char[] charArray = word.toCharArray();
int len = charArray.length;
for (int i = 0; i <len; i++ ) {
stack.push(charArray[i]);
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
System.out.println("反转后：" + sb.toString());
}
}
打印：
反转后：社会式株