数据结构--堆栈(Java版)

左手的ㄟ右手 2022-05-26 09:37 175阅读 0赞

### 一、栈的介绍 ###

> 栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

**栈的特点：先进后出**

### 二、栈的简单操作 ###

#### 1、栈的定义 ####

/** * 栈的接口 * @author hoaven * @see Stack * @see SetOfStacks * @see StackWithMin */
    public interface IStack<T> { 
    	
    	/** * 入栈操作 * @param item */
    	void push(T item);
    	
    	/** * 出栈操作 * @return */
    	T pop();
    	
    	/** * 返回栈顶元素，但不出栈 * @return */
    	T peek();
    	
    	/** * 栈是否为空 * @return boolean */
    	boolean isEmpty();
    }

#### 2、栈的基本实现 ####

/** * 栈的实现 * * @author hoaven * @see IStack * @see Node 结点元素，具体定义请见链表的实现博客 */
    public class Stack<T> implements IStack<T> { 
        //栈顶
        Node<T> top;
    
        public T pop() { 
            if (top != null) { 
                T item = top.data;
                //栈顶下移
                top = top.next;
                return item;
            }
    
            return null;
        }
    
        public void push(T item) { 
            Node<T> t = new Node<T>(item);
            //新栈顶的next域指向旧栈顶
            t.next = top;
            top = t;
        }
    
        public T peek() { 
            if (top != null) { 
                return top.data;
            }
            return null;
        }
    
    
        public boolean isEmpty() { 
            return (top == null);
        }
    }
    
    //单元测试
    @Test
    public void testStack(){ 
    		stack = new Stack<Integer>();
    		stack.push(1);
    		stack.push(2);
    		Assert.assertEquals(Integer.valueOf(2), stack.peek());
    		Assert.assertEquals(Integer.valueOf(2), stack.pop());
    		
    		stack.push(3);
    		Assert.assertEquals(Integer.valueOf(3), stack.pop());
    		Assert.assertFalse(stack.isEmpty());
    		Assert.assertEquals(Integer.valueOf(1), stack.pop());
    		
    		Assert.assertEquals(null, stack.peek());
    		Assert.assertEquals(null, stack.pop());
    		Assert.assertTrue(stack.isEmpty());
    	}

### 三、其他栈的实现 ###

#### 1、记录栈的最大存储容量和栈中内容实际索引值 ####

/** * 记录栈的最大存储容量和栈中内容实际索引值 * * @author hoaven */
    public class StackCapacity<T> extends Stack<T> { 
        private int capacity;
        private int index = 0;
    
        public int getIndex() { 
            return index;
        }
    
        public void setIndex(int index) { 
            this.index = index;
        }
    
        //构造栈时指定栈的最大容量
        public StackCapacity(int capacity) { 
            this.capacity = capacity;
        }
    
        public void push(T data) { 
            if (index >= capacity) { 
                throw new RuntimeException("栈容量不足");
            }
            super.push(data);
            index++;
        }
    
        public T pop() { 
            index--;
            return super.pop();
        }
    
        public boolean isFull() { 
            return (index == capacity);
        }
    }

#### 2、一个能随时获取栈中最小值的栈 ####

/**
     * 一个能随时获取栈中最小值的栈的实现
     * 实际上有两个栈，第一个栈记录所有的元素，第二个栈stackMin记录每次入栈后当前栈中的最小值
     *
     * @author hoaven
     * @see IStack
     * @see Node
     */
    public class StackWithMin extends Stack<Integer> {
        Stack<Integer> stackMin;
    
        public StackWithMin() {
            stackMin = new Stack<Integer>();
        }
    
        public void push(Integer item) {
            if (item <= min()) {
                //item为当前栈中的最小值
                stackMin.push(item);
            }
            //第一个栈也要入栈
            super.push(item);
        }
    
        public Integer pop() {
            int value = super.pop();
            if (value == min()) {
                //出栈后，stackMin的栈顶就是第一个栈中剩余元素的最小值
                stackMin.pop();
            }
            return value;
        }
    
        /**
         * 取得栈中的最小值
         *
         * @return
         */
        public Integer min() {
            if (stackMin.isEmpty()) {
                return Integer.MAX_VALUE;
            } else {
                return stackMin.peek();
            }
        }
    }
    
    //测试
    @Test
    public void testStackWithMin(){
    		StackWithMin s = new StackWithMin();
            s.push(4);
            s.push(2);
            Assert.assertEquals(Integer.valueOf(2), s.min());
            
            s.push(3);
            Assert.assertEquals(Integer.valueOf(2), s.min());
            
            s.push(1);
            Assert.assertEquals(Integer.valueOf(1), s.min());
            
            Assert.assertEquals(Integer.valueOf(1), s.peek());
            Assert.assertEquals(Integer.valueOf(1), s.pop());
            Assert.assertEquals(Integer.valueOf(2), s.min());
    	}