对于栈,这个数据结构据说现在现代计算机已经作为一个基本的数据结构,而且已经作为指令系统的一部分了,可见栈的重要性,以前我对链栈情有独钟,总觉得他永远不会出现栈满,而且实现起来比链栈复杂,很有成就感,但是今天看完算法分析这本书的栈的这一章才了解到,其实作为平常的使用,数组实现的栈才是最常用的,因为他的查询和入栈与出栈都是一个时间单位就能完成的,而且速度惊人完全可以忽略不计,他的唯一缺点就是需要指定最大的空间,但是一班的程序没必要这个栈做的太大,也就是一个短小的精悍的数据结构,所以这个最大数组长度也就不是什么问题了,我现在对数组实现栈又有了新的看法,他的结构简单通俗易懂,真的还不错,以后实现栈我就首先选择数组实现了。
下面废话少说,上代码,首先还是作为较为复杂的链栈的实现摆在前面
package com.bird.three;
/**
* @category 该类为链表的节点类,存储指针和数据
* @author Bird
*
*/
public class ListNode {//具有包友好访问权限
Object element;
ListNode next;
ListNode(Object theElement){
this(theElement,null);
}
ListNode(Object theElement, ListNode n){
element = theElement;
next = n;
}
}
package com.bird.three;
/**
* @category 栈的链表实现
* @author Bird
*
*/
public class StackList {
private ListNode topOfStack;
public StackList(){
topOfStack = null;
}
public boolean isEmpty(){
return topOfStack==null;
}
public void makeEmpty(){
topOfStack = null;
}
public void push(Object x){//入栈操作
topOfStack = new ListNode(x,topOfStack);//先创建X然后x的next指针指向topOfStack,然后返回给topOfStack
}
public Object peek(){//察看栈顶元素,不弹出
if(isEmpty())
return null;
return topOfStack.element;
}
public Object pop(){//弹出栈顶元素,并作为对象返回
if(isEmpty())
return null;
Object topItem = topOfStack.element;
topOfStack = topOfStack.next;
return topItem;
}
}
下面才是数组的实现,一定好好看看哦
package com.bird.three;
/**
* @category 栈的数组实现
* @author Bird
*
*/
public class StackArray {
private Object [] theArray;
private int topOfStack;
private static final int DEFAULT_CAPACITY = 10;//栈的数组默认大小
public StackArray(){
this(DEFAULT_CAPACITY);
}
public StackArray(int capacity){
theArray = new Object[capacity];
topOfStack = -1;
}
public boolean isEmpty(){
return topOfStack==-1;
}
public boolean isFull(){
return topOfStack==theArray.length-1;
}
public void push(Object x){//入栈操作
if(isFull())
throw new RuntimeException("栈满");
theArray[topOfStack++] = x;
}
public Object peek(){//查看栈顶元素
if(isEmpty())
return null;
return theArray[topOfStack];
}
public Object pop(){//弹出栈的顶元素
if(isEmpty())
return null;
Object topItem = theArray[topOfStack];
theArray[topOfStack--]=null;
return topItem;
}
}
分享到:
相关推荐
数据结构--栈和数组--思维导图.pdf
数据结构与算法PPT课件 DSChapter04 栈、队列和数组.ppt 数据结构与算法PPT课件 DSChapter05 树型结构.ppt 数据结构与算法PPT课件 DSChapter06 图.ppt 数据结构与算法PPT课件 DSChapter07 查找.ppt
数据结构练习题-第三章-栈、队列和数组-习题及答案.doc
非常清晰易懂的C#数据结构描述。目录如下: 数据结构(C#语言版) -------------------------------------------------- 前 言 1 -------------------------------------------------- 目录 3 ----------------------...
本资源为数据结构与算法第五章(串和数组)的作业程序代码。包含以下的程序: 5.10准对角矩阵 北工大电控学院《数据结构与算法》课程的其它章节程序实验及作业代码亦已在本站上传,需要的同学可进入作者的空间或通过...
数据结构-基础篇数据结构概述数据结构-算法时间复杂度与空间复杂度数据结构-字符串和数组数据结构-链表数据结构-树、二叉树算法算法题常见名词解释算法技巧总结如何写
第1章 课程导学对课程整体进行介绍,让您切实感受到前端工程师学习数据结构与算法的必要性。 1-1 课程导学 试看 1-2 学习姿势 1-3 说明与承诺第2章 基础算法之“字符串类”字符串作为JS最基本的数据类型,掌握好字符...
前端学数据结构与算法(三):链表为什么能和数组相提并论?实现数组bettle下 数组和链表.pdf
数据结构与算法PPT课件
第2章至第6章分别讨论了线性表、栈和队列、串和数组、树型结构和图结构等常用的数据结构及其应用,以及在.NET框架中相应的数据结构;第7、8两章分别讨论了排序和查找常用的各种方法及其应用以及在.NET框架中相应的...
全集内容结构如下: ├─图 │ ├─关键路径(有向无环图及其应用2) │ │ 1.txt │ │ ALGraph.cpp │ │ ALGraph.h │ │ CriticalPath.cpp │ │ CriticalPath.h │ │ InfoType.cpp │ │ InfoType.h │ │ ...
数据结构》是计算机相关专业的一门重要的专业基础课。它主要研究计算机加工对象的逻辑结构、在计算机...本课程将分别讲述数据结构的基本概念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序和文件等内容。
数据结构导论 栈、队列和数组 栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端(表尾)进行。
数据结构考研讲义 第三章 栈、队列和数组.pdf
java基本数据类型和数组,java编制0-255之间的UNICODE编码表
java双端队列的实现-Java实现自定义双端队列(链表和数组两种方式) 数组和链表.pdf
第7章 字符串和数组 字符串的基本概念 字符串的抽象数据类型 字符串的存储 字符串的匹配 数组相关概念 表格存储 特殊矩阵的压缩存储 数据的应用
包括线性表、栈和队列、串和数组等等数据结构的算法实现,且是以C++模板方式实现的
第2章至第6章分别讨论了线性表、栈和队列、串和数组、树型结构和图结构等常用的数据结构及其应用,以及在.NET框架中相应的数据结构;第7、8两章分别讨论了排序和查找常用的各种方法及其应用以及在.NET框架中相应的...