正文
java_stack
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
栈是一种数据结构，它代表只能在某一端进行插入、删除操作的特殊线性表。
栈的最大特点是是后进先出（First In Last Out），对栈的操作主要是入栈和出栈，判断栈是否为空，计算栈的大小。
对栈而言， 允许插入删除的一端是栈顶 ，另一端则称为栈底。
实际应用： 表达式求值和语法解析，校验和解析XML，文本编辑器里的撤销动作，浏览器里的浏览记录
栈的顺序存储实现：(基于数组实现)
package collectionsFramework.stack; /**
* @Package collectionsFramework.stack * @ClassName: SequenceStack * @Description: TODO(这里用一句话描述这个类的作用) * @author andy * @date 2013-11-22 下午04:03:14 */
public class SequenceStack<T>{
//栈里面的元素个数
private int size = 0;
//栈的默认容量大小
private int defaultCapacity = 10;
//栈的容量
private int capacity;
//容纳栈的数组
private Object[] elementData;
//栈满了之后,增量大小
private int incrementCapacity; //默认大小的空堆栈
public SequenceStack(){
capacity = defaultCapacity;
elementData = new Object[capacity];
} //指定容量大小的空堆栈
public SequenceStack(int capacity){
elementData = new Object[this.capacity];
} //指定容量大小和增量大小的空堆栈
public SequenceStack(int capacity,int incrementCapacity){
this(capacity);
this.incrementCapacity = incrementCapacity;
} //保证空间足够
private void ensureCapacity() throws Exception{
if(elementData.length == size){
Object[] copyElementData = elementData; int length = 0;
if(incrementCapacity > 0){
length = copyElementData.length + incrementCapacity;
}else{
length = copyElementData.length<<1;
}
elementData = new Object[length];
try {
System.arraycopy(copyElementData, 0, elementData, 0, elementData.length-1);
} catch (Exception e) {
throw new Exception("扩充数组时出现系统错误!");
}
}
} //入栈
public synchronized T push(T object){
boolean flag = true;
if(null != object){
try {
ensureCapacity();
} catch (Exception e) {
try {
ensureCapacity();
} catch (Exception e1) {
System.out.println("第二次扩容再次失败！");
flag = false;
}
}
if(flag){
elementData[size++] = object;
return object;
}else{
return null;
}
} return null;
} //出栈
public synchronized T pop(){
if(size == 0){
throw new RuntimeException("空栈");
}
return (T)elementData[--size];
} //获取栈顶元素但不移除
public synchronized T peek(){
if(size == 0){
throw new RuntimeException("空栈");
}
return (T)elementData[size-1];
} //获取元素个数
public synchronized int size(){
return size;
} //堆栈是否为空
public boolean empty() {
return size() == 0;
} public static void main(String[] args) {
SequenceStack<String> stack = new SequenceStack<String>();
System.out.println("元素" + stack.push("a") + "入栈");
System.out.println("元素" + stack.push("b") + "入栈");
System.out.println("元素" + stack.push("c") + "入栈");
System.out.println("元素" + stack.push("d") + "入栈");
System.out.println("元素" + stack.push("e") + "入栈"); System.out.println("-----------");
System.out.println("栈顶元素：" + stack.peek());
System.out.println("元素个数：" + stack.size());
System.out.println("-----------");
while(stack.size > 0){
System.out.println("元素" + stack.pop() + "出栈");
} }
}
栈的链式存储实现：（保存本节点数据，并保存对下一个结点的引用即指针） 跟单链表差不多
package collectionsFramework.stack; /**
* @Package collectionsFramework.stack
*
* @ClassName: LinkStack
*
* @Description: TODO(这里用一句话描述这个类的作用)
*
* @author andy
*
* @date 2013-11-22 下午05:58:55
*/
public class LinkStack<T> {
// 节点
private class Node {
// 保存本节点数据
private T data;
// 指向下个节点的引用
private Node next; public Node() { }
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
} //栈顶元素
private Node top;
//节点数
private int size; //创建空链栈
public LinkStack(){
top = null;
} //以指定数据元素来创建链栈，该链栈只有一个元素
public LinkStack(T element){
top = new Node(element, null);
size++;
} //进栈
public synchronized T push(T element) {
if(size==0){
top = new Node(element,null);
}else{
Node oldTop = top;
top = new Node(element,oldTop);
} size++;
return top.data;
} //出栈
public synchronized T pop() {
if(!empty()){
Node oldTop = top;
top = oldTop.next;
oldTop.next = null;
size--;
return oldTop.data;
}
return null;
} //访问栈顶元素，但不删除栈顶元素
public synchronized T peek() {
if(!empty()){
return top.data;
}
return null;
} // 判断链栈是否为空栈
public boolean empty() {
return size == 0;
} // 返回链栈的长度
public synchronized int length() {
return size;
} public static void main(String[] args) {
LinkStack<Character> stack = new LinkStack<Character>();
System.out.println("元素：" + stack.push('a') + "进栈");
System.out.println("元素：" + stack.push('b') + "进栈");
System.out.println("元素：" + stack.push('c') + "进栈");
System.out.println("元素：" + stack.push('d') + "进栈");
System.out.println("元素：" + stack.push('e') + "进栈"); System.out.println("-------");
System.out.println("栈顶元素：" + stack.peek());
System.out.println("-------");
while(stack.size >0){
System.out.println("元素:" + stack.pop() + "出栈");
}
} }
