自学内容网 自学内容网

【数据结构】栈

一、栈的概念

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();
    }
}


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

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