【数据结构与算法 | 基础篇】数组模拟栈

1. 前言

前文我们刚提及了如何用单向链表来模拟栈. 我们还可以用数组来模拟栈.使用栈顶指针top来进行栈顶的操作.

2. 数组模拟栈

(1). 栈接口

public interface stack<E> {
    //压栈
    boolean push(E value);
    //弹栈, 栈非空返回栈顶元素

    E pop();
    //返回栈顶元素, 但不弹栈
    E peek();
    //判断栈是否为空
    boolean isEmpty();
    //判断栈是否已满
    boolean isFull();
}

(2). 数组模拟栈

public class ArrayStack<E> implements stack<E>, Iterable<E>{
    //栈顶指针
    private int top;
    //数组模拟栈
    private E[] stack;

    public ArrayStack(int capacity) {
        stack = (E[]) new Object[capacity];
    }
    @Override
    public boolean push(E value) {
        if(isFull()) {
            return false;
        }
        stack[top++] = value;
        return true;
    }

    @Override
    public E pop() {
        if(isEmpty()) {
            return null;
        }
        return stack[--top];
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return stack[top-1];
    }

    @Override
    public boolean isEmpty() {
        return top < 0;
    }

    @Override
    public boolean isFull() {
        return top == stack.length;
    }
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            @Override
            public boolean hasNext() {
                return top > 0;
            }

            @Override
            public E next() {
                return stack[--top];
            }
        };
    }
}

3. 单元测试

public class ArrayStackTest {
    @Test
    public void test1() {
        ArrayStack<Integer> stack = new ArrayStack<>(10);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.push(6);
        stack.push(7);
        for (Integer element : stack) {
            System.out.print(element + " ");
        }
        //7 6 5 4 3 2 1
    }
    @Test
    public void test2() {
        ArrayStack<Integer> stack = new ArrayStack<>(10);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.push(6);
        stack.push(7);
        System.out.println(stack.peek());
        //7
        System.out.println(stack.pop());
        //7
        System.out.println(stack.peek());
        //6
    }
}