使用JAVA实现栈的数据结构

发表于   |   分类于 左手代码 计算机基础   |   阅读(114)   |   评论(92)

栈，是一种特殊的链表，是一种只能在表尾进行操作的特殊链表，是一种后进先出的结构。

一、栈的结构

栈本质是一种链表，因此栈存储结构与链表一致，形象图如下：

整个栈像我们日常使用的行礼箱，它是一层一层的放置东西，每件物品相当于一个栈元素，我们如果想放东西，只能从下面往上面放，最后放的东西永远在最上面，如果拿东西，也是从第上面开始拿

1.给栈添加元素

给栈添加元素

  • 就像往箱子里面放东西，后放的东西总是在最上面
2.从栈里面删除元素

从栈中删除元素

  • 就像拿东西，东西总是从上面开始拿

二、通过数组实现栈

通过数组来实现栈是比较简单的，因为栈只操作表尾，即数组的最后一个元素，其主要操作主要是入栈和出栈。

1.入栈

在栈尾添加节点

入栈

2.出栈

出栈

弹出栈尾元素节点

3.通过数组来实现栈这种数据结构
  1. package com.shixinke.demo.dataStruct;
  3. public class MyArrayStack<E> {
  4.     //栈的大小
  5.     private int size;
  6.     //栈存储的元素节点
  7.     private E[] data;
  8.     private static final int DEFAULT_CAPACITY = 10;
  10.     public MyArrayStack() {
  11.         clearStack(DEFAULT_CAPACITY);
  12.     }
  14.     public MyArrayStack(int capacity) {
  15.         clearStack(capacity);
  16.     }
  18.     public void clear() {
  19.         clearStack(DEFAULT_CAPACITY);
  20.     }
  22.     /**
  23.      * 清除栈
  24.      * @param capacity
  25.      */
  26.     private void clearStack(int capacity) {
  27.         this.size = 0;
  28.         ensureCapacity(capacity);
  29.     }
  31.     /**
  32.      * 获取栈的大小
  33.      * @return
  34.      */
  35.     public int size() {
  36.         return this.size;
  37.     }
  39.     /**
  40.      * 是否为空栈
  41.      * @return
  42.      */
  43.     public boolean isEmpty() {
  44.         return this.size == 0;
  45.     }
  47.     /**
  48.      * 栈是否包含某个元素
  49.      * @param value
  50.      * @return
  51.      */
  52.     public boolean contains(E value) {
  53.         return indexOf(value) == -1 ? false : true;
  54.     }
  56.     /**
  57.      * 获取某个元素在栈中的位置(第一次)
  58.      * @param value
  59.      * @return
  60.      */
  61.     public int indexOf(E value) {
  62.         for (int i = 0; i< this.size; i++) {
  63.             if (value.equals(this.data[i])) {
  64.                 return i;
  65.             }
  66.         }
  67.         return -1;
  68.     }
  70.     /**
  71.      * 获取某个元素在栈中最后一次出现的位置　
  72.      * @param value
  73.      * @return
  74.      */
  75.     public int lastIndexOf(E value) {
  76.         for (int i = this.size - 1; i >= 0; i--) {
  77.             if (value.equals(this.data[i])) {
  78.                 return i;
  79.             }
  80.         }
  81.         return -1;
  82.     }
  84.     /**
  85.      * 向栈添加元素
  86.      * @param value
  87.      * @return
  88.      */
  89.     public boolean push(E value) {
  90.         if (this.data.length == this.size) {
  91.             ensureCapacity(this.size * 2 + 1);
  92.         }
  93.         this.data[size] = value;
  94.         this.size ++;
  95.         return true;
  96.     }
  98.     /**
  99.      * 从栈中取出元素
  100.      * @return
  101.      */
  102.     public E pop() {
  103.         if (this.size == 0) {
  104.             return null;
  105.         }
  106.         E value = this.data[this.size - 1];
  107.         this.size --;
  108.         return value;
  109.     }
  111.     /**
  112.      * 给栈中某个位置设置值
  113.      * @param index
  114.      * @param value
  115.      */
  116.     public void set(int index, E value) {
  117.         if (index > this.size) {
  118.             throw new IndexOutOfBoundsException();
  119.         }
  120.         this.data[index] = value;
  121.     }
  123.     /**
  124.      * 获取某个位置的元素
  125.      * @param index
  126.      * @return
  127.      */
  128.     public E get(int index) {
  129.         if (index > this.size) {
  130.             throw new IndexOutOfBoundsException();
  131.         }
  132.         return this.data[index];
  133.     }
  136.     /**
  137.      * 栈扩容
  138.      * @param capacity
  139.      */
  140.     private void ensureCapacity(int capacity) {
  141.         //新容量比原表大小还小，直接返回，不需要扩容
  142.         if (capacity < this.size) {
  143.             return;
  144.         }
  145.         E[] oldData = data;
  146.         data = (E[]) new Object[capacity];
  147.         for (int i = 0; i < this.size; i++) {
  148.             data[i] = oldData[i];
  149.         }
  150.     }
  152.     /**
  153.     * 打印栈的元素
  154.     */
  155.     public void print() {
  156.         System.out.println();
  157.         System.out.print("[");
  158.         for (int i = 0; i< this.size; i++) {
  159.             System.out.print(this.data[i]);
  160.             if (i != this.size - 1) {
  161.                 System.out.print(",");
  162.             }
  163.         }
  164.         System.out.println("]");
  165.         System.out.println();
  166.     }
  168.     /**
  169.     * 演示使用(代码可移动到测试代码中)
  170.     */
  171.     public static void main(String[] args) {
  172.         MyArrayStack<String> books = new MyArrayStack<String>(5);
  173.         books.push("JAVA编程");
  174.         books.push("网络安全");
  175.         books.push("计算机网络");
  176.         books.push("计算机文化基础");
  177.         books.print();      //[JAVA编程,网络安全,计算机网络,计算机文化基础]
  178.         String lastBook = books.pop();
  179.         System.out.println(lastBook);  //计算机文化基础
  180.         books.print();                 //[JAVA编程,网络安全,计算机网络]
  181.         System.out.println(books.size());  //3
  182.         System.out.println(books.contains("计算机网络")); //true
  183.         System.out.println(books.indexOf("计算机网络"));  //2
  184.     }
  185. }

三、通过链表实现栈

1.入栈

通过链表实现入栈

  • 生成一个新的节点(它的prev指针指向表尾节点，next指针指向null)
  • 将原表尾节点的next指针指向新表尾节点
  • 将新表尾指向新的表尾节点
  • 表节点个数加1
2.出栈

通过链表实现出栈

  • 将原表尾节点的前一个节点的next指向指向null
  • 将表尾指向原节点的前一个节点
  • 清除了原表尾的资源，内容和prev指针都为null
  • 表节点个数减1
3.通过链表实现栈
  1. package com.shixinke.demo.dataStruct;
  3. public class MyLinkedStack<E> {
  4.     private int size;
  5.     private Node<E> first;
  6.     private Node<E> last;
  8.     public MyLinkedStack() {
  9.         clearStack();
  10.     }
  12.     public void clear() {
  13.         clearStack();
  14.     }
  16.     /**
  17.      * 清除栈的资源
  18.      */
  19.     public void clearStack() {
  20.         this.size = 0;
  21.         this.first = null;
  22.         this.last = null;
  23.     }
  25.     /**
  26.      * 入栈
  27.      * @param value
  28.      * @return
  29.      */
  30.     public boolean push(E value) {
  31.         //1.生成新的表尾节点(prev指针指向原表尾，next指针指向null)
  32.         Node<E> node = new Node<E>(value, this.last, null);
  33.         //2.如果原表尾为null，即原表为空表，则将表头指向新添加的表尾节点
  34.         if (this.last == null) {
  35.             this.first = node;
  36.         } else {
  37.             //3.如果表尾节点存在，则将原表尾节点指向新插入的表尾节点
  38.             this.last.next = node;
  39.         }
  40.         //4.将新表尾指向新的插入的表尾节点
  41.         this.last = node;
  42.         //5.增加表的节点个数
  43.         this.size ++;
  44.         return true;
  45.     }
  47.     /**
  48.      * 出栈
  49.      * @return
  50.      */
  51.     public E pop() {
  52.         //1.如果原表是空表，直接返回null
  53.         if (this.last == null) {
  54.             return null;
  55.         }
  56.         //2.获取原表尾节点
  57.         Node<E> oldNode = this.last;
  58.         //3.将表尾节点指向表尾节点的前一个节点
  59.         this.last = this.last.prev;
  60.         //4.获取原表尾节点的数据
  61.         E value = oldNode.data;
  62.         //5.删除原表尾节点上的数据和指针
  63.         oldNode.prev = null;
  64.         oldNode.next = null;
  65.         oldNode.data = null;
  66.         //6.减少表的元素个数
  67.         size --;
  68.         return value;
  69.     }
  71.     public int size() {
  72.         return this.size;
  73.     }
  75.     public boolean isEmpty() {
  76.         return this.size == 0;
  77.     }
  79.     public boolean contains(E value) {
  80.         return indexOf(value) >= 0 ? true :false;
  81.     }
  83.     public int indexOf(E value) {
  84.         if (value == null) {
  85.             Node<E> node = first;
  86.             for (int i = 0; i< this.size; i++) {
  87.                 if (node.data == null) {
  88.                     return i;
  89.                 }
  90.                 node = node.next;
  91.             }
  92.         } else {
  93.             Node<E> node = first;
  94.             for (int i = 0; i< this.size; i++) {
  95.                 if (value.equals(node.data)) {
  96.                     return i;
  97.                 }
  98.                 node = node.next;
  99.             }
  100.         }
  101.         return -1;
  102.     }
  104.     public int lastIndexOf(E value) {
  105.         if (value == null) {
  106.             Node<E> node = first;
  107.             for (int i = this.size - 1; i >= 0; i--) {
  108.                 if (node.data == null) {
  109.                     return i;
  110.                 }
  111.                 node = node.next;
  112.             }
  113.         } else {
  114.             Node<E> node = first;
  115.             for (int i = this.size - 1; i >= 0; i--) {
  116.                 if (value.equals(node.data)) {
  117.                     return i;
  118.                 }
  119.                 node = node.next;
  120.             }
  121.         }
  122.         return -1;
  123.     }
  125.     private class Node<E> {
  126.         private E data;
  127.         private Node<E> prev;
  128.         private Node<E> next;
  130.         public Node(E value, Node<E> prev, Node<E> next) {
  131.             this.data = value;
  132.             this.prev = prev;
  133.             this.next = next;
  134.         }
  135.     }
  137.     public void print() {
  138.         System.out.println();
  139.         System.out.print("[");
  140.         Node<E> p = first;
  141.         for (int i = 0; i < size; i++) {
  142.             System.out.print(p.data);
  143.             p = p.next;
  144.             if (i != size -1) {
  145.                 System.out.print(",");
  146.             }
  147.         }
  148.         System.out.print("]");
  149.         System.out.println();
  152.     }
  154.     public static void main(String[] args) {
  155.         MyLinkedStack<String> books = new MyLinkedStack<String>();
  156.         books.push("JAVA编程");
  157.         books.push("网络安全");
  158.         books.push("计算机网络");
  159.         books.push("计算机文化基础");
  161.         books.print();                    //[JAVA编程,网络安全,计算机网络,计算机文化基础]
  162.         String borrowBook = books.pop();
  163.         System.out.println(borrowBook);   //计算机文化基础
  164.         books.print();                    //[JAVA编程,网络安全,计算机网络]
  166.         System.out.println(books.indexOf("网络安全"));      //1
  167.         System.out.println(books.contains("JAVA编程"));    //true
  169.         books.clear();
  170.         System.out.println(books.isEmpty());              //true
  171.         books.print();                                    //[]
  172.     }
  173. }

专题 更多...

分类 更多...

展开

标签 更多...

归档 更多...

展开