[数据结构]Java 基于链表和泛型的栈结构-白红宇

[数据结构]Java 基于链表和泛型的栈结构

阅读量：6463 次

发布时间：2019-06-23

本文共 2997 字，大约阅读时间需要 9 分钟。

大致测试了下似乎没问题、姑且不管效率问题、仅仅演示逻辑、仅以记录、

1 package com.study;   2   3 import java.util.EmptyStackException;   4 import java.util.Stack;   5   6 class Linked
     
       {
     7     private Linked
      
        before = null; // 前驱   8     private Linked
       
         after = null; // 后继   9     private T obj;  10  11     public boolean hasNext() {
    12         return after != null;  13     }  14  15     public boolean hasLast() {
    16         return null != before;  17     }  18  19     public Linked
        
          getBefore() {
    20         return before;  21     }  22  23     public void setBefore(Linked
         
           before) {
    24         this.before = before;  25     }  26  27     public Linked
          
            getAfter() { 28 return after; 29 } 30 31 public void setAfter(Linked
           
             after) { 32 this.after = after; 33 } 34 35 @Override 36 public int hashCode() { 37 final int prime = 31; 38 int result = 1; 39 result = prime * result + ((obj == null) ? 0 : obj.hashCode()); 40 return result; 41 } 42 43 @Override 44 public boolean equals(Object obj) { 45 if (this == obj) 46 return true; 47 if (obj == null) 48 return false; 49 if (getClass() != obj.getClass()) 50 return false; 51 Linked other = (Linked) obj; 52 if (this.obj == null) { 53 if (other.obj != null) 54 return false; 55 } else if (!this.obj.equals(other.obj)) 56 return false; 57 return true; 58 } 59 60 public T getObj() { 61 return obj; 62 } 63 64 public void setObj(T obj) { 65 this.obj = obj; 66 } 67 68 public Linked(T obj) { 69 this.obj = obj; 70 } 71 } 72 73 public class StackDemo2
            
              extends Stack
             
               { 74 75 private Linked
              
                item = null; // 最后一个元素 76 private int position = -1; 77 78 @Override 79 public K push(K item) { 80 // TODO Auto-generated method stub 81 if (null == this.item) { 82 this.item = new Linked
               
                (item); 83 } else { 84 Linked
                
                  tmp = new Linked
                 
                  (item); 85 this.item.setAfter(tmp); 86 tmp.setBefore(this.item); 87 this.item = tmp; 88 } 89 position++; 90 return item; 91 } 92 93 @Override 94 public synchronized K pop() { 95 if (this.empty()) 96 throw new EmptyStackException(); 97 K item = this.item.getObj(); 98 99 this.item.setObj(null); 100 this.item = this.item.getBefore(); 101 this.item.setAfter(null); 102 103 position--; 104 105 return item; 106 } 107 108 @Override 109 public synchronized K peek() { 110 if (this.empty()) 111 throw new EmptyStackException(); 112 113 return this.item.getObj(); 114 } 115 116 @Override 117 public boolean empty() { 118 // TODO Auto-generated method stub 119 return this.item == null || this.item.getObj() == null; 120 } 121 122 @Override 123 public synchronized int search(Object o) { 124 return getIndex(o, this.item, 0); 125 } 126 127 private int getIndex(Object o, Linked
                  
                    L, int inx) { 128 if (L.getObj().equals(o)) 129 return position - inx + 1; 130 131 if (L.hasLast()) 132 return getIndex(o, L.getBefore(), inx + 1); 133 134 return -1; 135 } 136 }