数据结构栈之java实现

栈：是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶，另一端为栈底。当表中没有元素时成为空栈。（LIFO）后进先出
栈的基本操作：

initStack() //初始化
clearStack() //清空栈
stackEmpty() //判断栈是否为空
stackFull() //判断栈是否满栈
getTop() //获取栈顶元素
push() //从栈顶压入一个元素
pop() //从栈顶删除（取出）一个元素
stackLength() //计算堆栈中元素的个数

顺序栈：顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top来动态地指示栈顶元素的顺序栈中的位置。通常以top=0表示空栈。（java中使可用数组实现栈的基本操作）
链栈：采用链表作为存储结构实现的栈。为便于操作，采用带头结点的单链表实现栈。（java中使用LinkedArray 可以实现栈的基本操作，java也已经有相应的Stack类及其方法）
顺序栈和链栈的比较：
实现链式栈和顺序栈的操作都是需要常数时间，即时间复杂度为O（1），主要从空间和时间两个方面考虑。初始时，顺序堆栈必须说明一个固定的长度，当堆栈不够满时，造成一些空间的浪费；而链式堆栈的长度可变则使长度不需要预先设定，动态增减，相对比较节省空间，但是在每个节点中设置了一个指针域，从而产生了结构开销。
具体demo实现:

/**
 * Created by g-Linlf on 2017/5/26.
 * <p>
 * 方法一使用LinkedList实现栈（链栈）
 * (类似链表的栈实现，因为链表不用担心容量的问题)
 * 方法二使用数组实现（顺序栈）
 * 有容量限制。
 **/
public class TestStack {
    public static void main(String args[]) {
        LinkedListStack stack = new LinkedListStack();
        stack.push(1);
        System.out.println(stack.size());
        System.out.println(stack.peek());
        System.out.println(stack.pop());
        System.out.println(stack.size());
        System.out.println(stack.empty());
        //java 已经实现了Stack类extends Vector
        Stack stack1 = new Stack();
        stack1.push(2);
        System.out.println(stack1.size());
        System.out.println(stack1.peek());
        System.out.println(stack1.pop());
        System.out.println(stack1.size());
        System.out.println(stack1.empty());
        System.out.println("---------------------");
        //    测试数组实现 栈大小固定
        ArrayStack myStack = new ArrayStack(3);
        //myStack.push(3);
        //myStack.push(3);
        //myStack.push(3);
        //myStack.push(3);
        System.out.println(myStack.size());
        System.out.println(myStack.peek());
        System.out.println(myStack.pop());
        System.out.println(myStack.empty());
    }
}
//使用数组实现
class ArrayStack {
    private int top;
    private int[] data;
    private int maxSize;
    public ArrayStack(int cap) {
        data = new int[cap];
        maxSize = cap - 1;
        top = -1;
    }
    public int size() {
        return top+1;
    }
    public boolean push(int value) {
        if (top == maxSize) {
            return false;
        } else {
            data[++top] = value;
            return true;
        }
    }
    public int pop() {
        if (top == -1) {
            return -1;
        } else {
            return data[top--];
        }
    }
    //获得栈顶元素
    public int peek() {
        if (top == -1) {
            return -1;
        } else {
            return data[top];
        }
    }
    public boolean empty() {
        if (top == -1) {
            return true;
        } else {
            return false;
        }
    }
}
//使用LinkedList实现
class LinkedListStack {
    private LinkedList linkedList = new LinkedList();
    //进栈
    public void push(Object obj) {
        linkedList.addFirst(obj);
    }
    //出站 移除第一个元素并返回
    public Object pop() {
        return linkedList.removeFirst();
    }
    //获得第一个元素（栈顶元素）
    public Object peek() {
        return linkedList.getFirst();
    }
    public boolean empty() {
        return linkedList.isEmpty();
    }
    public int size() {
        return linkedList.size();
    }
}

数据结构 栈 之java实现

数据结构栈之java实现