栈是限制在表的一端,进行插入和删除操作的线性表,栈是后进先出
栈的操作:
构造栈
销毁栈
清空栈
计算栈长度
取栈顶元素
元素压栈
元素弹栈
代码:
package com.alg.stack;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
// 栈是限制在表的一端,进行插入和删除操作的线性表,栈是后进先出
//栈的操作:构造栈 销毁栈 清空栈 计算栈长度 取栈顶元素 元素压栈 元素弹栈
// Iterable实现这个可以使用for(T t:stack)循环
public class Stack<T> implements Iterable<T>
{
// 统计数组内保存的元素数量
private int elementCount;
// 保存数据的数组
protected Object[] elementData = null;
// 数组的每次增长幅度
protected int capacityIncrement;
// 默认数组大小
private static final int DEFAULT_SIZE = 10;
// 操作数
private int modCount;
public Stack()
{
this(DEFAULT_SIZE, 0);
}
public Stack(int capacity)
{
this(capacity, 0);
}
public Stack(int capacity, int capacityIncrment)
{
elementData = newElementArray(capacity);
elementCount = 0;
this.capacityIncrement = capacityIncrment;
}
// 取栈顶元素
@SuppressWarnings("unchecked")
public T peek()
{
return (T) elementData[elementCount - 1];
}
// 出栈
@SuppressWarnings("unchecked")
public T pop()
{
final int index = --elementCount;
T t = (T) elementData[index];
elementData[index] = null;
modCount++;
return t;
}
// 入栈
public void push(T object)
{
// 栈满,增加栈容量
if (elementCount == elementData.length)
{
growByOne();
}
elementData[elementCount++] = object;
modCount++;
}
// 清空栈
public void clear()
{
for (int i = 0; i < elementCount; i++)
{
elementData = null;
}
modCount++;
elementCount = 0;
}
@SuppressWarnings( {"unused", "unchecked"})
private T[] newElementArray(int size)
{
return (T[]) new Object[size];
}
// 如果从节省空间角度考虑capacityIncrement最好设置
private void growByOne()
{
int adding = 0;
// 没有设置增量的情况
if (capacityIncrement <= 0)
{ // 如果elementData长度为0,就加1,否则就增加elementData.length的一倍
if ((adding = elementData.length) == 0)
{
adding = 1;
}
}
else
{
adding = capacityIncrement;
}
T[] newData = newElementArray(elementData.length + adding);
System.arraycopy(elementData, 0, newData, 0, elementCount);
elementData = newData;
}
public int size()
{
return elementCount;
}
@SuppressWarnings("unchecked")
public synchronized T remove(int location)
{
if (location < elementCount)
{
T result = (T) elementData[location];
elementCount--;
int size = elementCount - location;
// 把location + 1到最后整个拷贝到从location开始到最后
if (size > 0)
{
System.arraycopy(elementData, location + 1, elementData, location, size);
}
// 因为中间的某个删除的位置被覆盖,所以需要把最后一位直空
elementData[elementCount] = null;
modCount++;
return result;
}
throw new ArrayIndexOutOfBoundsException(location);
}
@SuppressWarnings("unchecked")
public synchronized T elementAt(int location)
{
if (location < elementCount)
{
return (T) elementData[location];
}
throw new ArrayIndexOutOfBoundsException(location);
}
// 有这个可以对java新特性for循环的支持
public Iterator<T> iterator()
{
return new SimpleIterator();
}
// 简单了实现迭代器
private class SimpleIterator implements Iterator<T>
{
int pos = -1;
int expectedModCount;
int lastPosition = -1;
SimpleIterator()
{
super();
expectedModCount = modCount;
}
public boolean hasNext()
{
return pos + 1 < size();
}
public T next()
{
if (expectedModCount == modCount)
{
try
{
T result = elementAt(pos + 1);
lastPosition = ++pos;
return result;
}
catch (IndexOutOfBoundsException e)
{
throw new NoSuchElementException();
}
}
throw new ConcurrentModificationException();
}
public void remove()
{
if (this.lastPosition == -1)
{
throw new IllegalStateException();
}
if (expectedModCount != modCount)
{
throw new ConcurrentModificationException();
}
try
{
Stack.this.remove(lastPosition);
}
catch (IndexOutOfBoundsException e)
{
throw new ConcurrentModificationException();
}
expectedModCount = modCount;
if (pos == lastPosition)
{
pos--;
}
lastPosition = -1;
}
}
}
分享到:
相关推荐
数据结构-栈与队列,链表,递归,简单排序到高级排序的算法的详细笔记,本人根据视频学习进行的数据结构记录。适合入门算法学习初级篇
数据结构学习资料分享 内容概览: 本次分享包涵了大学计算机相关专业必学的“数据结构”课程的一系列学习资料。主要包括: 算法代码:我们提供了多种数据结构的实现代码,包括数组、链表、栈、队列、树、图等。...
NULL 博文链接:https://yuan.iteye.com/blog/305590
数据结构学习资料分享 内容概览: 本次分享包涵了大学计算机相关专业必学的“数据结构”课程的一系列学习资料。主要包括: 算法代码:我们提供了多种数据结构的实现代码,包括数组、链表、栈、队列、树、图等。...
数据结构学习资料分享 内容概览: 本次分享包涵了大学计算机相关专业必学的“数据结构”课程的一系列学习资料。主要包括: 算法代码:我们提供了多种数据结构的实现代码,包括数组、链表、栈、队列、树、图等。...
4.19 List高级-数据结构:Deque栈 44 4.20 Set集合的实现类HashSet 45 4.21 Map集合的实现类HashMap 46 4.22单例模式和模版方法模式 48 Java SE核心II 49 5.1 Java异常处理机制 49 5.2 File文件类 51 5.3 ...
主要为大家详细介绍了Java数据结构学习笔记第二篇,Java数据结构与算法之栈Stack实现,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
JAVA学习笔记第十四天——字符集编码解码、泛型的使用、数据结构栈和链表、集合框架&List,示例代码,里面主要是知识点的具体使用和各种现象。
常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...
常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...
高级java笔试题 整理了一波学到头秃的 Java 入坑笔记,劝退一波,别搞后端了,转算法去吧! Java 设计模式 算法 网络 操作系统 ...Java ...对象与类:继承、接口、抽象类、内部类、枚举、常用类、常用...数据结构与算法 算
学习笔记:在完成项目的过程中,我记录了大量的学习笔记,这些笔记涵盖了我遇到的问题、解决方案以及学习心得。 适用人群: 这份合集适用于所有正在学习或已经掌握Java基础的人群,无论你是大学生、Java初学者还是...
项目代码结构清晰,共包含97个文件,涉及多种编程语言和环境配置。 技术栈: - 主要语言:Java - 相关技术:JavaScript, PHP, C#, CSS 文件类型分布: - XML配置文件:53个,用于配置SSM框架及数据库相关设置 - ...
数据结构 源于慕课网的 玩转 Java 数据结构 自我学习,尝试Javascript实现 数组 不使用数组提供的api 实现数组的增删改查 数组方法的时间复杂度分析 add O(n) addLast O(1) addFirst O(n) remove O(n) removeLast O...
java8 集合源码分析 Computer-Basics-Notes-Links 学习笔记 我在学习计算机基础的过程中整理了一部分笔记,但都比较零散,有些稍微连贯的内容已经整理为...数据结构与算法相关 链表 树结构 栈 动态规划 一般算法 1.6
学习笔记:在完成项目的过程中,我记录了大量的学习笔记,这些笔记涵盖了我遇到的问题、解决方案以及学习心得。 适用人群: 这份合集适用于所有正在学习或已经掌握Java基础的人群,无论你是大学生、Java初学者还是...
学习笔记:在完成项目的过程中,我记录了大量的学习笔记,这些笔记涵盖了我遇到的问题、解决方案以及学习心得。 适用人群: 这份合集适用于所有正在学习或已经掌握Java基础的人群,无论你是大学生、Java初学者还是...
学习笔记:在完成项目的过程中,我记录了大量的学习笔记,这些笔记涵盖了我遇到的问题、解决方案以及学习心得。 适用人群: 这份合集适用于所有正在学习或已经掌握Java基础的人群,无论你是大学生、Java初学者还是...
学习笔记:在完成项目的过程中,我记录了大量的学习笔记,这些笔记涵盖了我遇到的问题、解决方案以及学习心得。 适用人群: 这份合集适用于所有正在学习或已经掌握Java基础的人群,无论你是大学生、Java初学者还是...