Java 基础系列 23：栈的基本概念与栈的几种实现方式详解

zifangsky
1,385 阅读5分钟

一 简介

（1）什么是栈？

栈（stack）是一种用于存储数据的简单数据结构。栈一个有序线性表，只能在表的一端（PS：栈顶）执行插人和删除操作。最后插人的元素将被第一个删除。所以，栈也称为后进先出（Last In First Out,LIFO）或先进后出（First In Last Out,FILO）线性表

（2）有关栈的几个基本概念：

  • 入栈（push）：表示在栈顶插入一个元素
  • 出栈（pop）：表示从栈中删除栈顶元素
  • 下溢（underflow）：试图对一个空栈执行出栈操作称为下溢
  • 溢出（overflow）：试图对一个满栈执行入栈操作称为溢出

（3）有关栈的几种基本操作：

注：为了简单起见，下面有关栈操作的数据类型均为整型

  • void push(int data)：入栈（将数据data插入到栈中）
  • int pop()：出栈（删除并返回最后一个插入栈的元素）
  • int top()：返回最后一个插入栈的元素，但不删除
  • int size()：返回存储在栈中的元素个数
  • boolean isEmpty()：返回栈是否是空栈
  • boolean isFull()：返回是否是满栈
  • void deleteStack()：删除整个栈

（4）栈的应用：

  • 符号匹配
  • HTML和XML文件中的标签（tag）匹配
  • 实现函数调用（包括递归）
  • 文本编辑器中的撤销（undo）序列
  • 网页浏览器中已访问页面的历史记录（后退(back)按钮）
  • 作为一个算法的辅助数据结构（如：树遍历算法）
  • 其他数据结构的组件（如：模拟队列）

二 栈的几种实现方式

栈抽象数据类型有多种实现方式，常见的有以下几种思路：

  1. 基于简单数组的实现方式
  2. 基于动态数组的实现方式
  3. 基于链表的实现方式

（1）基于简单数组的实现：

基于简单数组实现一个栈，其基本思路是这样的：从左至右向数组中添加所有的元素，并定义一个变量用来记录数组当前栈顶(top)元素的下标。当数组存满了栈元素时，执行入栈(插入元素)操作将抛出栈满异常；当对一个没有存储栈元素的数组执行出栈(删除元素)操作将抛出栈空异常

当然，这种实现方式有一个很明显的局限性。那就是：栈的最大空间必须预先声明且不能改变。试图对一个满栈执行入栈操作将会产生异常

（2）基于动态数组的实现：

基于动态数组的实现一个栈，其基本思路跟上面类似。不同的是，这种方式下当数组中存储的元素达到一定量时（如：数组空间的0.75或者整个数组空间），这时我们通常会选择新建一个比原数组空间大一倍的新数组，然后将原数组按照原来的顺序复制进去，接着便可以继续进行入栈操作了

Java 
package cn.zifangsky.stack;

import java.util.EmptyStackException;

/**
 * 使用重复倍增数据实现栈结构
 * @author zifangsky
 */
public class ArrayStack {
    private int top; //栈顶元素位置
    private int capacity; //栈的容量
    private int[] array; //存储栈的数组
    
    public ArrayStack() {
        capacity = 1;
        top = -1;
        array = new int[capacity];
    }
    
    /**
     * 返回栈是否是空栈
     * @时间复杂度 O(1)
     * @return
     */
    public boolean isEmpty(){
        return (top == -1);
    }
    
    /**
     * 返回是否是满栈
     * @时间复杂度 O(1)
     * @return
     */
    public boolean isFull(){
        return (top == capacity -1);
    }
    
    /**
     * 入栈
     * @时间复杂度 O(1)
     * @param data 入栈数据
     */
    public void push(int data){
        if(isFull()){
            doubleStack();
        }
        array[top+1] = data;
        top++;
    }
    
    /**
     * 出栈：移动栈顶指针并返回数据
     * @时间复杂度 O(1)
     * @return
     */
    public int pop(){
        if(isEmpty()){
            throw new EmptyStackException();
        }else{
            int result = array[top];
            top--;
            return result;
        }
    }
    
    /**
     * 返回最后一个插入栈的元素，但不删除
     * @时间复杂度 O(1)
     * @return
     */
    public int top(){
        if(isEmpty()){
            throw new EmptyStackException();
        }else{
            return array[top];
        }
    }
    
    /**
     * 返回存储在栈中的元素个数
     * @时间复杂度 O(1)
     * @return
     */
    public int size(){
        return top+1;
    }
    
    /**
     * 删除整个栈
     * @时间复杂度 O(1)
     */
    public void deleteStack(){
        top = -1;
    }
    
    /**
     * 将栈的容量扩大两倍
     */
    private void doubleStack(){
        int[] newArray = new int[capacity * 2];
        System.arraycopy(array, 0, newArray, 0, capacity);
        capacity = capacity * 2;
        array = newArray;
    }

}

测试代码如下：

Java 
  @Test
    public void testArrayStack(){
        ArrayStack arrayStack = new ArrayStack();
        arrayStack.push(1);
        arrayStack.push(2);
        arrayStack.push(3);
        arrayStack.push(4);
        arrayStack.push(5);
        
        System.out.println(arrayStack.pop());
        System.out.println(arrayStack.top());
        System.out.println(arrayStack.pop());
        System.out.println("剩余栈元素个数： " + arrayStack.size());
    }

测试代码输出如下：

5
4
4
剩余栈元素个数： 3

（3）基于链表的实现：

基于链表实现一个栈，其基本思路是这样的：通过在链表的表头插入元素的方式来实现push操作；通过删除链表的表头节点的方式来实现pop操作

Java 
package cn.zifangsky.stack;

import java.util.EmptyStackException;

import cn.zifangsky.linkedlist.SinglyNode;

public class LinkStack {

    private SinglyNode headNode;
    
    /**
     * 返回栈是否是空栈
     * @时间复杂度 O(1)
     * @return
     */
    public boolean isEmpty(){
        return headNode == null ? true : false;
    }
    
    /**
     * 入栈
     * @时间复杂度 O(1)
     * @param data 入栈数据
     */
    public void push(int data){
        if(headNode == null){
            headNode = new SinglyNode(data);
        }else{
            SinglyNode newNode = new SinglyNode(data);
            newNode.setNext(headNode);
            headNode = newNode;
        }
    }
    
    /**
     * 出栈：移动栈顶指针并返回数据
     * @时间复杂度 O(1)
     * @return
     */
    public int pop(){
        if(headNode == null){
            throw new EmptyStackException();
        }else{
            int data = headNode.getData();
            headNode = headNode.getNext();
            return data;
        }
    }
    
    /**
     * 返回最后一个插入栈的元素，但不删除
     * @时间复杂度 O(1)
     * @return
     */
    public int top(){
        if(headNode == null){
            throw new EmptyStackException();
        }else{
            return headNode.getData();
        }
    }
    
    /**
     * 返回存储在栈中的元素个数
     * @时间复杂度 O(n)
     * @return
     */
    public int size(){
        if(headNode == null){
            return -1;
        }else{
            int length = 0;
            SinglyNode currentNode = headNode;
            while (currentNode != null) {
                length++;
                currentNode = currentNode.getNext();
            }
            return length;
        }
    }
    
    /**
     * 删除整个栈
     * @时间复杂度 O(1)
     */
    public void deleteStack(){
        headNode = null;
    }
}

注：关于这里的SinglyNode（PS：表示单链表的一个节点）的定义可以参考我之前的这篇文章：www.zifangsky.cn/933.html

测试代码如下：

Java 
  @Test
    public void testLinkStack(){
        LinkStack linkStack = new LinkStack();
        linkStack.push(1);
        linkStack.push(2);
        linkStack.push(3);
        linkStack.push(4);
        linkStack.push(5);
        
        System.out.println(linkStack.pop());
        System.out.println(linkStack.top());
        System.out.println(linkStack.pop());
        System.out.println("剩余栈元素个数： " + linkStack.size());
    }

测试代码输出如下：

5
4
4
剩余栈元素个数： 3

三 基于数组实现和基于链表实现的比较

（1）基于数组实现的栈：

  • 各个操作都是常数时间开销
  • 每隔一段时间进行的倍增操作的时间开销较大

（2）基于链表实现的栈：

  • 栈规模的增加和减小都很容易
  • 各个操作都是常数时间开销
  • 每个操作都需要使用额外的空间和时间开销来处理指针

好了本篇文章到此结束，下篇文章将继续介绍有关栈的经典问题解析

avatar
文章
阅读
粉丝

友情链接：