当前位置:   article > 正文

数据结构(栈)

数据结构(栈)

一.什么是栈

1.栈的定义

        栈是一种特殊类型的线性表,它的特点是仅允许在其一端进行插入(入栈)和删除(弹出)操作。这一端称为栈顶,而相对的另一端称为栈底。

2.栈的特点

        栈遵循“后进先出”(LIFO)的原则,也就是说新加入的元素总是位于栈顶,先入栈的元素总是最后出栈。

3.基本操作
  • 入栈(Push):将元素推送到栈顶
  • 出栈(Pop):删除栈顶元素

 ① 入栈

② 出栈

二. 栈的基本操作

1.顺序栈

         顺序栈是一种使用数组实现的栈,也称为数组栈。其基本思路是通过数组来存储栈中的元素,并通过栈顶指针指示栈顶元素在数组中的位置。

  • 代码实现
  1. public interface myStack<T>{
  2. // 入栈
  3. void push(T ele);
  4. // 出栈
  5. T pop();
  6. // 查看当前栈顶元素
  7. T peek();
  8. // 判断栈是否为空
  9. boolean isEmpty();
  10. // 获取栈内的元素个数
  11. int getSize();
  12. }
  13. public class MyArray<T> {
  14. private T[] arr;
  15. private int size;
  16. private int capacity; //容积
  17. // 构造方法
  18. public MyArray(int capacity) {
  19. // 入参判断
  20. if (capacity <= 0) {
  21. throw new IllegalArgumentException("输入容积异常!");
  22. }
  23. this.capacity = capacity;
  24. this.size = 0;
  25. this.arr = (T[]) new Object[this.capacity];
  26. }
  27. // 获取元素个数
  28. public int getSize() {
  29. return this.size;
  30. }
  31. // 获取容积
  32. public int getCapacity() {
  33. return this.capacity;
  34. }
  35. // 添加元素
  36. public void add(T item) {
  37. this.arr[this.size] = item;
  38. this.size++;
  39. }
  40. // 向指定位置添加元素
  41. public void addValueByIndex(int index, T value) {
  42. if (index < 0 || index > this.size) {
  43. throw new IllegalArgumentException("索引异常!");
  44. }
  45. if (this.size == this.capacity) {
  46. resize(this.capacity * 2);
  47. }
  48. for (int i = this.size - 1; i >= index; i--) {
  49. this.arr[i + 1] = this.arr[i];
  50. }
  51. this.arr[index] = value;
  52. this.size++;
  53. }
  54. // 扩容
  55. private void resize(int newCapacity) {
  56. T[] newArr = (T[]) new Object[newCapacity];
  57. for (int i = 0; i < this.size; i++) {
  58. newArr[i] = this.arr[i];
  59. }
  60. // 改变容器与容积
  61. this.arr = newArr;
  62. this.capacity = newCapacity;
  63. }
  64. // 判空
  65. public boolean isEmpty() {
  66. return this.size == 0;
  67. }
  68. // 修改元素
  69. public void modifyValueByIndex(int index, T value) {
  70. // 入参判断
  71. if (index < 0 || index > capacity) {
  72. throw new IllegalArgumentException("索引异常!");
  73. }
  74. this.arr[index] = value;
  75. }
  76. // 获取指定位置的值
  77. public T getValueByIndex(int index) {
  78. // 入参判断
  79. if (index < 0 || index > capacity) {
  80. throw new IllegalArgumentException("索引异常!");
  81. }
  82. return this.arr[index];
  83. }
  84. // 查询指定的值在数组中是否存在,存在返回索引,不存在返回-1
  85. public int containsValue(T value) {
  86. for (int i = 0; i < this.size; i++) {
  87. if (value.equals(this.arr[i])) {
  88. return i;
  89. }
  90. }
  91. return -1;
  92. }
  93. // 删除指定位置的元素
  94. public T deleteValueByIndex(int index) {
  95. // 入参判断
  96. if (index < 0 || index > capacity) {
  97. throw new IllegalArgumentException("索引异常");
  98. }
  99. // 1.找到删除的位置的元素
  100. T deValue = this.arr[index];
  101. // 2.将删除元素之后的元素前移
  102. for (int j = index + 1; j < this.size; j++) {
  103. this.arr[j - 1] = this.arr[j];
  104. }
  105. this.size--;
  106. // 判断是否缩容
  107. if (this.size <= this.capacity / 4 && this.capacity / 2 > 0) {
  108. resize(this.capacity / 2);
  109. }
  110. return deValue;
  111. }
  112. public T removeFromLast() {
  113. T delVal = this.arr[this.size - 1];
  114. this.size--;
  115. return delVal;
  116. }
  117. public T getValue() {
  118. return getValueByIndex(this.size - 1);
  119. }
  120. @Override
  121. public String toString() {
  122. StringBuilder sb = new StringBuilder();
  123. sb.append("{");
  124. for (int i = 0; i < this.size; i++) {
  125. sb.append(this.arr[i]);
  126. if (i < this.size - 1) {
  127. sb.append(",");
  128. }
  129. }
  130. sb.append("}");
  131. return sb.toString();
  132. }
  133. }
  134. // 以数组为栈的数据存储结构
  135. public class ArrStack<T> implements myStack<T> {
  136. private MyArray<T> data;
  137. int size;
  138. public ArrStack() {
  139. this.data = new MyArray<>(100);
  140. this.size = 0;
  141. }
  142. @Override
  143. public void push(T ele) {
  144. this.data.add(ele);
  145. this.size++;
  146. }
  147. @Override
  148. public T pop() {
  149. if(this.data.isEmpty()){
  150. return null;
  151. }
  152. return this.data.removeFromLast();
  153. }
  154. @Override
  155. public T peek() {
  156. return this.data.getValue();
  157. }
  158. @Override
  159. public boolean isEmpty() {
  160. return this.size == 0;
  161. }
  162. @Override
  163. public int getSize() {
  164. return this.size;
  165. }
  166. }
  167. import java.util.ArrayList;
  168. import java.util.Random;
  169. public class StackTest<T> {
  170. public void test(myStack<T> stack, ArrayList<T> list){
  171. long startTime = System.nanoTime();
  172. // 入栈
  173. for (int i = 0; i < list.size(); i++) {
  174. stack.push(list.get(i));
  175. System.out.print(list.get(i) + " ");
  176. }
  177. System.out.println();
  178. // 获取栈中元素个数
  179. System.out.println("栈中元素个数为:" + stack.getSize());
  180. // 出栈
  181. for (int i = 0; i < stack.getSize(); i++) {
  182. // 查看栈顶元素
  183. System.out.println("当前栈顶元素为:" + stack.peek());
  184. stack.pop();
  185. if(!stack.isEmpty()){
  186. System.out.println("出栈成功!");
  187. }
  188. }
  189. long endTime = System.nanoTime();
  190. System.out.println("总耗时:" + (endTime - startTime) / 1000000000.0 + "s");
  191. }
  192. public static void main(String[] args) {
  193. StackTest<Integer> t = new StackTest<>();
  194. ArrayList<Integer> list = new ArrayList<>();
  195. ArrStack<Integer> arrStack = new ArrStack<>();
  196. LinkedStack<Integer> stack = new LinkedStack<>();
  197. Random random = new Random();
  198. for (int i = 0; i < 10; i++) {
  199. list.add(random.nextInt(100));
  200. }
  201. t.test(arrStack,list);
  202. }
  203. }

2.链表栈 

         链栈是一种基于链表实现的栈,其特点是无需事先分配固定长度的存储空间,栈的长度可以动态增长或缩小,避免了顺序栈可能存在的空间浪费和存储溢出问题。

  • 代码实现(与上述顺序栈相比,只是数据存储的存储采用了链表的方式) 
  1. import java.util.Optional;
  2. public class LinkedStack<T> implements myStack<T>{
  3. private LinkedList<T> data;
  4. public LinkedStack() {
  5. this.data = new LinkedList<>();
  6. }
  7. @Override
  8. public void push(T ele) {
  9. this.data.addInHead(ele);
  10. }
  11. @Override
  12. public T pop() {
  13. return (T) this.data.deleteHead();
  14. }
  15. @Override
  16. public T peek() {
  17. Optional<T> optional = this.data.getHead();
  18. if(optional.isPresent()){
  19. return (T) optional;
  20. }else{
  21. throw new RuntimeException();
  22. }
  23. }
  24. @Override
  25. public boolean isEmpty() {
  26. return this.data.isEmpty();
  27. }
  28. @Override
  29. public int getSize() {
  30. return this.data.getSize();
  31. }
  32. }
  33. import java.util.Optional;
  34. public class LinkedList<T> {
  35. class Node<T> {
  36. T data;
  37. Node next;
  38. public Node(T data) {
  39. this.data = data;
  40. this.next = null;
  41. }
  42. public Node(T data, Node next) {
  43. this.data = data;
  44. this.next = next;
  45. }
  46. }
  47. private Node head;
  48. private int size;
  49. public LinkedList() {
  50. this.head = new Node(null);
  51. this.size = 0;
  52. }
  53. // 判空
  54. public boolean isEmpty() {
  55. return this.size == 0;
  56. }
  57. // 向头部添加元素
  58. public void addInHead(T data) {
  59. addInAny(0, data);
  60. }
  61. // 向尾部添加元素
  62. public void addInTail(T data) {
  63. addInAny(this.size, data);
  64. }
  65. // 向任意位置添加元素
  66. public void addInAny(int index, T data) {
  67. if (index < 0 || index > this.size) {
  68. throw new IndexOutOfBoundsException("非法索引!");
  69. }
  70. Node node = new Node(data);
  71. // 寻找插入位置的前驱结点
  72. Node pre = this.head;
  73. for (int i = 0; i < index; i++) {
  74. pre = pre.next;
  75. }
  76. node.next = pre.next;
  77. pre.next = node;
  78. this.size++;
  79. }
  80. // 从链表中查找指定元素
  81. public boolean contains(T data) {
  82. Node curNode = this.head.next;
  83. while (curNode != null) {
  84. if (curNode.data.equals(data)) {
  85. return true;
  86. }
  87. curNode = curNode.next;
  88. }
  89. return false;
  90. }
  91. // 删除头结点
  92. public Optional deleteHead() {
  93. if (this.head.next == null) {
  94. return Optional.empty();
  95. }
  96. Node delNode = this.head.next;
  97. this.head.next = delNode.next;
  98. delNode.next = null;
  99. return Optional.ofNullable(delNode.data);
  100. }
  101. // 删除尾节点
  102. public Optional deleteTail() {
  103. if (this.head.next == null) {
  104. return Optional.empty();
  105. }
  106. Node curNode = this.head.next;
  107. while (curNode.next.next != null) {
  108. curNode = curNode.next;
  109. }
  110. Node delNode = curNode.next;
  111. curNode.next = delNode.next;
  112. delNode.next = null;
  113. this.size--;
  114. return Optional.ofNullable(delNode.data);
  115. }
  116. // 删除指定位置的元素
  117. public Optional deleteInIndex(int index) {
  118. if (this.head == null) {
  119. return Optional.empty();
  120. }
  121. if (index < 0 || index >= this.size) {
  122. throw new IndexOutOfBoundsException("索引异常!");
  123. }
  124. Node pre = this.head;
  125. // 找删除结点的前驱结点
  126. int i = 0;
  127. while (i < index) {
  128. pre = pre.next;
  129. i++;
  130. }
  131. Node delNode = pre.next;
  132. pre.next = delNode.next;
  133. delNode.next = null;
  134. this.size--;
  135. return Optional.ofNullable(delNode.data);
  136. }
  137. // 根据值删除元素
  138. public int deleteByData(T val) {
  139. int count = 0;
  140. Node pre = this.head;
  141. while (pre.next != null) {
  142. Node curNode = pre.next;
  143. if (curNode.data.equals(val)) {
  144. pre.next = pre.next.next;
  145. curNode.next = null;
  146. this.size--;
  147. count++;
  148. } else {
  149. pre = pre.next;
  150. }
  151. }
  152. return count;
  153. }
  154. // 获取元素个数
  155. public int getSize() {
  156. return this.size;
  157. }
  158. // 获取链表头结点
  159. public Optional getHead() {
  160. if (this.head.next == null) {
  161. return Optional.empty();
  162. }
  163. return Optional.ofNullable(this.head.next.data);
  164. }
  165. //获取链表尾结点
  166. public Optional getTail() {
  167. if (this.head.next == null) {
  168. return Optional.empty();
  169. }
  170. Node curNode = this.head.next;
  171. while (curNode != null) {
  172. curNode = curNode.next;
  173. if (curNode.next == null)
  174. break;
  175. }
  176. return Optional.ofNullable(curNode.data);
  177. }
  178. // 获取任意位置的元素
  179. public Optional getIndex(int index) {
  180. if (this.head.next == null) {
  181. return Optional.empty();
  182. }
  183. if (index < 0 || index >= this.size) {
  184. throw new IndexOutOfBoundsException("索引异常!");
  185. }
  186. Node curNode = this.head.next;
  187. int i = 0;
  188. while (i < index) {
  189. curNode = curNode.next;
  190. i++;
  191. }
  192. return Optional.ofNullable(curNode.data);
  193. }
  194. // 重写toString方法
  195. @Override
  196. public String toString() {
  197. StringBuilder sb = new StringBuilder();
  198. Node curNode = this.head.next;
  199. while (curNode != null) {
  200. sb.append(curNode.data + "--->");
  201. curNode = curNode.next;
  202. }
  203. sb.append("null");
  204. return sb.toString();
  205. }
  206. }

 三.栈的应用

         栈常用来解决递归、括号匹配、表达式求值等问题。

1.例题一:有效的括号(20. 有效的括号 - 力扣(LeetCode))

① 题目分析:

我们遍历给定的字符串 s。当遇到一个左括号时,我们会期望在后续的遍历中,有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合,因此我们可以将这个左括号放入栈中。

当我们遇到一个右括号时,我们需要将一个相同类型的左括号闭合。此时,我们可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型,或者栈中并没有左括号,那么字符串 s 无效。

② 代码实现

  1. import java.util.Stack;
  2. public class LeetCode_20 {
  3. public boolean isValid(String s) {
  4. Stack<Character> c = new Stack<>();
  5. // 入参判断
  6. if (s == null || s.length() == 0) {
  7. return true;
  8. }
  9. for (int i = 0; i < s.length(); i++) {
  10. // 碰到左括号就入栈
  11. if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
  12. c.push(s.charAt(i));
  13. }
  14. if (c.empty()) {
  15. return false;
  16. }
  17. // 没有相匹配的括号就return false
  18. if (((s.charAt(i) == ')' && c.pop() != '(') || (s.charAt(i) == ']' && c.pop() != '[') || (s.charAt(i) == '}' && c.pop() != '{'))) {
  19. return false;
  20. }
  21. }
  22. return c.empty();
  23. }
  24. public static void main(String[] args) {
  25. String s = "(()[]{}";
  26. LeetCode_20 leetCode_20 = new LeetCode_20();
  27. System.out.println(leetCode_20.isValid(s));
  28. }
  29. }

 

2.例题二:基本计算器II(227. 基本计算器 II - 力扣(LeetCode)

① 题目分析

        由于乘除优先于加减计算,因此不妨考虑先进行所有乘除运算,并将这些乘除运算后的整数值放回原表达式的相应位置,则随后整个表达式的值,就等于所有整数加减后的值。

        基于上述想法,我们可以用一个栈,保存这些进行乘除运算后的整数的值。对于加减号后的数字,将其直接入栈;对于乘除号后的数字,可以直接与栈顶元素计算,并替换栈顶元素为计算后的结果。

② 代码实现

  1. import java.util.Stack;
  2. public class LeetCode_227 {
  3. public int calculate(String s) {
  4. s = s.trim(); //去掉字符串两端的空格
  5. Stack<Integer> stack = new Stack<>();
  6. char c = '+';
  7. int num = 0;
  8. for (int i = 0; i < s.length(); ++i) {
  9. if (Character.isDigit(s.charAt(i))) { //判断当前字符是否是数字
  10. num = num * 10 + s.charAt(i) - '0'; //处理两位及两位以上的数字
  11. }
  12. // 判断当前字符是不是运算符号,对最后一个数字做特殊处理
  13. if ((!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ') || i == s.length() - 1) {
  14. switch (c) {
  15. case '+':
  16. stack.push(num);
  17. break;
  18. case '-':
  19. stack.push(-num);
  20. break;
  21. case '*':
  22. stack.push(stack.pop() * num);
  23. break;
  24. default:
  25. stack.push(stack.pop() / num);
  26. }
  27. c = s.charAt(i); //记录下当前的运算符号
  28. num = 0; //重置
  29. }
  30. }
  31. int res = 0;
  32. while (!stack.isEmpty()) {
  33. res += stack.pop();
  34. }
  35. return res;
  36. }
  37. public static void main(String[] args) {
  38. String s = " 13+5 / 2 -3 ";
  39. LeetCode_227 leetCode_227 = new LeetCode_227();
  40. System.out.println("计算结果为:" + leetCode_227.calculate(s));
  41. }
  42. }

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/blog/article/detail/47913
推荐阅读
相关标签
  

闽ICP备14008679号