重温数据结构：栈的顺序表示和实现与栈的链式表示和实现

1.栈的顺序表示与实现

/*
 * $filename: MyArrayStack.java,v $
 * $Date: 2014-3-11  $
 * Copyright (C) ZhengHaibo, Inc. All rights reserved.
 * This software is Made by Zhenghaibo.
 */
package edu.njupt.zhb;
/*
 *@author: ZhengHaibo  
 *web:     http://blog.csdn.net/nuptboyzhb
 *mail:    [e-mail]
 *2014-3-11  Nanjing,njupt,China
 */
/**
 * 使用数组方式实现栈
 * @author Administrator
 *
 */
public class MyArrayStack {
final int INIT_LEN = 10;//初始化长度
final int INCREAMENT_LEN = 20;//存储空间分配增量
private int top;
private Object []elements;//用于保存栈中的元素
public MyArrayStack(){
top=-1;
elements = new Object[INIT_LEN];
}
/**
 * 入栈
 * @param object
 * @return
 */
public boolean push(Object object){
if(top+1>=elements.length){//扩充空间
Object [] temp = new Object[elements.length+INCREAMENT_LEN];
for(int i=0;i<elements.length;i++){
temp[i]=elements[i];
}
elements = temp;
}
elements[++top]=object;
return true;
}
/**
 * 出栈
 * @return
 */
public Object pop(){
if(top==-1){
return null;
}
return elements[top--];
}
/**
 * 栈的大小
 * @return
 */
public int getSize(){
return top+1;
}

public Object peek(){
return elements[top];
}
/**
 * 判断栈是否为空
 * @return
 */
public boolean isEmpty(){
if(top==-1){
return true;
}
return false;
}
public static void main(String[] args) {
MyArrayStack arrayStack = new MyArrayStack();
for(int i=0;i<30;i++){
arrayStack.push("--"+i);
}
while(!arrayStack.isEmpty()){
System.out.println((String)arrayStack.pop());
}
}
}

2.栈的链式表示和实现

/*
 * $filename: MyLinkedStack.java,v $
 * $Date: 2014-3-11  $
 * Copyright (C) ZhengHaibo, Inc. All rights reserved.
 * This software is Made by Zhenghaibo.
 */
package edu.njupt.zhb;
/*
 *@author: ZhengHaibo  
 *web:     http://blog.csdn.net/nuptboyzhb
 *mail:    [e-mail]
 *2014-3-11  Nanjing,njupt,China
 */
/**
 * 用链表方式实现栈
 */
public class MyLinkedStack {
/**
 * 链表的节点
 */
public class Node{
public Node next;
public Object data;
}
private Node top;//栈顶指针
private int size;
public MyLinkedStack(){
top = new Node();
top.next = null;
size = 0;
}
/**
 * 入栈
 * @param object
 */
public void push(Object object){//将节点插入到top和top的下一个节点之间
Node node = top.next;//取出下一个节点
Node newNode = new Node();
newNode.data = object;
newNode.next = node;
top.next=newNode;
size++;
}
/**
 * 出栈
 * @return
 */
public Object pop(){
Node node = top.next;//取出栈顶节点
Object object = node.data;//取出站定节点所保存的数据
top.next= top.next.next;//删除栈顶的元素
size--;
return object;
}
/**
 * 
 * @return
 */
public int getSize(){
return size;
}
/**
 * 获取栈顶元素，但是不出栈
 * peek(偷看一眼)
 * @return
 */
public Object peek(){
return top.next;
}

public boolean isEmpty(){
if(top.next==null){
return true;
}
return false;
}

public static void main(String[] args) {
MyArrayStack arrayStack = new MyArrayStack();
for(int i=0;i<30;i++){
arrayStack.push("--"+i);
}
while(!arrayStack.isEmpty()){
System.out.println((String)arrayStack.pop());
}
}

}