使用JAVA实现栈的数据结构

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

一、栈的结构

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

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

1.给栈添加元素

给栈添加元素

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

从栈中删除元素

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

二、通过数组实现栈

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

1.入栈

在栈尾添加节点

入栈

2.出栈

出栈

弹出栈尾元素节点

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

三、通过链表实现栈

1.入栈

通过链表实现入栈

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

通过链表实现出栈

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