栈的数组实现和链式实现

  1. 云栖社区>
  2. 博客>
  3. 正文

栈的数组实现和链式实现

范大脚脚 2017-11-22 14:39:00 浏览564
展开阅读全文
1,堆栈ADT

 
 
package Stack;

public interface StackADT {

    public void push(Object element);//压栈
    
    public Object pop();//出栈
    
    public boolean isEmpty();
    
    public int size();
    
    public Object peek();//返回栈顶对象的一个引用
    
    public String toString();
}
 


2,链式实现

中维护一个指向栈顶的结点和一个count变量指示栈的大小:在栈的一段添加和删除元素,在栈

private LinearNode top; //指向栈顶
private int count;//标记栈的大小

每次出栈和压栈在链表的表头:(也可以再表尾,实现方式不一样而已)
top--->元素1--->元素2--->元素3.........

实现(附带测试main):

 
 
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





3,数组实现

栈底总是数组下标为0的位置,入栈出栈从数组下标的最后一个元素开始:

private Object[] contents;
private int top;//top标记下一个入栈的位置,同时也表示栈的容量大小,跟链式实现的count比较一下!!!

实现(附带测试main):

 
 
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
复制代码

 


本文转自农夫山泉别墅博客园博客,原文链接:http://www.cnblogs.com/yaowen/p/4386002.html,如需转载请自行联系原作者

网友评论

登录后评论
0/500
评论
范大脚脚
+ 关注