棧的實現

棧是一種特殊的線性表，僅能線上性表的一端操作，棧頂允許操作，棧底不允許操作。
棧的特性：後進先出

棧主要分為兩類：

• 靜態棧
• 動態棧

【靜態棧】

靜態棧的核心是數組，類似於一個連續記憶體的數組，我們只能操作其棧頂元素。

【動態棧】

動態棧的核心是鏈表，在記憶體中可以不連續，我們只能操作其棧頂結點。

以下代碼是用鏈表實現的動態棧：

1.雙向鏈表類

  1 public class DoubleLinkedList<T> implements MyList<T>{
  2     protected ListNode<T> first=new ListNode<T>();
  3     protected ListNode<T> last=new ListNode<T>();
  4     private int size=0;
  5     
  6     public DoubleLinkedList()
  7     {
  8         first.next=last;
  9         last.pre=first;
 10     }
 11     
 12     @Override
 13     public void add(T element) {
 14         ListNode<T> newNode=new ListNode<T>(element);
 15         last.pre.next=newNode;
 16         newNode.pre=last.pre;
 17         newNode.next=last;
 18         last.pre=newNode;
 19         size++;
 20     }
 21 
 22     @Override
 23     public void delete(T element) {
 24         ListNode<T> p=first.next;
 25         while(p!=null)
 26         {
 27             if(p.data.equals(element))
 28             {
 29                 p.pre.next=p.next;
 30                 p.next.pre=p.pre;
 31                 size--;
 32                 return ;
 33             }
 34             p=p.next;
 35         }
 36         
 37     }
 38 
 39     @Override
 40     public void delete(int index) {
 41         int i=0;
 42         ListNode<T> p=first.next;
 43         while(p!=last)
 44         {
 45             if(i==index)
 46             {
 47                 p.pre.next=p.next;
 48                 p.next.pre=p.pre;
 49                 p.pre=null;
 50                 p.next=null;
 51                 size--;
 52                 return ;
 53             }
 54             p=p.next;
 55             i++;
 56         }
 57         
 58     }
 59 
 60     @Override
 61     public void update(int index, T newelement) {
 62         int i=0;
 63         ListNode<T> p=first.next;
 64         while(p!=null)
 65         {
 66             if(i==index)
 67             {
 68                 p.data=newelement;
 69             }
 70             p=p.next;
 71             i++;
 72         }
 73         
 74         
 75     }
 76 
 77     @Override
 78     public boolean contains(T element) {
 79         return indexOf(element)>=0;
 80     }
 81 
 82     @Override
 83     public T at(int index) {
 84         int i=0;
 85         ListNode<T> p=first.next;
 86         while(p!=null)
 87         {
 88             if(i==index)
 89             {
 90                 return (T) p.data;
 91             }
 92             p=p.next;
 93             i++;
 94         }
 95         return null;
 96     }
 97 
 98     @Override
 99     public int indexOf(T element) {
100         int i=0;
101         ListNode<T> p=first.next;
102         while(p!=null)
103         {
104             if(p.data.equals(element))
105             {
106                 return i;
107             }
108             p=p.next;
109             i++;
110         }
111         return -1;
112     }
113     
114     @Override
115     public String toString()
116     {
117         StringBuilder sb=new StringBuilder("[");
118         ListNode<T> p=first.next;
119         while(p!=last)
120         {
121             sb.append(p.data+(p.next!=last?",":""));
122             
123             p=p.next;
124         }
125         sb.append("]");
126         return sb.toString();
127     }
128 
129     public int getSize()
130     {
131         return this.size;
132     }
133     
134     public void setSize(int size) {
135         this.size=size;
136     }
137 }

2.雙向鏈表的介面：

 1 public interface MyList<T>{
 2     //新增一個元素
 3     void add(T element);
 4     //刪除與輸入元素相同的元素
 5     void delete(T element);
 6     //根據索引刪除元素
 7     void delete(int index);
 8     //更新元素
 9     void update(int index,T newelement);
10     //查詢1
11     boolean contains(T element);
12     
13     T at(int index);
14     
15     int indexOf(T element);
16 }

3.結點類：

 1 public class ListNode<T> {
 2       T data;
 3       ListNode<T> pre; //前驅結點
 4       ListNode<T> next; //後驅結點
 5     
 6     public ListNode()
 7     {
 8         
 9     }
10     public ListNode(T element)
11     {
12         this.data=element;
13     }
14     
15     
16 }

4.棧的介面

 1 public interface IStack<T>{
 2 
 3     //元素入棧
 4     void push(T e);
 5     
 6     //彈出棧頂
 7     T pop();
 8     
 9     //是否為空
10     boolean isEmpty();
11     
12     //查看棧頂元素
13     T peek();
14     
15     //棧內元素個數 
16     int getSize();
17     
18 }

5.棧類

 1 import java.util.EmptyStackException;
 2 
 3 public class MyStack<T> extends DoubleLinkedList<T> implements IStack<T>{
 4 
 5     @Override
 6     public void push(T e) {
 7         super.add(e);
 8         
 9     }
10 
11     @Override
12     public T pop() {
13         if(getSize()<=0) throw new EmptyStackException();
14         ListNode<T> the=last.pre;
15         T value=(T) the.data;
16         super.delete(getSize()-1);
17         return value;
18         
19     }
20 
21     @Override
22     public boolean isEmpty() {
23         
24         return getSize()>0;
25     }
26     
27     @Override
28     public T peek() {
29         if(getSize()<=0) throw new EmptyStackException();
30         return (T) last.pre.data;
31     }
32 
33     public int getSize()
34     {
35         return super.getSize();
36     }
37 
38     
39 }