java: 数据结构---栈(链表)

浅浅的花香味﹌ 2022-05-20 02:34 238阅读 0赞

链表的结构如下:( 1, head是一个引用地址,  用来指引最新的数据\[ 栈:  先进后出\]  Node newNode=new Node(data);

2,  新加入的数据被封装为Node对象,  若容器为空时, 新node没有下一个;  Node tmp=head;

若容器不为空,则把旧的head当做下一个  newNode.next=tmp;

3,  head引用指向最新的node    head=newNode; )

push()----->添加

![70][]

pop() 删除--->

![70 1][]

/**
     * 代码实现:  栈(链表) 
     * @author wang
     *
     */
    public class MyLinkedStack {
    	//属性--内部类(保存顺序): 对象
    	private class Node{
    		int data;
    		Node next;
    		
    		public Node(int data) {
    			this.data=data;
    		}
    	}
    	Node head;//对外提供的访问: 对象接口
    	int size;//记录容器大小
    	
    	//方法: 添加(head), 删除(head)
    	public void push(int data) {
    		Node tmp=head;
    		if(head==null) {
    			head=new Node(data);
    		}else {
    			Node newNode=new Node(data);
    			newNode.next=tmp;//新节点.next-->原head 
    			head=newNode;	//新节点--->    head
    		}
    		size++;//容器记录+1
    	}
    	
    	public int pop() throws Exception {
    		if(size==0) {
    			throw new Exception("nothing in Stack...");
    		}else {
    			//取出head: 删除
    			Node tmp=head;
    			head=tmp.next;//原head.nex---->head:  删除操作
    			
    			size--;
    			int res=tmp.data;
    			tmp=null;//清空原head
    			
    			return res ;
    		}
    		
    	}//pop
    }

测试类

public class Test {
    	public static void main(String[] args) throws Exception {
    		//链表stack
    		MyLinkedStack stack = new MyLinkedStack();
    		
    		stack.push(1);
    		stack.push(2);
    		stack.push(3);
    		
    		System.out.println(stack.pop());//3
    		System.out.println(stack.pop());//2
    		System.out.println(stack.pop());//1
    		//System.out.println(stack.pop());//java.lang.Exception: nothing in Stack...
    		
    		stack.push(4);
    		stack.push(5);
    		stack.push(6);
    		
    		System.out.println(stack.pop());//6
    		System.out.println(stack.pop());//5
    		System.out.println(stack.pop());//4
    	}
    
    }

[70]: /images/20220520/7d59f6926649473fb504b240f62a3c3b.png
[70 1]: /images/20220520/2d64911511114c088bcf93952d21e624.png