栈是一种"后进先出(LIFO)"的数据结构.最近压入的数据项总是位于栈顶的.
首先我们先定义一个Stack Interface,我们把他定义成泛型的.
/**
* Stack接口
* @author 鼎鼎
*
* @param <E>
*/
public interface Stack<E> {
/**
* 判断栈是否为空
* @return
*/
public boolean isEmpty();
/**
* 返回栈中元素个数
* @return
*/
public int size();
/**
* 入栈
* @param target
*
*/
public void push(E target);
/**
* 出栈
* @return E
*/
public E pop();
/**
* 返回栈顶元素,并不出栈
* @return
*/
public E top();
}
然后进行利用Java中的数组实现ArrayStack,下面是代码:
/**
* 一个基于数组的栈实现
*
* @author 鼎鼎
* @param <E>
*/
public class ArrayStack<E> implements Stack<E> {
/**
* 表示要存入栈里的元素
*/
private E[] data;
/**
* 表示当前栈的容量
*/
private int size = 0;
public ArrayStack() {
data = (E[]) new Object[10];
//一开始的时候 栈中元素为空
size = 0;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size < 1;
}
/**
* 返回栈顶元素,但是不出栈
*/
public E top() {
if (isEmpty()) {
throw new RuntimeException("链表为空!!");
}
return data[size-1];
}
/**
* 出栈
*/
public E pop() {
if (isEmpty()) {
throw new RuntimeException("链表为空!!");
}
// 先保存那个栈顶元素
E element = data[size - 1];
// 然后清空栈顶元素,
data[size] = null;
//栈中元素减少一个
size--;
return element;
}
/**
* 入栈的时候先判断 栈是否已满,如栈满就扩充
*/
public void push(E target) {
if(target==null)
throw new RuntimeException("插入的元素不可为NULL");
if (isFull()) {
enlarge();
}
size++;
// 往栈顶添加一个元素
data[size - 1] = target;
}
/**
* 扩充数组长度 注意:一般是判断栈满以后 才扩充 扩充为原数组的两倍长度
*/
public void enlarge() {
E[] newData = (E[]) new Object[data.length * 2];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
/**
* 如果数组的长度 已经等于 放入栈中的元素数量 则表示 栈已经满了
*
* @return
*/
public boolean isFull() {
return data.length == size;
}
}
分享到:
相关推荐
利用Java语言实现的,基于数组实现的顺序栈——ArrayStack
数组栈的结构如下: type ArrayStack struct { data []interface{} top int // 栈顶指针 } 实现的操作: 栈是否为空 入栈 出栈 清空栈 输出栈 代码如下: package main import fmt type ArrayStack struct { ...
数组模拟栈1.解决思路3.代码代码实现//定义一个 ArrayStack 表示栈// 栈的大小// 数组,数组模拟栈,数据就放在该数组// top表示栈顶,初始
leetcode双人赛 ...数组栈 ArrayStack push:均摊O(1) pop:均摊O(1) getTop:O(1) getSize:O(1) isEmpty:O(1) 链栈 LinkedStack 链栈 push:O(1) pop:O(1) getTop:O(1) getSize:O(1) isEmpty:O(1)
#Array Stack已移至: 使用调整大小的数组可以简单地实现堆栈。 从 第1.3节
数组栈
`ArrayStack` 类是一个数组实现的栈,支持基本的栈操作。 以下是 `ArrayStack` 类的实现代码: ```java public class ArrayStack implements StackADT { private Object[] stack; private int top; private ...
顺序栈是一种基于数组实现的栈结构。下面是一个简单的顺序栈的实现示例,使用Python语言: ```python class ArrayStack: def __init__(self, capacity): self.capacity = capacity # 栈的容量 self.data = [None...
栈的数组形式实现,见文章:https://blog.csdn.net/qq_41453285/article/details/103329785
* 栈是先进后出* 只能访问栈顶的数据* 基于数组来实现栈的基本操作* 数据项入栈和出栈的时间复杂度均为O(1)public class ArrayStack
Java实现的MyArrayStack,包含抽象数据类型MyStack接口,MyArrayStack源码以及Junit测试case,能够帮助新手很好地学习栈及其实现
多图 要使用所有您需要做的就是创建一个类并扩展Multigraph类。 public class ...数组栈 此外,还包括内部由数组支持的实用程序堆栈类 Stack stack = new ArrayStack ( 50 ); 其中50是堆栈包含的元素数
栈_基于动态数组实现 3.8.LinkedListStack ..................... 栈_基于链表实现 3.9.BSTSet ..................................... 集合_基于二分搜索树实现 3.10.LinkedListSet ....................... 集合_...
8.3.2 类arrayStack 8.3.3 性能测量 8.4 链表描述 8.4.1 类derivedLinkedStack 8.4.2 类linkedStack 8.4.3 性能测量 8.5 应用 8.5.1 括号匹配 8.5.2 汉诺塔 8.5.3 列车车厢重排 8.5.4 开关盒布线 8.5.5 离线等价类...
本文实例讲述了PHP使用栈解决约瑟夫环问题算法。分享给大家供大家参考,具体如下: 约瑟夫环问题: 39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人...class ArrayStack { private $size; private $stack
Class.forName("org.apache.commons.collections.ArrayStack"); supportCommonCollection = true; } catch (ClassNotFoundException ex) { } try { Class.forName("org.apache.commons.digester.Digester"); ...
借用arraystack的包完成 import github.com/emirpasic/gods/stacks/arraystack func isValid(s string) bool { stack := arraystack.New() for _, c := range s { if c == '(' { stack.Push(')') } else if...
第8章 9.1typedef enum { pointer_is_null, newLength_less_than_zero } arrayStack_err
GoDS(Go数据结构) Go中各种数据结构和算法的实现。 数据结构 货柜 所有数据结构都通过以下方法实现容器接口: type Container interface { Empty () bool Size () int Clear () Values () [] interface {} ...
Containers, Sets, Lists, Stacks, Maps, Trees, HashSet, TreeSet, ArrayList, SinglyLinkedList, DoublyLinkedList, LinkedListStack, ArrayStack, HashMap, TreeMap, RedBlackTree, BinaryHeap, Comparator, ...