数据结构学习之栈的Java实现

介绍

栈是一种后进先出的数据结构，就像盖房子的砖头一样，后来者居上。栈只允许在一端进行插入和删除操作，叫做栈顶。栈也有两种实现方式，一种用数组实现，叫顺序栈，另一种用链表实现，叫做链栈。

顺序栈

package Stack;

/**
 * Created by xiaojian on 2017/7/20.
 * 顺序栈 入栈 出栈 判空 返回栈顶元素
 */
public class SequenceStack {
private Object[] data = new Object[5];
// 栈顶
private int top=0;
// 元素个数
private int size=0;

// 入栈
public void push(Object o){
if(isFull()){
            increStack();
        }
        data[top++] = o;
        size++;
    }
// 出栈
public Object pop(){
if(isEmpty()){
throw new RuntimeException("栈空");
        }
        Object o = data[top-1];
        data[--top] = null;
        size--;
return  o;
    }
// 返回栈顶元素
public Object getTop(){
if(!isEmpty()){
return data[top-1];
        }
return null;
    }
// 扩容
public void increStack(){
        Object[] newData = new Object[data.length * 2];
        System.arraycopy(data,0,newData,0,data.length);
        data = newData;
    }
// 遍历
public void display(){
while(!isEmpty()){
            System.out.println(pop());
        }
    }
// 判空
public boolean isEmpty(){
return size == 0;
    }
// 栈满
public boolean isFull(){
return size == data.length;
    }

}

链栈

package Stack;

/**
 * Created by xiaojian on 2017/7/21.
 * 结点类
 */
public class Node {
private Object data;
private Node next;

public Object getData() {
return data;
    }

public void setData(Object data) {
this.data = data;
    }

public Node getNext() {
return next;
    }

public void setNext(Node next) {
this.next = next;
    }
}

package Stack;

/**
 * Created by xiaojian on 2017/7/20.
 * 链栈
 */
public class LinkQueue {
private Node top = null;
private int size =0;

// 进栈
public void push(Object o){
        Node node = new Node();
        node.setData(o);
if(top==null){
            top = node;
        }else{
            node.setNext(top);
            top= node;
        }
        size++;
    }
// 出栈
public Object pop( ){
if(isEmpty()){
throw new RuntimeException("栈空");
        }else {
            Node node = top;
            top = top.getNext();
            node.setNext(null);
            size -- ;
return node.getData();
        }
    }
//返回栈顶元素
public Object getTop(){
if(isEmpty()){
throw new RuntimeException("栈空");
        }
return top.getData();
    }
// 遍历
public void display(){
while(top!=null){
           System.out.println(pop());
        }
    }
public boolean isEmpty(){
return size == 0;
    }


}