用Java代码实现栈数据结构的基本方法归纳
程序员文章站
2024-03-05 13:56:06
链式实现:
在栈的一段添加和删除元素,在栈中维护一个指向栈顶的结点和一个count变量指示栈的大小:
private linearnode top; //指向栈顶
p...
链式实现:
在栈的一段添加和删除元素,在栈中维护一个指向栈顶的结点和一个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(); } } }