首页 > 代码库 > Stack结构模拟

Stack结构模拟

2024-07-18 00:36:50   220人阅读

我们接着就开始模拟stack数据结构，发觉敲多的头昏，坚持分享

1.基础结构对象Node

public class Node {

private Object data;// 存放值
private Node next;// 下一个节点

public   Node(){}


public Node(Object data) {// 构造值为data的结点
  this(data,null);
}
public Node(Object data, Node next) {
  this.data = http://www.mamicode.com/data;
  this.next = next;
}
public Object getData() {
  return data;
}
public void setData(Object data) {
  this.data = http://www.mamicode.com/data;
}
public Node getNext() {
  return next;
}
public void setNext(Node next) {
  this.next = next;
}
}

2.栈接口

public interface IStack {
    
public void clear(); // 将一个已经存在的栈置成空
public boolean isEmpty(); // 测试栈是否为空
public int length();// 求栈中的数据元素个数并由函数返回其值
public Object peek();// 查看栈顶对象而不移除它，返回栈顶对象
public Object pop();// 移除栈顶对象并作为此函数的值返回该对象
public void push(Object o) throws Exception;// 把项压入栈顶
public void display();// 打印函数，打印所有栈中的元素(栈底到栈顶)
}


3.单链表实现栈

public class LinkStack  implements IStack{

private  Node  top;// 栈顶元素的引用

//清空栈
public void clear() {
  top=null;
}
     //栈数据展示
public void display() {
    Node  p=top;
   int  index=1;
   while(p!=null)
   {
    System.out.println("(节点"+index+")"+p.getData());
    p=p.getNext();
    index++;
   }
}

//栈是否为空
public boolean isEmpty() {
  return top==null;
}
   
//栈长度
public int length() {
     Node  p=top;
     int  length=0;
     while(p!=null)
     {   p=p.getNext();
      length++;
     }
  return length;
}

//取出首元素,但不删除
public Object peek() {
  if (!isEmpty())
   return top.getData();// 返回栈顶元素
  else
   return null;
}
  
//取出首元素,并删除
public Object pop() { 
  if (!isEmpty()) {
   Node p = top;// p指向栈顶结点
   top = top.getNext();
   return p.getData();
  } else
   return null;
}


//插入数据
public void push(Object o) throws Exception {
        //改变栈顶结点
  Node p = new Node(o); // 构造一个新的结点
  p.setNext(top);
  top = p;
}


public Node getTop() {
  return top;
}
public void setTop(Node top) {
  this.top = top;
}
}

4.顺序结构实现栈
public class SqStack   implements  IStack{
private Object[] stackElem; // 栈存储空间
private int top; // 非空栈中始终表示栈顶元素的下一个位置，当栈为空时其值为0

public  SqStack(int  maxSize)
{
  stackElem=new Object[maxSize];
  top=0;
}

//清空栈
public void clear() { 
  top=0;
}

    //展示队列
public void display() {
    //从站栈顶开始打印
  for (int i=top-1;i>=0;i--)
  {
   System.out.println(stackElem.toString() + " ");// 打印
  }
}
   
//栈是否为空
public boolean isEmpty() {
  
  return top==0;
}
//栈的长度
public int length() {

  return top;
}
public Object peek() {
  if(!isEmpty())// 栈非空
   return stackElem[top-1]; // 栈顶元素
  else
   // 栈为空
   return null;
}
public Object pop() {
  
  if (top == 0)// 栈为空
   return null;
  else {// 栈非空
   return stackElem[--top];// 修改栈顶指针，并返回栈顶元素
  }
}
public void push(Object o) throws Exception {
  if (top == stackElem.length)// 栈满
   throw new Exception("栈已满");// 输出异常
  else
   // 栈未满
   stackElem[top++] = o;// o赋给栈顶元素后，top增1
}
}
小结：希望这样的分享方式对你有用.


联系
我们