import java.util.Collection;
import java.util.NoSuchElementException;
public class ArrayStack<E> {
private int initalSize = 5;
private Object[] stack;
private int head;
private int tail;
public ArrayStack() {
initialize(null);
}
public ArrayStack(int newcapacity){
if (newcapacity < this.initalSize)
throw new IllegalArgumentException("The new capacity is too small!");
initalSize = newcapacity;
initialize(null);
}
public ArrayStack(E[] items) {
initialize(items);
}
public ArrayStack(Collection<E> collection) {
initialize(collection.toArray());
}
private void initialize(Object[] items){
if (items == null || items.length == 0){
stack = new Object[initalSize];
head = 0;
tail = 0;
}
else{
stack = new Object[items.length + 1];
System.arraycopy(items, 0, stack, 0, items.length);
head = items.length;
tail = 0;
}
}
@SuppressWarnings("unchecked")
public E pop(){
if (size() == 0)
throw new NoSuchElementException();
if (head == 0)
head = stack.length;
Object ret = stack[--head];
loseWeight();
return (E)ret;
}
public void push(E item){
increaseWeight();
stack[head++] = item;
if (head == stack.length)
head = 0;
}
@SuppressWarnings("unchecked")
public E peek(){
if (size() == 0)
throw new NoSuchElementException();
if (head == 0)
return (E)stack[stack.length - 1];
else
return (E)stack[head-1];
}
public boolean isEmpty(){
return (size() == 0);
}
public int size(){
return head >= tail ? head - tail : head + stack.length - tail;
}
public boolean increaseWeight(){
if (size() == stack.length - 1){
Object[] newStack = new Object[stack.length * 2];
System.arraycopy(stack, 0, newStack, 0, stack.length);
stack = newStack;
return true;
}
return false;
}
public boolean loseWeight(){
if (size() == stack.length / 4){
Object[] newStack = new Object[stack.length/2];
if (head >= tail){
System.arraycopy(stack, tail, newStack, 0, size());
}
else{
System.arraycopy(stack, tail, newStack, 0, stack.length-tail);
System.arraycopy(stack, 0, newStack, stack.length-tail, head);
}
tail = 0;
head = size();
return true;
}
return false;
}
}
//本篇文章来源于csdn论坛:http://topic.csdn.net/u/20100201/21/8abd9e46-c84c-4ba1-bf28-3a8ed907bd94.html
原文链接http://edu.codepub.com/2009/1003/16063.php
分享到:
相关推荐
数组可以作为这些数据结构的基础实现,如用数组模拟链表、实现队列的FIFO(先进先出)和栈的LIFO(后进先出)特性。 通过学习和实践上述知识点,对于Java算法题中的数组问题,你将能够游刃有余地进行解答。不断练习...
本资源是一个 Java 实现的栈的先进后出的算法演示程序,展示了栈的基本操作和多线程同步机制的应用。 一、栈的基本概念 栈是一种基本的数据结构,遵循先进后出(FILO)的原则,即最后入栈的元素最先被取出。栈的...
栈是后进先出(LIFO)的数据结构,可以用数组模拟;队列是先进先出(FIFO)的,同样可以使用数组来实现。这两种结构在处理任务调度、内存管理等方面非常有用。 数组的性能优化也是一个重要话题。合理选择数组大小、...
在Java中,我们可以利用LinkedList的addFirst()方法来模拟压栈操作,将新元素添加到链表头部,使用removeFirst()方法来模拟弹栈操作,删除并返回链表头部的元素。以下是一个简单的栈实现: ```java public class ...
栈被称为“后进先出”(LIFO, Last In First Out)数据结构,而队列则是“先进先出”(FIFO, First In First Out)数据结构。这两种数据结构在实现上通常使用数组或链表。 栈是一种操作受限的线性表,只允许在表的...
在Java中,我们可以使用数组或者链表来模拟栈的实现。上述代码提供了一个基于数组的栈实现,`StackS` 类中定义了栈的容量`max`,存储元素的数组`ary`,以及栈顶指针`top`。`push()`方法用于压栈,`pop()`方法用于弹...
1. 数据结构:模拟题中出现了对栈(Stack)和队列(Queue)操作的描述,栈通常遵循后进先出(LIFO)原则,而队列则是先进先出(FIFO)。在Java中,可以使用`java.util`包下的`Stack`、`Queue`、`LinkedList`等类来...
在这个特定的项目"池塘夜将彩色雨"中,开发者使用Java编程语言来模拟一个夜晚池塘下雨的情景,融入了风声、风向可变性、彩色雨以及随风摇曳的荷花等元素,从而创建出一个生动的场景。 首先,我们需要了解数据结构在...
Java中可以使用LinkedList类来模拟队列,熟悉enqueue(入队)和dequeue(出队)操作是基础,同时理解循环队列和优先级队列的概念也很重要。 5. **数组和链表的比较**: 在复习过程中,你可能会遇到比较数组和链表...
为了使用队列实现栈的功能,我们需要确保能够模拟栈的行为。具体来说,我们需要做到: - 在`push`操作时,新元素应该成为栈顶元素。 - 在`pop`操作时,应该移除栈顶元素并返回该值。 - 在`top`操作时,应该返回栈顶...
队列是一种先进先出(FIFO)的数据结构,`java.util.Queue`接口及其实现类如`LinkedList`可用来创建队列,常见应用包括任务调度和广度优先搜索。 树是一种非线性数据结构,包含根节点、子节点和分支。Java中的`java...
此外,还可以自定义数据结构来模拟栈和队列的行为。 练习题目通常会涉及使用栈和队列解决实际问题,如括号匹配、回文检查、计算表达式、迷宫路径寻找等。通过这些练习,可以加深对栈和队列的理解,并提升解决问题的...
在 Java 中,可以使用数组来模拟栈的实现,如下所示: ```java public class Statck { private int maxSize; //栈的最多元素数 private int top; //栈顶指针 private int len; //栈的深度 private int[] ...
顺序栈是基于数组实现的,其特点是元素的存储和访问按照先进后出(First In Last Out, FIFO)的原则进行。在这个"顺序栈.zip"文件中,很可能是包含了一些关于顺序栈的实例、代码实现或相关练习。 顺序栈的基本操作...
在数据结构课程的实验4中,学生可能会学习如何使用编程语言(如C++、Java或Python)来实现栈和队列的基本操作,并通过实际的编程练习来加深理解。可能的实验任务包括: 1. 设计和实现栈和队列的类结构,包括构造...
在实验“实验4 队列.doc”中,你可能会学习到如何通过编程语言(如C++、Java或Python)来实现队列的基本操作,并通过具体的实例或问题来理解和掌握其工作原理。可能包括创建队列、入队、出队的代码示例,以及相关的...
队列是先进先出(FIFO)的数据结构,Java提供了`java.util.Queue`接口和其实现类如`LinkedList`,用于实现队列操作。队列常用于任务调度、打印队列等。 哈希表,如Java中的`HashMap`和`HashSet`,提供了基于键值对...
在Java中,可以使用二维数组来模拟棋盘,用回溯算法来尝试各种放置皇后的位置,直到找到所有解或无解为止。 【迷宫问题】: 迷宫问题通常涉及路径查找算法,如深度优先搜索(DFS)或广度优先搜索(BFS)。在Java中...
3. **队列**:对于处理交易请求,可以使用队列数据结构,遵循先进先出(FIFO)的原则,模拟银行柜台处理交易的顺序。 4. **栈**:在某些情况下,比如撤销最近的操作,栈的后进先出(LIFO)特性可能会派上用场。 5....