Java数据结构之栈Stack的使用和实现原理解读

一、java中栈与其他集合的关系

1.Stack与其他相关数据结构接口的关系

栈与其他相关数据结构接口的关系

2.Stack与Vector
  • Vector是Stack的父类,它实现了Stack实现与之相关接口的所有方法
3.Vector与ArrayList
  • 相同点:
    • 它们都实现了List接口和Collection接口等 
    • 它们的底层都使用数组来存储节点
  • 不同点
    • (1)线程安全:ArrayList是不是线程安全的,而Vector是线程安全的(多线程操作)
    • (2)扩容:ArrayList容量增长率为当前容量的50%,而Vector是100%,对于数据量比较大的数据,Vector减少了扩容开销
    • (3)性能:因为ArrayList不是线程安全的,没有使用synchoronized线程锁,所以性能更高,而Vector使用了synchoronized线程锁,所以速度没有ArrayList快

二、Stack的使用与实现原理解读

因为Stack实现了List接口,而且底层也使用数组存储数据节点,因此与ArrayList很类似,在此不再赘述

1.初始化
  • new Stack() : 不需要任何参数,返回一个Stack对象
  1. Stack<String> books = new Stack<String>();
2.push方法 
(1)push方法的使用
  • push(E element) : 向栈中添加节点元素
  1. Stack<String> books = new Stack<String>();
  2. books.push("JAVA编程");
  3. books.push("网络安全");
  4. books.push("计算机网络");
  5. books.push("计算机文化基础");
  6. System.out.println(books); //[JAVA编程, 网络安全, 计算机网络, 计算机文化基础]
(2)push方法的实现
  1. public E push(E item) {
  2. /*-------------------------------------------------
  3. public synchronized void addElement(E obj) {
  4. modCount++;
  5. //扩容
  6. ensureCapacityHelper(elementCount + 1);
  7. //将元素添加到数组末尾,并增加元数个数
  8. elementData[elementCount++] = obj;
  9. }
  10. ---------------------------------------------------*/
  11. addElement(item);
  12. return item;
  13. }
3.pop方法 
(1)pop方法的使用
  • pop:出栈操作
  1. Stack<String> books = new Stack<String>();
  2. books.push("JAVA编程");
  3. books.push("网络安全");
  4. books.push("计算机网络");
  5. books.push("计算机文化基础");
  6. String lastBookName = books.pop();
  7. System.out.println(lastBookName); //计算机文化基础
  8. System.out.println(books); //[JAVA编程, 网络安全, 计算机网络]
(2)pop方法的实现解读
  1. public synchronized E pop() {
  2. E obj;
  3. int len = size();
  4. //1.通过调用peek方法获取最后一个节点
  5. obj = peek();
  6. /*-------------------------------------------------
  7. public synchronized void removeElementAt(int index) {
  8. modCount++;
  9. if (index >= elementCount) {
  10. throw new ArrayIndexOutOfBoundsException(index + " >= " +
  11. elementCount);
  12. }
  13. else if (index < 0) {
  14. throw new ArrayIndexOutOfBoundsException(index);
  15. }
  16. //1.获取需要移动的元素的长度
  17. int j = elementCount - index - 1;
  18. if (j > 0) {
  19. //2.通过复制数组的方式将数组往前移动
  20. System.arraycopy(elementData, index + 1, elementData, index, j);
  21. }
  22. //3.元素节点个数减1
  23. elementCount--;
  24. //4.将最后一位元素设置为null
  25. elementData[elementCount] = null; /* to let gc do its work */
  26. }
  27. --------------------------------------------------*/
  28. //2.调用removeElementAt方法删除最后一个节点
  29. removeElementAt(len - 1);
  30. return obj;
  31. }
4.peek方法
(1)peek方法的使用
  • peek方法:返回栈的最后一个元素节点
(2)peek方法的实现解读

-

  1. public synchronized E peek() {
  2. //1.获取数组的长度
  3. int len = size();
  4. if (len == 0)
  5. throw new EmptyStackException();
  6. /*-----------------------------------------------------
  7. public synchronized E elementAt(int index) {
  8. if (index >= elementCount) {
  9. throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
  10. }
  11. /*---------------------------------------------------
  12. E elementData(int index) {
  13. //通过索引值从数组中查找元素
  14. return (E) elementData[index];
  15. }
  16. *----------------------------------------------------/
  17. return elementData(index);
  18. }
  19. -------------------------------------------------------*/
  20. return elementAt(len - 1);
  21. }
5.empty方法 
(1)empty方法的使用
  • empty判断栈是否为空栈
  1. Stack<String> books = new Stack<String>();
  2. System.out.println(books.empty()); //true
  3. books.push("大学英语");
  4. System.out.println(books.empty()); //false
(2)empty方法的实现解读
  1. /*------------------------------------------------
  2. public synchronized int size() {
  3. return elementCount;
  4. }
  5. --------------------------------------------------*/
  6. public boolean empty() {
  7. //判断元素个数是否为0即可
  8. return size() == 0;
  9. }
6.search方法 
(1)search方法的使用
  • search(E element):搜索元素在栈中的出现的位置(不存在时,返回-1)
  1. Stack<String> books = new Stack<String>();
  2. books.push("JAVA编程");
  3. books.push("网络安全");
  4. books.push("计算机网络");
  5. books.push("计算机文化基础");
  6. int idx = books.search("计算机网络");
  7. System.out.println(idx); //2
(2)search方法的实现解读
  1. public synchronized int search(Object o) {
  2. /*----------------------------
  3. public synchronized int lastIndexOf(Object o, int index) {
  4. if (index >= elementCount)
  5. throw new IndexOutOfBoundsException(index + " >= "+ elementCount);
  6. //如果元素为null
  7. if (o == null) {
  8. //从最后一个元素开始查找,遍历栈的节点
  9. for (int i = index; i >= 0; i--)
  10. if (elementData[i]==null)
  11. return i;
  12. } else {
  13.   //从最后一个元素开始查找,遍历栈的节点
  14. for (int i = index; i >= 0; i--)
  15. if (o.equals(elementData[i]))
  16. return i;
  17. }
  18. return -1;
  19. }
  20. public synchronized int lastIndexOf(Object o) {
  21. return lastIndexOf(o, elementCount-1);
  22. }
  23. -----------------------------*/
  24. //1.查找出元素在栈中最后一次出现的位置
  25. int i = lastIndexOf(o);
  26. if (i >= 0) {
  27. return size() - i;
  28. }
  29. return -1;
  30. }