首页 > > 程序设计 > Java技术 >

栈的实现

2019-01-01 23:18:49来源：博客园阅读 ()

栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。
栈的特性：后进先出

栈主要分为两类：

静态栈
动态栈

【静态栈】

静态栈的核心是数组，类似于一个连续内存的数组，我们只能操作其栈顶元素。

【动态栈】

动态栈的核心是链表，在内存中可以不连续，我们只能操作其栈顶结点。

以下代码是用链表实现的动态栈：

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 }