栈的两种实现

image

静态栈:数组

动态栈:链表

栈的基本操作

package dataStructure.stack;

import dataStructure.list.ListNode;

/**
 * 栈的基本操作
 */
public class MyStackOperate {

    /**
     * 入栈
     */
    public static void pushStack(MyStack stack, int value){
        //头结点插入一个元素
        ListNode newHead = new ListNode(value);

        newHead.next = stack.stackTop;
        stack.stackTop = newHead;
    }

    /**
     * 是否是空栈
     */
    public static boolean isEmpty(MyStack stack){
        //若头结点和尾结点相等,则是空栈,否则则不是
        return stack.stackTop == stack.stackBottom;
    }

    /**
     * 出栈
     */
    public static void popStack(MyStack stack){
        //若是空栈,则返回
        if(isEmpty(stack)){
           return;
        }

        //若不是,则头结点删除
        System.out.println(stack.stackTop);
        stack.stackTop = stack.stackTop.next;
    }

    /**
     * 清空栈
     */
    public static void clear(MyStack stack){
        stack.stackTop = null;
        stack.stackBottom = stack.stackTop;
    }

    /**
     * 遍历栈
     */
    public static void traverse(MyStack stack){
        ListNode currentNode = stack.stackTop;
        while (currentNode != stack.stackBottom){
            System.out.print(currentNode.value + "  ");

            currentNode = currentNode.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(0);
        MyStack myStack = new MyStack(node1,node1);

        System.out.println(isEmpty(myStack));//true

        pushStack(myStack,1 );
        pushStack(myStack,2 );
        pushStack(myStack,3 );

        traverse(myStack);//3 2 1

        popStack(myStack);
        traverse(myStack);//2 1
        System.out.println(isEmpty(myStack));//false

        clear(myStack);

        System.out.println(isEmpty(myStack));//true
    }
}