【数据结构】栈

  • 开发
  • 15

文章目录

一、栈的概念

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接口，具体框架图如下：
在这里插入图片描述
注意：

  1. Stack实现了RandomAccess接口，表明Stack支持随机访问
  2. Stack实现了Cloneable接口，表明Stack是可以clone的
  3. Stack实现了Serializable接口，表明Stack是支持序列化的
  4. Vector（向量）是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。
  5. 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();
    }
}
阅读全部

相关推荐

  4. 数据结构--栈

    2024-07-21 17:50:01       50 阅读

  5. 数据结构-栈

    2024-07-21 17:50:01       51 阅读

  10. 数据结构---栈(Stack)

    2024-07-21 17:50:01       55 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-21 17:50:01       52 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-21 17:50:01       54 阅读

  9. 在Django里面运行非项目文件

    2024-07-21 17:50:01       45 阅读

  19. Python语言-面向对象

    2024-07-21 17:50:01       55 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-21 17:50:01       50 阅读

热门阅读

  3. Python基本语法

    2024-07-21 17:50:01       18 阅读

  4. GPU算力租用平台推荐

    2024-07-21 17:50:01       20 阅读

  9. 文本溢出显示省略号

    2024-07-21 17:50:01       15 阅读

  10. 简单回顾C++常用的数据类型

    2024-07-21 17:50:01       18 阅读

  14. https和http有哪些区别？

    2024-07-21 17:50:01       18 阅读

  15. stable diffusion Sampler 的选择

    2024-07-21 17:50:01       18 阅读

  18. 读书记 | 《李光耀观天下》

    2024-07-21 17:50:01       16 阅读

  26. resultMap

    2024-07-21 17:50:01       16 阅读

  27. set、multiset、unordered_set的区别以及常见用法 + 基本位运算bitset常见用法

    2024-07-21 17:50:01       15 阅读

  28. Python编程防止计算机休眠，保持唤醒状态

    2024-07-21 17:50:01       14 阅读