链式实现:
在栈的一段添加和删除元素,在栈中维护一个指向栈顶的结点和一个count变量指示栈的大小:
private LinearNode top; //指向栈顶
private int count;//标记栈的大小
每次出栈和压栈在链表的表头:(也可以再表尾,实现方式不一样而已)
top--->元素1--->元素2--->元素3.........
实现(附带测试main):
LinkedStack
package Stack; import Bag.LinearNode; //为了重点来实现算法,将异常情况直接打印出然后退出程序,不再声明异常类 public class LinkedStack implements StackADT { private LinearNode top; //指向栈顶 private int count;//标记栈的大小 public static void main(String[] args){ LinkedStack stack = new LinkedStack(); System.out.println("将0到10依次压栈"); for(int i = 0;i < 10;i++) stack.push(i); System.out.println("连续执行5次出栈操作"); for(int i = 0;i < 5;i++) stack.pop(); System.out.println("栈为空吗?: " + stack.isEmpty()); System.out.println("栈的大小为: " + stack.size()); System.out.println("栈顶元素为: " + stack.top.getElement()); System.out.println("栈顶元素为: " + stack.peek()); } public LinkedStack() { top = null; count = 0; } public int size() { return count; } public boolean isEmpty() { return (size() == 0); } public void push(Object element) { LinearNode node = new LinearNode(element); node.setNext(top); top = node; count++; } public Object pop() { if(isEmpty()) { System.out.println("stack is empty!"); System.exit(1); } Object result = top.getElement(); top = top.getNext(); count--; return result; } public Object peek() { Object result = top.getElement(); return result; } }
运行结果:
将0到10依次压栈
连续执行5次出栈操作
栈为空吗?: false
栈的大小为: 5
栈顶元素为: 4
栈顶元素为: 4
数组实现:
栈底总是数组下标为0的位置,入栈出栈从数组下标的最后一个元素开始:
private Object[] contents; private int top;//top标记下一个入栈的位置,同时也表示栈的容量大小,跟链式实现的count比较一下!!!
实现(附带测试main):
ArrayStack
package Stack; public class ArrayStack implements StackADT { private Object[] contents; private int top;//top标记下一个入栈的位置,同时也表示栈的容量大小,跟链式实现的count比较一下!!! private static int SIZE = 10; public ArrayStack() { contents = new Object[SIZE]; top = 0; } public void expand(){//借助于申请一个辅助空间,每次扩展容量一倍 Object[] larger = new Object[size()*2]; for(int index = 0;index < top;index++) larger[index] = contents[index]; contents = larger; } public int size() { return top; } public boolean isEmpty() { return (size() == 0); } public void push(Object element) { //if(isEmpty()) //expand(); if(top == contents.length) expand(); contents[top] = element; top++; } public Object pop() { if(isEmpty()) { System.out.println("stack is empty!"); System.exit(1); } Object result = contents[top-1]; contents[top-1] = null;//出栈 top--; return result; /*书上这样写简便一点::: * top--; * Object result = contents[top]; * contents[top] = null;*/ } public Object peek() { Object result; if(isEmpty()) result = null; else result = contents[top-1]; return result; } public static void main(String[] args) { ArrayStack stack = new ArrayStack(); System.out.println("将0到24依次压栈,然后连续10次出栈"); for(int i = 0;i < 25;i++) stack.push(i); for(int i = 0;i < 10;i++) stack.pop(); System.out.println("栈的大小为: " + stack.size()); System.out.println("栈为空吗?: " + stack.isEmpty()); System.out.println("栈顶元素为: " + stack.peek()); } }
运行结果:
将0到24依次压栈,然后连续10次出栈
栈的大小为: 15
栈为空吗?: false
栈顶元素为: 14
使用集合LinkedList来模拟栈
方法
java的泛型可以让LinkedList模拟存储各种数据类型的栈,包括int,double,String,Object等等,介绍一下几种用到的API接口:
入栈
void addFirst(E e); // 将指定元素插入此列表的开头
获取栈顶元素
E getFirst(); // 返回此列表的第一个元素
出栈
E removeFirst(); // 移除并返回此列表第一个元素
判栈空
boolean isEmpty(); // 判断栈空
示例代码
import java.util.LinkedList; import java.util.NoSuchElementException; public class SimulateStack { private LinkedList<Integer> stack = new LinkedList<Integer>(); public boolean isEmpty() { return this.stack.isEmpty(); } public void push(int data) { this.stack.addFirst(data); } public int pop() throws NoSuchElementException{ return this.stack.removeFirst(); } public int getTop() throws NoSuchElementException{ return this.stack.getFirst(); } public static void main(String args[]) { SimulateStack s = new SimulateStack(); s.push(1); s.push(2); s.push(3); while (! s.isEmpty()) { int data = s.getTop(); System.out.println(data); s.pop(); } } }
栈简介 栈作为一种数据结构,是一种只能在一端进行插入和删除操作的特殊线性表。 它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。 栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,
本文向大家介绍Java递归遍历树形结构的实现代码,包括了Java递归遍历树形结构的实现代码的使用技巧和注意事项,需要的朋友参考一下 废话不多说了,直接给大家贴代码,具体代码如下所示: ps:java实现树的递归遍历(用于实现折叠菜单) 1.核心算法 2.实体类(部门) 以上所述是小编给大家介绍的Java递归遍历树形结构的相关内容,希望对大家有所帮助! 更多精彩内容请关注公众号【Java技术迷】,可
本文向大家介绍使用C#实现数据结构堆的代码,包括了使用C#实现数据结构堆的代码的使用技巧和注意事项,需要的朋友参考一下 一、 堆的介绍: 堆是用来排序的,通常是一个可以被看做一棵树的数组对象。堆满足已下特性: 1. 堆中某个节点的值总是不大于或不小于其父节点的值 任意节点的值小于(或大于)它的所有后裔,所以最小元(或最大元)在堆的根节点上(堆序性)。堆有大根堆和小根堆,将根节点最大的堆
本文向大家介绍Java 数据结构链表操作实现代码,包括了Java 数据结构链表操作实现代码的使用技巧和注意事项,需要的朋友参考一下 链表是一种复杂的数据结构,其数据之间的相互关系使链表分成三种:单链表、循环链表、双向链表,下面将逐一介绍。链表在数据结构中是基础,也是重要的知识点,这里讲下Java 中链表的实现, JAVA 链表操作:单链表和双链表 主要讲述几点: 一、链表的简介 二、链表实现原理
本文向大家介绍Java数据结构之链表、栈、队列、树的实现方法示例,包括了Java数据结构之链表、栈、队列、树的实现方法示例的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了Java数据结构之链表、栈、队列、树的实现方法。分享给大家供大家参考,具体如下: 最近无意中翻到一本书,闲来无事写几行代码,实现几种常用的数据结构,以备后查。 一、线性表(链表) 1、节点定义 2、链表操作类 二、栈 1、
本文向大家介绍C++语言数据结构 串的基本操作实例代码,包括了C++语言数据结构 串的基本操作实例代码的使用技巧和注意事项,需要的朋友参考一下 C语言数据结构 串的基本操作实例代码 输出结果: 实现代码: