堆栈

堆栈的基本概念

堆栈（Stack）是具有一定操作约束的线性表。

只在一端（栈顶，Top）做插入、删除。

插入数据称为入栈（Push）。

删除数据称为出栈（Pop）。

数据出栈顺序是后入先出。​​​

例如叠盘子就是堆栈。​

堆栈的抽象数据类型描述

• 类型名称：堆栈（Stack）
• 数据集对象：一个有0个或多个元素的有穷线性表
• 操作集
  • 1. Stack CreateStack(int MaxSize)：生成空堆栈，其最大长度为M
  • 2. int IsFull(Stack S,int MaxSize)：判断堆栈S是否已满
  • 3. void Push(Stack S,ElementType item)：将元素item压入堆栈
  • 4. int isEmpty(Stack S)：判断堆栈S是否为空
  • 5. ElementType Pop(Stack S)：删除并返回栈顶元素

堆栈的顺序存储

栈的顺序实现通常由一个一维数组和一个记录栈顶元素位置的变量组成。

• 实现思路
  • 判断栈是否满
    是判断记录栈顶元素位置的变量值是否与数组的长度减1相等，如果相等则表示栈满，否则仍可继续入栈。
  • 入栈
    首先判断当前栈是否满，如果没有则将入栈的元素赋给当前栈顶元素位置的上一个元素（即栈顶位置加1的哪个位置），并且栈顶位置也要变化指向新加入元素的位置。
  • 判断栈是否空
    一般判断是否等于-1。初始空栈时将栈顶位置赋值为-1。
  • 出栈
    首先判断栈是否是空，如果没有则返回当前栈顶位置的元素，并将栈顶位置下移（即当前栈顶位置-1）
• 代码实现

  

  

Java代码实现

/**
 * 堆栈的顺序存储
 *
 * @author lck100
 */
public class MyStack {
    public int[] stack;// 一维数组（即是栈）
    public int top;// 记录栈顶位置（即数组下标）

    private MyStack(int maxSize) {
        // 给栈分配空间
        stack = new int[maxSize];
        // 现在为空栈，使栈顶位置为-1表示当前栈为空
        this.top = -1;
    }

    /**
     * 判断栈是否已满
     *
     * @return 如果已满返回true，否则返回false
     */
    public boolean isFull() {
        return top == stack.length - 1;
    }

    /**
     * 入栈，将元素添加栈中
     *
     * @param item 要加入栈中的元素
     */
    public void push(int item) throws Exception {
        // 首先要判断栈是否已满
        if (isFull()) {
            throw new Exception("栈已满！");
        } else {
            stack[++top] = item;
        }
    }

    /**
     * 判断栈是否为空
     *
     * @return 如果为空返回true，否则返回false
     */
    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * 出栈，删除并返回栈顶元素
     *
     * @return 返回栈顶元素
     */
    public int pop() throws Exception {
        // 首先判断栈是否为空
        if (isEmpty()) {
            throw new Exception("当前栈为空，没有可删除元素！");
        } else {
            return stack[top--];
        }
    }

    public static void main(String[] args) throws Exception {
        MyStack stack = new MyStack(3);
        // 打印当前栈的栈顶位置
        System.out.println(stack.top + "\n");

        // 判断当前栈是否已满
        System.out.println(stack.isFull() + "\n");

        // 入栈
        stack.push(11);
        stack.push(22);
        stack.push(33);
        // 打印当前栈的栈顶位置
        System.out.println(stack.top);
        // 判断当前栈是否已满
        System.out.println(stack.isFull() + "\n");

        // 判断栈是否为空
        System.out.println(stack.isEmpty() + "\n");

        // 出栈
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        // 打印当前栈的栈顶位置
        System.out.println(stack.top);
        // 判断当前栈是否为空
        System.out.println(stack.isEmpty() + "\n");
    }
}

测试，控制台打印：

注：上面的笔记是基于中国大学MOOC的浙大数据结构课程的PPT。