栈的两种实现
静态栈:数组
动态栈:链表
栈的基本操作
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
}
}