`
Brucegaochina
  • 浏览: 40474 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

数组模拟一个栈的操作

阅读更多
栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为退栈(POP)。 栈也称为先进后出表。

import java.util.Arrays;

/**
 * <h2>Stack</h2>仿照java的 Stack类实现的
 * <dl>
 * <br>
 * <dt>职能概要 <br>
 * <dd> 用一个数组来模拟栈的操作,当栈已满时,把大小扩大为原来的二倍 <br>
 * <dd> 
 * </dl>
 * 
 * @author Bruce
 * @date Sep 7, 2011
 * @version 1.0
 */

class Stack<E> {
	private Object[] elementData;
	private int elementCount;
	private static final int INITIAL_CAPACITY = 1;

	public Stack() {
		super();
		elementData = new Object[INITIAL_CAPACITY];
		elementCount = 0;
	}

	/**
	 * 入栈操作
	 * @param element
	 */
	public void push(E element) {

		int oldCapacity = elementData.length;
		int newCapacity;

		if (elementCount + 1 > oldCapacity) {
			newCapacity = oldCapacity * 2;
			if (newCapacity < elementCount + 1) {
				newCapacity = elementCount + 1;
			}

			elementData = Arrays.copyOf(elementData, newCapacity);
		}

		elementData[elementCount++] = element;
	}

	/**
	 * 出栈操作,返回栈顶元素;并且将其移除栈
	 * @return object
	 */
	public Object pop() {
		Object temp = elementData[elementCount - 1];
		if (elementCount > 0) {
			elementData = Arrays.copyOf(elementData, --elementCount);
		}
		return temp;
	}

	/**
	 * 返回栈顶元素
	 * @return
	 */
	public Object peek() {
		if (elementCount > 0) {
			return elementData[elementCount - 1];
		} else
			return null;
	}

	public boolean isEmpty() {
		return elementCount == 0;
	}

	public Object[] getElementData() {
		return elementData;
	}
}
/**
 * 测试类
 * @author Bruce
 * @date Sep 7, 2011
 * @version
 */
public class SimulationStack {

	public static void main(String[] args) {
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(4);
		stack.push(0);
		stack.push(1);

		System.out.println(stack.pop());
		System.out.println(stack.pop());
		System.out.println(stack.pop());

	}

}

分享到:
评论

相关推荐

    数组模拟栈.rar

    数组模拟栈是计算机科学中数据结构的一个基础概念,主要用于实现后进先出(LIFO)的数据访问模式。在本资源“数组模拟栈.rar”中,包含的代码是用C语言实现的,它允许我们理解如何利用数组来创建一个功能完备的栈。 ...

    数组模拟栈

    数组模拟栈是数据结构中的一个基础概念,它利用数组来实现栈这种线性数据结构。在计算机科学中,栈是一种后进先出(LIFO,Last In First Out)的数据结构,通常用于临时存储和处理数据。数组作为一种基本的内存分配...

    用数组实现一个栈

    在C++中,我们可以通过定义一个固定大小的数组来模拟栈的数据存储。例如,我们可以定义一个大小为10的整数数组来存储栈元素: ```cpp int stackArray[10]; ``` 初始化时,我们将栈顶指针(top)设置为-1,...

    数据结构中数组,队列,栈

    1. 猴子选大王问题:通过数组模拟报数过程,找出最后剩下的猴子的位置。 2. 狐狸捉兔子问题:兔子利用队列的特性来隐藏位置,使得狐狸无法预测其位置。 3. 约瑟夫问题:利用栈来实现循环报数,找出按照特定规则出列...

    猫的基因编码-版本2 树的数组模拟+先序遍历

    在数组模拟的树中,先序遍历需要通过数组索引来实现,通常会涉及递归或栈操作。具体来说,对于数组中的每个节点,先访问该节点,然后根据数组索引找到左子节点和右子节点,并按同样方式进行遍历。 在这个问题中,...

    C++模拟栈操作源程序

    本篇将详细介绍C++模拟栈操作的相关知识点。 首先,我们需要理解栈的基本操作。栈通常包括以下基本操作: 1. **压栈(push)**:将元素添加到栈顶。 2. **弹栈(pop)**:移除并返回栈顶元素。 3. **查看栈顶元素...

    用栈操作构建数组1

    如果不在,就需要先 "Push" 一个数字再 "Pop" 一个数字,以模拟移除不需要的数字。 这个解法的时间复杂度为 O(n),其中 n 是目标数组的最大值。空间复杂度为 O(m),m 是目标数组的长度,因为使用了哈希表存储每个...

    基于数组来实现的顺序栈和基于链表来实现的链式栈

    顺序栈和链式栈是两种常见的数据结构,用于模拟计算机内存中的栈操作。栈是一种后进先出(LIFO)的数据结构,常被用于函数调用、表达式求解、括号匹配等场景。本篇文章将详细介绍这两种栈的实现方式,并以数组和链表...

    线性表操作 栈和队列的应用 多维数组和串

    链式存储的线性表使用节点结构(如`struct node`)来表示元素,每个节点包含一个数据域和一个指向下一个节点的指针。这种方式允许动态调整表的大小,而无需预先知道表的长度。`create_link_list`函数展示了如何创建...

    用数组栈实现表达式求值(数据结构)(自制)

    在这个项目中,“用数组栈实现表达式求值”是指使用数组来模拟栈这一数据结构,处理数学表达式的计算,特别是涉及括号配对的问题。 数组栈在表达式求值中的应用主要体现在中缀表达式转后缀表达式(逆波兰表示法)和...

    Java数据结构篇-链表与数组实现栈.pptx.pptx

    - **数组栈操作**:数组栈的入栈是在数组的末尾添加元素,而出栈则是从数组末尾移除元素,同时更新栈顶指针。 - **数组栈优点**:数组栈的主要优点是访问速度快,因为数组元素可以通过索引直接访问,没有额外的...

    链表-使用Python基于链表实现数组栈.zip

    这种方法尤其适用于需要频繁进行压栈和弹栈操作,但对元素访问顺序不敏感的情况。 总结起来,这个压缩包文件提供了关于链表和数组栈的知识点,包括链表的基本概念、Python中如何模拟链表、数组栈的LIFO原理以及如何...

    顺序栈,压栈、弹栈、获得栈顶元素、统计栈中元素个数、打印栈中元素

    1. **初始化栈**:创建一个数组来模拟顺序栈,并设置栈顶指针top为-1,表示栈为空。 2. **压栈(Push)**:当需要将新元素添加到栈时,会执行压栈操作。首先检查栈是否已满(即top是否等于数组长度减一),如果未满...

    两个栈实现一个队列

    在两个栈模型中,一个栈用于入队操作,另一个用于出队操作。 1. 入队(enqueue)操作: 当需要将元素加入队列时,我们实际上是在第一个栈(称为“入队栈”)执行push操作。新元素被压入栈顶,这符合栈的LIFO特性。...

    数组的使用

    栈是后进先出(LIFO)的数据结构,可以用数组模拟;队列是先进先出(FIFO)的,同样可以使用数组来实现。这两种结构在处理任务调度、内存管理等方面非常有用。 数组的性能优化也是一个重要话题。合理选择数组大小、...

    链表模拟栈

    在C语言中,实现链表模拟栈需要定义节点结构体,包括数据和指向下一个节点的指针。同时,需要定义栈的结构体,包含链表头节点和其他可能的属性,如栈的大小。编写相应的函数来执行上述操作,如`push`、`pop`、`peek`...

    数据结构和算法必知必会的50个代码实现.zip

    实现一个大小固定的有序数组,支持动态增删改操作 实现两个有序数组合并为一个有序数组 链表 实现单链表、循环链表、双向链表,支持增删操作 实现单链表反转 实现两个有序的链表合并为一个有序链表 实现求链表...

    JavaScript数组用法详解

    使用 Array() 构造函数可以创建一个空数组、带有初始元素的数组、指定长度的数组等。数组直接量是一种简洁的创建数组的方式,只需要将元素用逗号分隔,放入方括号中即可。 数组的 length 属性是一个特殊的属性,它...

    C语言创建一个栈+入栈+出栈

    4. 错误处理:在栈操作中,如果栈已满或为空,程序会输出错误信息,以便于正确地处理栈操作。 在实际应用中,栈可以用于实现递归算法、语法分析和计算机网络协议等领域。 栈是一种非常重要的数据结构,它广泛应用...

    c语言数据结构-栈队列数组完美版资料.ppt

    栈的应用非常广泛,例如可以用于计算表达式的求解过程中模拟栈的操作。栈的应用场景非常广泛,例如可以用于计算机科学、软件开发、数据处理等领域。 在栈的实现中,有很多需要注意的地方,例如判栈空、判栈满、入栈...

Global site tag (gtag.js) - Google Analytics