数据结构（java语言描述）-- 栈的两种简单实现

àì夳堔傛蜴生んèń 2022-08-12 20:29 148阅读 0赞

首先了解下栈的概念：

栈是限定仅在表头进行插入和删除操作的线性表。有时又叫LIFO（后进先出表）。要搞清楚这个概念，首先要明白”栈“原来的意思，如此才能把握本质。

"栈“者,存储货物或供旅客住宿的地方,可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈、出栈的说法。

栈模型：

![27.jpg][]

只有栈顶元素是可以访问的。

任何实现表的方法都能实现栈。因为栈操作是常数时间，所以，除非在非常独特的环境下，这是不可能产生任何明显的改进的。

下面给出第一种比较简单的方法，即使用双链表实现栈。

import java.util.*;
    /**
     * 链式结构实现栈
     * @author Administrator
     *
     * @param <E>
     */
    public class MyStack<E>{
        LinkedList<E> list;
        
        public MyStack(){
            list = new LinkedList<E>();
        }
        //出栈
        public E pop(){
            return list.removeLast();
        }
        //入栈
        public void push(E o){
            list.add(o);
        }
        //访问栈顶元素
        public E getTop(){
            return list.getLast();
        }
        //栈为空
        public boolean isEmpty(){
            return list.size()==0;
        }
        //栈大小
        public int size(){
            return list.size();
        }
        /**
         * 测试代码
         * @param args
         */
        public static void main(String[] args) {
            MyStack<String> stack = new MyStack<String>();
            stack.push("我是第一入栈的元素");
            stack.push("我是第二入栈的元素");
            stack.push("我是第三入栈的元素");
            System.out.println("栈是否为空："+stack.isEmpty());
            System.out.println("栈顶元素："+stack.getTop());
            System.out.println("第一个出栈："+stack.pop());
            System.out.println("第二个出栈："+stack.pop());
            System.out.println("第三个出栈："+stack.pop());
            System.out.println("栈是否为空："+stack.isEmpty());
        }
        
    }

测试结果：

![Center][]

下面给出第二种简单的方法，即使用数组实现栈。

/**
     * 栈的简单数组实现
     * @author lenovo
     *
     * @param <E>
     */
    public class TestArrStack<E> { 
          
        private Object[] stack; 			// 栈的声明  
        private static final int DEFAULLT_SIZE = 2;   // 栈的默认初始大小      
        private int theOfStack;    // 栈顶索引   
        
        /**
         * 构造栈
         */
        public TestArrStack() { 
            stack = new Object[DEFAULLT_SIZE]; 
            theOfStack = -1; 
        }    
        
        /** 
         * 构造方法 
         *  
         * @param theSize 
         *            栈的初始大小 
         */
        public TestArrStack(int theSize) { 
            if (theSize < 0) { 
                throw new IllegalArgumentException(); 
            } 
            stack = new Object[theSize]; 
            theOfStack = -1; 
        }  
        
        /** 
         * 出栈操作 
         *  
         * @return 栈顶对象 
         */
        public  E pop() { 
            if (!isEmpty()) { 
                E temp = peek(); 
                stack[theOfStack--] = null; 
                return temp; 
            } 
            return null; 
        } 
        
        /** 
         * 入栈操作 
         *  
         * @param newVal 等待入栈的对象 
         *            
         */
        public  void push(E newVal) { 
            if (isFull()) { 
                Object[] temp = stack; 
                // 如果栈满，则创建空间为当前栈空间两倍的栈 
                stack = new Object[stack.length * 2]; 
                System.arraycopy(temp, 0, stack, 0, temp.length); 
            } 
            stack[++theOfStack] = newVal; 
        } 
          
        /** 
         * 查看栈顶对象 
         *  
         * @return 栈顶对象 
         */
        public E peek() { 
            if (!isEmpty()) { 
                return (E) stack[theOfStack]; 
            } 
            return null; 
        } 
          
        /** 
         * 查看栈是否为空 
         *  
         * @return 如果栈为空返回true，否则返回false 
         */
        public boolean isEmpty() { 
            return theOfStack == -1; 
        } 
          
        /** 
         * 查看栈是否满 
         *  
         * @return 如果栈满返回true,否则返回false 
         */
        public boolean isFull() { 
            return theOfStack >= stack.length - 1; 
        } 
        
        /**
         * 测试代码
         * @param args
         */
        public static void main(String[] args) {
        	TestArrStack<String> sta = new TestArrStack<String>();
            sta.push("我是第一入栈的元素");
            sta.push("我是第二入栈的元素");
            sta.push("我是第三入栈的元素");
            System.out.println("栈满？"+sta.isFull());
            System.out.println("栈是否为空："+sta.isEmpty());
            System.out.println("栈顶元素："+sta.peek());
            System.out.println("第一个出栈："+sta.pop());
            System.out.println("第二个出栈："+sta.pop());
            System.out.println("第三个出栈："+sta.pop());
            System.out.println("栈满？"+sta.isFull());
            System.out.println("栈是否为空："+sta.isEmpty());
        }
    }

测试结果：

![Center 1][]

[27.jpg]: /images/20220810/91384fdce28d4daabc9465fa0837e400.png
[Center]: /images/20220810/241cab897df5444897f112fb8dfb291f.png
[Center 1]: /images/20220810/910d77c6eba84e008aa54192ac4cd957.png