摘要：要实现，至少应该包括出栈操作，弹出栈顶元素。入栈操作查看栈顶元素栈为空另外，实现一个栈，还应该考虑到几个问题栈的初始大小以及栈满以后如何新增栈空间对栈进行更新时需要进行同步有三种实现的方式，数组，容器，以及链表的方法。
虽是读书笔记，但是如转载请注明出处http://segmentfault.com/blog/exploring/
..拒绝伸手复制党
想更一进步的支持我，请扫描下方的二维码，你懂的~
栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
java 没有栈这样的数据结构，如果想利用先进后出（FILO）这样的数据结构，就必须自己实现。
要实现Stack，至少应该包括：
1. pop() 出栈操作，弹出栈顶元素。
2. push(E e) 入栈操作
3. peek() 查看栈顶元素
4. isEmpty() 栈为空
另外，实现一个栈，还应该考虑到几个问题：
1. 栈的初始大小以及栈满以后如何新增栈空间
2. 对栈进行更新时需要进行同步
有三种实现的方式，数组，容器，以及链表的方法。
数据：
javapackage gsm;
import java.util.*;
public class StackArray{
private int[] array;//用数组实现
private int top; //栈顶指针
private final static int size = 100;
public StackArray(){
array = new int[size];
top = -1; //栈空的时候
}
//压栈
public void push(int element){
if(top == size-1){
throw new StackOverflowError();
}
else
array[++top] = element;
}
//弹栈
public int pop(){
if(top == -1){
throw new EmptyStackException();
}
return array[top--];
}
//判断是否为空
public boolean isEmpty(){
return top == -1;
}
//返回栈顶元素
public Integer peek(){
if(top == -1){
throw new EmptyStackException();
}
return array[top];
}
}
容器
javapackage gsm; public interface Stack{ public T pop(); public void push(T element); public boolean isEmpty(); public T peek(); } package gsm; import java.util.*; public class StackList implements Stack { private List list ; //用容器实现 StackList(){ list = new ArrayList (); } //弹栈 public T pop(){ if(this.isEmpty() == true){ throw new EmptyStackException(); } return list.remove(list.size()-1); } //压栈 public void push(T element){ list.add(element); } //判断是否为空 public boolean isEmpty(){ return list.size() == 0; } //返回栈顶元素 public T peek(){ if(this.isEmpty() == true){ throw new EmptyStackException(); } return list.get(list.size()-1); } }
链表
javapackage gsm; import java.util.EmptyStackException; public class LinkedStackimplements Stack { //不用容器或者数组等数据结构存储节点 //Node定义一个节点类 private static class Node{ private U item; //存储的data private Node next; //类似指针 Node(){ this.item = null; this.next = null; } Node(U item, Node next){ this.item = item; this.next = next; } boolean end(){ return item == null && next == null; } } private Node top ; //栈顶指针 LinkedStack(){ top = new Node (); } //弹栈 public T pop(){ if(this.isEmpty() == true){ throw new EmptyStackException(); } T result = top.item; if(!top.end()) { top = top.next; } return result; } //压栈 public void push(T element){ top = new Node (element, top); } //判断是否为空 public boolean isEmpty(){ return top.end(); } //返回栈顶元素 public T peek(){ if(this.isEmpty() == true){ throw new EmptyStackException(); } T result = top.item; return result; } }
可以发现容器果然是java的一个利器，方便高效。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/64250.html
摘要：常见数据结构分析及实现说明本文中的代码是参考编程思想某培训机构。同时还要分析这些数据结构在时间和空间上的开销。这种专门研究应用程序中的数据之间的逻辑关系，存储方式及其操作的学问就是数据结构。 常见数据结构分析及实现 说明 本文中的代码是参考《Java编程思想》、某培训机构。 文中的代码放Github了，有兴趣的可以看看，点歌star鼓励下我。 代码在Sublime中敲的，坑爹的GBK...
Java是面向对象的语言，对象时Java不可或缺的一个元素，基本数据类型有数组用来存储，那么对象元素有什么存储呢，这就是集合，集合是Java非常重要的一块知识，Java编程思想中的持有对象简述了集合的相关知识，下面简述集合的相关功能： showImg(/img/bVC153); 集合类我们通常称为容器 其实容器只有四种：Map、List、Set和Queue 常用的容器有ArrayList、Lin...
摘要：在改进前使用数组的一个缺点是必须声明数组的大小，所以栈有确定的容量。待解决的问题建立一个能够增长或者缩短到任意大小的栈。下边的图是观察时间开销的另一种方式，表示了入栈操作需要访问数组的次数。 前言 上一篇：算法分析下一篇：基本排序 本篇内容主要是栈，队列 (和包)的基本数据类型和数据结构文章里头所有的对数函数都是以 2 为底关于性能分析，可能还是需要一些数学知识，有时间可以回一下在很多...
阅读 1507·2023-04-26 00:25
阅读 906·2021-09-27 13:36
阅读 929·2019-08-30 14:14
阅读 2171·2019-08-29 17:10
阅读 1006·2019-08-29 15:09
阅读 1942·2019-08-28 18:21
阅读 961·2019-08-26 13:27
阅读 971·2019-08-26 10:58
