堆栈的创建Java实现

青旅半醒 2022-03-26 10:49 108阅读 0赞

**关键词：**结点类，堆栈类，栈顶指针

**1.结点类的设计**

和单链表结点类的设计是类似的的

class StackNode {
    	int data;//数据域
    	StackNode next;//指针域
    }

**2.链式堆栈类的设计(基于链表实现)**

class LinStack {
    	private StackNode top;//栈顶指针
    	
    	public LinStack(){//初始化，栈顶为空表示空栈
    		top = null;
      	}
    	public void clear(){
    		top = null;
      	}
    	public boolean isEmpty(){
        	        return top==null;
    	}
    	public void push(StackNode node){
    		node.next = top;
    		top = node;
    	}
    	public int pop(){
    		if(isEmpty())
    			System.out.println("错误，当前栈是空的");
    		int data = top.data;
    		top = top.next;//修改栈顶指针
    		return data;//返回出栈结点的数据域
    	}
    	public int getTop(){
    		if (isEmpty())
    			System.out.println("错误，当前栈是空的");
    		return top.data;
    	}
    }

**3.顺序堆栈类的设计（基于数组实现） **

class SeqList{
    	private StackNode[] array;//保存结点的数组
    	private int top;//栈顶指针，也表示当前栈中结点个数
    	
    	public SeqList(){//默认初始化
    		array  = new StackNode[10];
    		top = 0
    	}
    	public SeqList(int MaxSize){//以指定大小初始化
    		array  = new StackNode[MaxSize];
    		top = 0;
    	}
    	public boolean isEmpty(){
    		return top ==0;
    	}
    	public int getTop(){
    		return array[top].data;
    	}
    	public void push(StackNode node){
    		if(top == array.length){
    			System.out.println("栈满，无法入栈");
    			return;
    		}
    		node.next = array[top];
    		top++;
    		array[top] = node;
    	}
    	public int pop(){
    		if(isEmpty()){
    			System.out.println("错误，当前栈是空的");
    			return 0;
    		}
    		int data = array[top].data;
    		array[top] = null;
    		top--;
    		return data;
    	}
    	public void clear(){
    		for(int i=0; i<top; i++){
    			pop();
    		}
    	}
    }