栈的Java实现和栈的应用举例

栈的实现

我们提供的服务有：网站设计制作、成都做网站、微信公众号开发、网站优化、网站认证、应城ssl等。为上千余家企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务，是有科学管理、有技术的应城网站制作公司

栈是一种先进后出的数据结构, 首先定义了栈需要实现的接口：

 
 
 
    
  
  
  
  1. public interface MyStack {  
    2. 
  
  
  
  2.     /**  
    3. 
  
  
  
  3.      * 判断栈是否为空  
    4. 
  
  
  
  4.      */ 
    5. 
  
  
  
  5.     boolean isEmpty();  
    6. 
  
  
  
  6.     /**  
    7. 
  
  
  
  7.      * 清空栈  
    8. 
  
  
  
  8.      */ 
    9. 
  
  
  
  9.     void clear();  
    10. 
  
  
  
  10.     /**  
    11. 
  
  
  
  11.      * 栈的长度  
    12. 
  
  
  
  12.      */ 
    13. 
  
  
  
  13.     int length();  
    14. 
  
  
  
  14.     /**  
    15. 
  
  
  
  15.      * 数据入栈  
    16. 
  
  
  
  16.      */ 
    17. 
  
  
  
  17.     boolean push(T data);  
    18. 
  
  
  
  18.     /**  
    19. 
  
  
  
  19.      * 数据出栈  
    20. 
  
  
  
  20.      */ 
    21. 
  
  
  
  21.     T pop();  
    22. 
  
  
  
  22. } 
    23.

栈的数组实现，底层使用数组：

 
 
 
    
  
  
  
  1. public class MyArrayStack implements MyStack {  
    2. 
  
  
  
  2.     private Object[] objs = new Object[16];  
    3. 
  
  
  
  3.     private int size = 0;  
    4. 
  
  
  
  4.  
    5. 
  
  
  
  5.     @Override 
    6. 
  
  
  
  6.     public boolean isEmpty() {  
    7. 
  
  
  
  7.         return size == 0;  
    8. 
  
  
  
  8.     }  
    9. 
  
  
  
  9.  
    10. 
  
  
  
  10.     @Override 
    11. 
  
  
  
  11.     public void clear() {  
    12. 
  
  
  
  12.         // 将数组中的数据置为null, 方便GC进行回收  
    13. 
  
  
  
  13.         for (int i = 0; i < size; i++) {  
    14. 
  
  
  
  14.             objs[size] = null;  
    15. 
  
  
  
  15.         }  
    16. 
  
  
  
  16.         size = 0;  
    17. 
  
  
  
  17.     }  
    18. 
  
  
  
  18.  
    19. 
  
  
  
  19.     @Override 
    20. 
  
  
  
  20.     public int length() {  
    21. 
  
  
  
  21.         return size;  
    22. 
  
  
  
  22.     }  
    23. 
  
  
  
  23.  
    24. 
  
  
  
  24.     @Override 
    25. 
  
  
  
  25.     public boolean push(T data) {  
    26. 
  
  
  
  26.         // 判断是否需要进行数组扩容  
    27. 
  
  
  
  27.         if (size >= objs.length) {  
    28. 
  
  
  
  28.             resize();  
    29. 
  
  
  
  29.         }  
    30. 
  
  
  
  30.         objs[size++] = data;  
    31. 
  
  
  
  31.         return true;  
    32. 
  
  
  
  32.     }  
    33. 
  
  
  
  33.  
    34. 
  
  
  
  34.     /**  
    35. 
  
  
  
  35.      * 数组扩容  
    36. 
  
  
  
  36.      */ 
    37. 
  
  
  
  37.     private void resize() {  
    38. 
  
  
  
  38.         Object[] temp = new Object[objs.length * 3 / 2 + 1];  
    39. 
  
  
  
  39.         for (int i = 0; i < size; i++) {  
    40. 
  
  
  
  40.             temp[i] = objs[i];  
    41. 
  
  
  
  41.             objs[i] = null;  
    42. 
  
  
  
  42.         }  
    43. 
  
  
  
  43.         objs = temp;  
    44. 
  
  
  
  44.     }  
    45. 
  
  
  
  45.  
    46. 
  
  
  
  46.     @SuppressWarnings("unchecked")  
    47. 
  
  
  
  47.     @Override 
    48. 
  
  
  
  48.     public T pop() {  
    49. 
  
  
  
  49.         if (size == 0) {  
    50. 
  
  
  
  50.             return null;  
    51. 
  
  
  
  51.         }  
    52. 
  
  
  
  52.         return (T) objs[--size];  
    53. 
  
  
  
  53.     }  
    54. 
  
  
  
  54.  
    55. 
  
  
  
  55.     @Override 
    56. 
  
  
  
  56.     public String toString() {  
    57. 
  
  
  
  57.         StringBuilder sb = new StringBuilder();  
    58. 
  
  
  
  58.         sb.append("MyArrayStack: [");  
    59. 
  
  
  
  59.         for (int i = 0; i < size; i++) {  
    60. 
  
  
  
  60.             sb.append(objs[i].toString());  
    61. 
  
  
  
  61.             if (i != size - 1) {  
    62. 
  
  
  
  62.                 sb.append(", ");  
    63. 
  
  
  
  63.             }  
    64. 
  
  
  
  64.         }  
    65. 
  
  
  
  65.         sb.append("]");  
    66. 
  
  
  
  66.         return sb.toString();  
    67. 
  
  
  
  67.     }  
    68. 
  
  
  
  68. }   
    69.

栈的链表实现，底层使用链表：

 
 
 
    
  
  
  
  1. public class MyLinkedStack implements MyStack {  
    2. 
  
  
  
  2.     /**  
    3. 
  
  
  
  3.      * 栈顶指针  
    4. 
  
  
  
  4.      */ 
    5. 
  
  
  
  5.     private Node top;  
    6. 
  
  
  
  6.     /**  
    7. 
  
  
  
  7.      * 栈的长度  
    8. 
  
  
  
  8.      */ 
    9. 
  
  
  
  9.     private int size;  
    10. 
  
  
  
  10.       
    11. 
  
  
  
  11.     public MyLinkedStack() {  
    12. 
  
  
  
  12.         top = null;  
    13. 
  
  
  
  13.         size = 0;  
    14. 
  
  
  
  14.     }  
    15. 
  
  
  
  15.       
    16. 
  
  
  
  16.     @Override 
    17. 
  
  
  
  17.     public boolean isEmpty() {  
    18. 
  
  
  
  18.         return size == 0;  
    19. 
  
  
  
  19.     }  
    20. 
  
  
  
  20.       
    21. 
  
  
  
  21.     @Override 
    22. 
  
  
  
  22.     public void clear() {  
    23. 
  
  
  
  23.         top = null;  
    24. 
  
  
  
  24.         size = 0;  
    25. 
  
  
  
  25.     }  
    26. 
  
  
  
  26.       
    27. 
  
  
  
  27.     @Override 
    28. 
  
  
  
  28.     public int length() {  
    29. 
  
  
  
  29.         return size;  
    30. 
  
  
  
  30.     }  
    31. 
  
  
  
  31.       
    32. 
  
  
  
  32.     @Override 
    33. 
  
  
  
  33.     public boolean push(T data) {  
    34. 
  
  
  
  34.         Node node = new Node();  
    35. 
  
  
  
  35.         node.data = data;  
    36. 
  
  
  
  36.         node.pre = top;  
    37. 
  
  
  
  37.         // 改变栈顶指针  
    38. 
  
  
  
  38.         top = node;  
    39. 
  
  
  
  39.         size++;  
    40. 
  
  
  
  40.         return true;  
    41. 
  
  
  
  41.     }  
    42. 
  
  
  
  42.       
    43. 
  
  
  
  43.     @Override 
    44. 
  
  
  
  44.     public T pop() {  
    45. 
  
  
  
  45.         if (top != null) {  
    46. 
  
  
  
  46.             Node node = top;  
    47. 
  
  
  
  47.             // 改变栈顶指针  
    48. 
  
  
  
  48.             top = top.pre;  
    49. 
  
  
  
  49.             size--;  
    50. 
  
  
  
  50.             return node.data;  
    51. 
  
  
  
  51.         }  
    52. 
  
  
  
  52.         return null;  
    53. 
  
  
  
  53.     }  
    54. 
  
  
  
  54.       
    55. 
  
  
  
  55.     /**  
    56. 
  
  
  
  56.      * 将数据封装成结点  
    57. 
  
  
  
  57.      */ 
    58. 
  
  
  
  58.     private final class Node {  
    59. 
  
  
  
  59.         private Node pre;  
    60. 
  
  
  
  60.         private T data;  
    61. 
  
  
  
  61.     }  
    62. 
  
  
  
  62. } 
    63.

两种实现的比较，主要比较数据入栈和出栈的速度：

 
 
 
    
  
  
  
  1. @Test 
    2. 
  
  
  
  2. public void testSpeed() {  
    3. 
  
  
  
  3.     MyStack stack = new MyArrayStack();  
    4. 
  
  
  
  4.     int num = 10000000;  
    5. 
  
  
  
  5.     long start = System.currentTimeMillis();  
    6. 
  
  
  
  6.     for (int i = 0; i < num; i++) {  
    7. 
  
  
  
  7.         stack.push(new Person("xing", 25));  
    8. 
  
  
  
  8.     }  
    9. 
  
  
  
  9.     long temp = System.currentTimeMillis();  
    10. 
  
  
  
  10.     System.out.println("push time: " + (temp - start));  
    11. 
  
  
  
  11.     while (stack.pop() != null)  
    12. 
  
  
  
  12.         ;  
    13. 
  
  
  
  13.     System.out.println("pop time: " + (System.currentTimeMillis() - temp));  
    14. 
  
  
  
  14. } 
    15.

MyArrayStack中入栈和出栈10,000,000条数据的时间：

push time：936

pop time：47

将MyArrayStack改为MyLinkedStack后入栈和出栈的时间：

push time：936

pop time：126

可见两者的入栈速度差不多，出栈速度MyArrayStack则有明显的优势。

为什么测试结果是这样的？可能有些朋友的想法是数组实现的栈应该具有更快的遍历速度，但增删速度应该比不上链表实现的栈才对。但是栈中数据的增删具有特殊性：只在栈顶入栈和出栈。也就是说数组实现的栈在增加和删除元素时并不需要移动大量的元素，只是在数组扩容时需要进行复制。而链表实现的栈入栈和出栈时都需要将数据包装成Node或者从Node中取出数据，还需要维护栈顶指针和前驱指针。

栈的应用举例

1. 将10进制正整数num转换为n进制

 
 
 
    
  
  
  
  1. private String conversion(int num, int n) {  
    2. 
  
  
  
  2.     MyStack myStack = new MyArrayStack();  
    3. 
  
  
  
  3.     Integer result = num;  
    4. 
  
  
  
  4.     while (true) {  
    5. 
  
  
  
  5.         // 将余数入栈  
    6. 
  
  
  
  6.         myStack.push(result % n);  
    7. 
  
  
  
  7.         result = result / n;  
    8. 
  
  
  
  8.         if (result == 0) {  
    9. 
  
  
  
  9.             break;  
    10. 
  
  
  
  10.         }  
    11. 
  
  
  
  11.     }  
    12. 
  
  
  
  12.     StringBuilder sb = new StringBuilder();  
    13. 
  
  
  
  13.     // 按出栈的顺序倒序排列即可  
    14. 
  
  
  
  14.     while ((result = myStack.pop()) != null) {  
    15. 
  
  
  
  15.         sb.append(result);  
    16. 
  
  
  
  16.     }  
    17. 
  
  
  
  17.     return sb.toString();  
    18. 
  
  
  
  18. } 
    19.

2. 检验符号是否匹配. '['和']', '('和')'成对出现时字符串合法. 例如"[][]()", "[[([]([])()[])]]"是合法的; "([(])", "[())"是不合法的。

遍历字符串的每一个char, 将char与栈顶元素比较. 如果char和栈顶元素配对, 则char不入栈, 否则将char入栈. 当遍历完成时栈为空说明字符串是合法的。

 
 
 
    
  
  
  
  1. public boolean isMatch(String str) {  
    2. 
  
  
  
  2.     MyStack myStack = new MyArrayStack();  
    3. 
  
  
  
  3.     char[] arr = str.toCharArray();  
    4. 
  
  
  
  4.     for (char c : arr) {  
    5. 
  
  
  
  5.         Character temp = myStack.pop();  
    6. 
  
  
  
  6.         // 栈为空时只将c入栈  
    7. 
  
  
  
  7.         if (temp == null) {  
    8. 
  
  
  
  8.             myStack.push(c);  
    9. 
  
  
  
  9.         }  
    10. 
  
  
  
  10.         // 配对时c不入栈  
    11. 
  
  
  
  11.         else if (temp == '[' && c == ']') {  
    12. 
  
  
  
  12.         }   
    13. 
  
  
  
  13.         // 配对时c不入栈  
    14. 
  
  
  
  14.         else if (temp == '(' && c == ')') {  
    15. 
  
  
  
  15.         }   
    16. 
  
  
  
  16.         // 不配对时c入栈  
    17. 
  
  
  
  17.         else {  
    18. 
  
  
  
  18.             myStack.push(temp);  
    19. 
  
  
  
  19.             myStack.push(c);  
    20. 
  
  
  
  20.         }  
    21. 
  
  
  
  21.     }  
    22. 
  
  
  
  22.     return myStack.isEmpty();  
    23. 
  
  
  
  23. } 
    24.

3. 行编辑: 输入行中字符'#'表示退格, '@'表示之前的输入全都无效。

使用栈保存输入的字符, 如果遇到'#'就将栈顶出栈, 如果遇到@就清空栈. 输入完成时将栈中所有字符出栈后反转就是输入的结果：

 
 
 
    
  
  
  
  1. private String lineEdit(String input) {  
    2. 
  
  
  
  2.     MyStack myStack = new MyArrayStack();  
    3. 
  
  
  
  3.     char[] arr = input.toCharArray();  
    4. 
  
  
  
  4.     for (char c : arr) {  
    5. 
  
  
  
  5.         if (c == '#') {  
    6. 
  
  
  
  6.             myStack.pop();  
    7. 
  
  
  
  7.         } else if (c == '@') {  
    8. 
  
  
  
  8.             myStack.clear();  
    9. 
  
  
  
  9.         } else {  
    10. 
  
  
  
  10.             myStack.push(c);  
    11. 
  
  
  
  11.         }  
    12. 
  
  
  
  12.     }  
    13. 
  
  
  
  13.       
    14. 
  
  
  
  14.     StringBuilder sb = new StringBuilder();  
    15. 
  
  
  
  15.     Character temp = null;  
    16. 
  
  
  
  16.     while ((temp = myStack.pop()) != null) {  
    17. 
  
  
  
  17.         sb.append(temp);  
    18. 
  
  
  
  18.     }  
    19. 
  
  
  
  19.     // 反转字符串  
    20. 
  
  
  
  20.     sb.reverse();  
    21. 
  
  
  
  21.     return sb.toString();  
    22. 
  
  
  
  22. } 
    23.

当前题目：栈的Java实现和栈的应用举例
当前URL：http://www.shufengxianlan.com/qtweb/news20/114220.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

网站排名知识

同城分类信息

LED亮化工程　　 　画册设计制作　　 　攀枝花网站设计　　 　铁科精智测控　　 　南宁旺客科技　　 　专业网站设计　　 　成都电信服务器托管　　 　成都托管服务器　　 　整合营销　　 　香港虚拟主机空间　　 　全网整合营销　　 　什邡做网站　　 　香港服务器空间　　 　云服务器　　 　香港虚拟主机腾讯云　　 　响应式网站设计　　 　成都发电机维修　　 　雅安做网站　　 　电信成都枢纽中心　　 　成都酒店服定制