栈的Java实现

  栈是存放对象的一种特殊容器，在插入与删除对象时，这种结构遵循后进先出（Last-in-first-out，LIFO）的原则⎯⎯也就是说，对象可以任意插入栈中，但每次取出的都是此前插入的最后一个对象。

Java栈的通用接口

package com.stack;

public interface Stack {

    public int getSize();//返回栈中元素个数
    
    public boolean isEmpty();//判断栈是否为空
    
    public Object top();//获取栈顶元素，但不删除
    
    public void push(Object elem);//入栈
    
    public Object pop();//出栈
}

基于数组实现栈

package com.stack;

public class MyStack implements Stack{

    public static final int CAPACITRY = 1024;
    public int capacity;
    public Object[] s;
    public int top = -1;
    
    public MyStack()
    {
        this(CAPACITRY);
    }
    
    
    public MyStack(int cap) {
        capacity = cap;
        s = new Object[capacity];
    }


    @Override
    public int getSize() {
        
        return top+1;
    }

    @Override
    public boolean isEmpty() {
        
        return (top < 0);
    }

    @Override
    public Object top() {
        
        if(isEmpty())
        {
            System.out.println("栈为空");
            return null;
        }
        return s[top];
    }

    @Override
    public void push(Object elem) {
        if(getSize() == capacity)
        {
            System.out.println("栈满");       
            return;
        }
        s[++top] = elem;
    }

    @Override
    public Object pop() {
        if(isEmpty())
        {
            System.out.println("栈为空");
            return null;
        }
        
        Object elem = s[top];
        s[top--] = null;
        return elem;
    }

}

基于单链表实现栈

  节点的java实现

package com.node;

public class Node {

    private Object elem;
    private Node next;
    
    public Node()
    {
        this(null,null);
    }
    
    public Node(Object e,Node n)
    {
        elem = e;
        next = n;
    }
    
    public Object getElem() {       
        return elem;
    }

    public void setElem(Object elem) {
        this.elem = elem;
    }
    
    public Node getNext()
    {
        return this.next;
    }
    
    public void setNext(Node next)
    {
        this.next = next;
    }

}

  栈的实现

package com.stack;

import com.node.Node;

//单链表实现栈
public class Stack_list implements Stack{

    protected Node top;//栈顶元素
    protected int size;//栈中元素个数
    
    //初始化时创建头结点
    public Stack_list()
    {
        top = null;
        size = 0;
    }
    
    @Override
    public int getSize() {

        return size;
    }

    @Override
    public boolean isEmpty() {
        return (top == null)?true:false;
    }

    @Override
    public Object top() {
        if(isEmpty())
        {
            System.out.println("栈为空");
        }
        return top.getElem();
    }

    @Override
    public void push(Object elem) {
        //元素压栈
        Node newNode = new Node(elem,top);
        top = newNode;//修改栈顶指针
        size++;//修改栈中元素个数
    }

    @Override
    public Object pop() {
        if(isEmpty())
        {
            System.out.println("栈为空");
            return null;            
        }
        Object elem = top.getElem();
        top = top.getNext();
        size--;
        return elem;
    }

}