欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

用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(); 
      } 
    } 
  }