【数据结构】栈

🕗 发布于 2024-07-21 19:34 数据结构 java android 开发语言

一、栈的概念

1.栈的定义

栈(Stack):只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。
他是一种”先进后出“的数据结构
在这里插入图片描述

栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表

2.栈的常见基本操作

InitStack(&S)：初始化一个空栈S。
StackEmpty(S)：判断一个栈是否为空，若栈为空则返回true，否则返回false。
Push(&S, x)：进栈（栈的插入操作），若栈S未满，则将x加入使之成为新栈顶。
Pop(&S, &x)：出栈（栈的删除操作），若栈S非空，则弹出栈顶元素，并用x返回。
GetTop(S, &x)：读栈顶元素，若栈S非空，则用x返回栈顶元素。
DestroyStack(&S)：栈销毁，并释放S占用的存储空间（“&”表示引用调用）。

二、栈的顺序存储结构

1.栈的顺序存储结构

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判断条件定位top等于-1。

若现在有一个栈，StackSize是5，则栈的普通情况、空栈、满栈的情况分别如下图所示：
在这里插入图片描述

2.共享栈(两栈共享空间)(双端栈)

(1)共享栈概念

利用栈底位置相对不变的特征，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，如下图所示：在这里插入图片描述

两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=MaxSize时1号栈为空；仅当两个栈顶指针相邻（top0+1=top1）时，判断为栈满。当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减一再赋值出栈时则刚好相反。

双端栈是线性表的一种,更是栈的一个特殊分类，可用借用动态数组+栈的组合实现。

(2)特点

双端栈的特点是可以从两个方向进行操作，即从左侧插入和删除元素，也可以从右侧插入和删除元素。这使得双端栈在某些场景下可以提供更灵活的操作和更高的效率。

(3)实例

使用Java的Deque实现双端栈的演示实例：

public class DequeStack {
    private Deque<Integer> deque;
 
    public DequeStack() {
        deque = new ArrayDeque<>();
    }
 
    public void push(int item) {
        deque.push(item);
    }
 
    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return deque.pop();
    }
 
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return deque.peek();
    }
 
    public boolean isEmpty() {
        return deque.isEmpty();
    }
 
    public int size() {
        return deque.size();
    }
}

在这个示例中，我们使用了Java的Deque，具体是ArrayDeque实现类。ArrayDeque是基于可调整大小的数组实现的双端队列，可以在队列的两端进行插入和删除操作。我们将其作为双端栈的底层数据结构来实现。

通过双端栈，我们可以在栈顶和栈底进行元素的插入和删除操作。例如：

DequeStack stack = new DequeStack();
stack.push(1);
stack.push(2);
 
System.out.println(stack.peek()); // 输出：2
 
stack.push(3);
stack.push(4);
 
System.out.println(stack.pop()); // 输出：4
 
stack.push(5);
 
System.out.println(stack.pop()); // 输出：5
System.out.println(stack.pop()); // 输出：3
System.out.println(stack.pop()); // 输出：2
System.out.println(stack.isEmpty()); // 输出：true

三、栈的链式存储结构

1.链栈

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头节点，Lhead指向栈顶元素
如下图所示。
在这里插入图片描述
对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL的时候。

2.性能比较

链栈的进栈push和出栈pop操作都很简单，时间复杂度均为O(1)。
对比一下顺序栈与链栈,它们在时间复杂度上是一样的,均为O(1)。
空间：1.顺序栈需要确定一个连续的长度，可能会存在内存浪费现象
优点：定位方便
2.链栈要求每个元素都要有指针域，会增加内存开销
对栈的长度无限制
如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些。

四、Stack的常用方法

方法名称	类型	说明
public Stack()	构造方法	创建Stack对象
public E Stack(E item)	普通方法	入栈
public synchronized E pop()	普通方法	出栈
public synchronized E peek()	普通方法	获取栈顶元素
public boolean empty()	普通方法	判断栈是否为空
public synchronized int search(Object o)	普通方法	基于栈顶位置(索引为1，索引自栈顶向栈底自增) 查找对象o，如果找到了返回索引值，否则返回-1

代码

public class MyStack {
    public int[] elem; //数组 -> 栈空间
    public int usedSize;//有效数据
    public MyStack(){
        this.elem = new int[5];
        this.usedSize = 0;
    }
    //入栈
    public void push(int val){
        //如果栈满了就进行扩容
        if(isFull()){
            this.elem = Arrays.copyOf(elem,2*this.elem.length);
        }
        this.elem[this.usedSize] = val;
        usedSize++;
    }
    //判断栈是否满
    public boolean isFull(){
        return usedSize==this.elem.length;
    }
 
    //出栈
    public int pop(){
        if(isEmpty()){
            throw new NullPointerException("栈为空！");
        }
        int oldVal = this.elem[usedSize-1];
        this.usedSize--;
        return oldVal;
    }
    //判断栈是否为空
    public boolean isEmpty(){
        return this.usedSize==0;
    }
 
    //读取栈顶元素
    public int peek(){
        if(isEmpty()){
            throw new NullPointerException("栈为空！");
        }
        return this.elem[usedSize-1];
    }
}

测试类

public class TestDemo1 {
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(1);//入栈
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        System.out.println(myStack.peek());//获取栈顶元素
        System.out.println(myStack.pop());//出栈
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.isEmpty());//判断栈是否为空，如果为空返回true，否则返回false
    }
}

运行结果：

4
4
3
2
1
true

五、栈的使用

在这里插入图片描述
在集合框架中，Stack（栈）是一个普通的类，实现了List接口，具体框架图如下：

注意：

Stack实现了RandomAccess接口，表明Stack支持随机访问
Stack实现了Cloneable接口，表明Stack是可以clone的
Stack实现了Serializable接口，表明Stack是支持序列化的
Vector（向量）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。
Vector 与 ArrayList 基本是一致的，不同的是Vector是线程安全的，会在可能出现线程安全的方法前面使用 synchronized 关键字。

六、栈的几种实现方式

1.基于简单数组的实现方式

使用简单数组作为底层数据结构来实现栈，通过将栈顶元素的索引存储在变量中，实现压栈和弹栈操作，每次压栈时将元素添加到数组末尾，每次弹栈时将栈顶元素从数组中删除。由于数组的长度是固定的，需要提前定义栈的最大容量。

public class ArrayStack {
    private int[] stack;
    private int top;
 
    public ArrayStack(int capacity) {
        stack = new int[capacity];
        top = -1;
    }
 
    public void push(int item) {
        if (top == stack.length - 1) {
            throw new IllegalStateException("Stack is full");
        }
        stack[++top] = item;
    }
 
    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return stack[top--];
    }
 
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return stack[top];
    }
 
    public boolean isEmpty() {
        return top == -1;
    }
}

2.基于动态数组的实现方式

使用动态数组（如ArrayList）作为底层数据结构来实现栈，通过在动态数组的尾部进行插入和删除操作来实现栈的功能。当栈容量不足时，动态数组可以自动进行扩容，当栈元素减少时，动态数组可以自动进行缩容。这种实现方式提供了动态调整容量的特性。

public class DynamicArrayStack {
    private ArrayList<Integer> stack;
 
    public DynamicArrayStack() {
        stack = new ArrayList<>();
    }
 
    public void push(int item) {
        stack.add(item);
    }
 
    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return stack.remove(stack.size() - 1);
    }
 
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return stack.get(stack.size() - 1);
    }
 
    public boolean isEmpty() {
        return stack.isEmpty();
    }
}

3.基于链表的实现方式

使用链表作为底层数据结构来实现栈，链表的头部或尾部作为栈顶，每次插入和删除操作都在链表的头部进行，通过修改引用来实现栈的操作。链表实现的栈可以动态增加和缩小容量，不需要提前定义栈的最大容量，但相对于数组实现，需要更多的空间开销。

public class LinkedListStack {
    private Node top;
 
    private class Node {
        int data;
        Node next;
 
        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
 
    public LinkedListStack() {
        top = null;
    }
 
    public void push(int item) {
        Node newNode = new Node(item);
        if (isEmpty()) {
            top = newNode;
        } else {
            newNode.next = top;
            top = newNode;
        }
    }
 
    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        int item = top.data;
        top = top.next;
        return item;
    }
 
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return top.data;
    }
 
    public boolean isEmpty() {
        return top == null;
    }
}

基于数组的实现与基于链表的实现的区别

(1)基于数组的实现

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

(2) 基于链表实现的栈：

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

4.基于队列的实现方式

使用队列作为底层数据结构来实现栈，可以使用两个队列来模拟栈的操作。当压栈时，将元素添加到非空队列中；当弹栈时，将非空队列中的元素依次弹出并放入另一个空队列中，直到剩下最后一个元素，即栈顶元素，然后弹出。这种实现方式可以保持栈顶元素总是在队列的尾部，模拟了栈的后进先出（LIFO）特性。

public class QueueBasedStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;
    private int top;
 
    public QueueBasedStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
 
    public void push(int item) {
        queue1.add(item);
        top = item;
    }
 
    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        while (queue1.size() > 1) {
            top = queue1.remove();
            queue2.add(top);
        }
        int item = queue1.remove();
        Queue<Integer> tempQueue = queue1;
        queue1 = queue2;
        queue2 = tempQueue;
        return item;
    }
 
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return top;
    }
 
    public boolean isEmpty() {
        return queue1.isEmpty();
    }
}

原文地址：https://blog.csdn.net/qq_55846232/article/details/140561052

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【数据结构】二叉搜索树
下一篇：[MMU]现代计算机内存管理

Linux系统下svn新建目录
Linux安装svn自行查找。
阅读更多2024-11-14
Scala的不可变Map常用操作
/3.1 get方法：输入key，如果找到，就返回包装数据，如果没有找到，就返回None。val map1 = Map("鄂"->"湖北省","
阅读更多2024-11-14
mqtt学习笔记（一）
mqtt相关笔记（一）之mqtt初探，以提出、解决问题的方式来逐步学习
阅读更多2024-11-14
Ken和Bwk趣说UNIX
[肯汤普森和布莱恩(AWK作者之一)趣说UNIX](https://www.bilibili.com/video/BV1nP411t7gt/ “肯汤普森和布莱恩(AWK作者之一 “肯汤普森和布莱恩(A
阅读更多2024-11-14
【CentOS】中的Firewalld：全面介绍与实战应用（上）
本文深入探讨了CentOS操作系统中Firewalld防火墙的全面功能与实战应用。首先，文章概述了Firewalld的基本概念，强调了它在现代Linux系统中作为动态管理防火墙规则的重要工具的地位。与
阅读更多2024-11-14
新手小白学习docker第七弹------安装redis集群大厂面试
新手小白学习docker第七弹----安装redis集群大厂面试
阅读更多2024-11-14
/// ts中的三斜线指令 | 前端
包），你需要在你的项目中以某种方式告诉TypeScript编译器这些类型定义的存在。三斜线指令是一种在单个文件中这样做的方式，虽然在实际项目中，更常见的是通过。1. 这行代码是TypeScript中
阅读更多2024-11-14
快速掌握——python类封装[私有属性方法]、继承【python进阶】(内附代码)
python类的封装【私有属性、私有方法、属性装饰器】类的继承
阅读更多2024-11-14
2024年5款大屏可视化工具多维分析对比
经过对市场上多款大屏可视化工具的深入研究和对比，强烈推荐FineVis作为您的首选。无论您是希望快速搭建大屏项目、展示复杂3D模型还是实现多屏适应和实时数据分析，FineVis都能满足您的需求。文章中
阅读更多2024-11-14
计算机网络-mac地址与ip地址的区别总结
mac地址在OSI模型中的第二层数据链路层工作，数据链路层基于mac地址进行转发数据帧【交换机基于mac地址表转发数据】ip地址在OSI模型中的第三层网络层工作，网络层基于ip地址转发报文【路由器
阅读更多2024-11-14