数据结构之栈的讲解

简介: 数据结构之栈的讲解

💕"

春宵一刻值千金,花有清香月有阴。

"💕

作者:Mylvzi

文章主要内容:leetcode刷题之哈希表的应用(1)

1.栈的概念

 栈是一种只允许在一端(栈顶)进行数据操作的数据结构,具有“后进先出”的特性,也叫做Last in First Out

最常见的现实生活中的例子就是压子弹  只能一端压子弹

2.栈的模拟实现

 我们想想什么可以实现栈的操作呢?我们知道,栈最大的特性就行只能在一端进行数据操作,使用数组可以更好的模拟栈

 数组的末尾就是我的栈顶,操作栈顶就是操作数组的最后一个元素,而数组最后一个元素的添加,删除都很方便!!!

1.使用数组模拟

public class MyStack {
    /**
     * 栈的实现一:用数组实现栈
     */
    private int[] elem;
    private int usedSize;
    private static final int DEFAULTCAPACITY = 10;
    public MyStack() {
        this.elem = new int[DEFAULTCAPACITY];
    }
    public MyStack(int size) {
        this.elem = new int[size];
    }
    public void push(int val) {
        if (isFull()) {
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[usedSize] = val;
        this.usedSize++;
    }
    private boolean isFull() {
        return this.usedSize == this.elem.length;
/*        if (this.elem.length == this.usedSize) {
            return true;
        }
        return false;*/
    }
    public int pop() {
        if (isEmpty()) {
            throw new StackEmptyException("栈区之内不含有数据,无法删除");
        }
//        this.usedSize--;
//        return this.elem[usedSize];
        int oldVal = this.elem[usedSize-1];
        this.usedSize--;
        return oldVal;
    }
    public int peek() {
        if (isEmpty()) {
            throw new StackEmptyException("栈区之内不含有数据,无法删除");
        }
        return this.elem[usedSize-1];
    }
    public boolean isEmpty() {
        return this.usedSize == 0;
/*        if (this.usedSize == 0) {
            return true;
        }
        return false;*/
    }
}

2.使用链表模拟

当然除了使用数组模拟栈,使用链表也可以实现栈的功能(Java中的LinkedList本质上是一个无头双向非循环链表)

class Mystack3 {
    // 使用链表模拟栈
    /**
     * 栈只能在一端进行数据的操作
     * 在这里我们只在链表的last进行数据的操作
     */
    LinkedList<Integer> mystack = new LinkedList<>();
    // push
    public void push(int data) {
        mystack.addLast(data);
    }
    // pop
    public int pop() {
        if(mystack.isEmpty()) {
            return -1;// 抛异常也可以
        }
        return mystack.pollLast();
    }
    public int peek() {
        return mystack.peekLast();
    }
    public static void main(String[] args) {
        Mystack3 mystack3 = new Mystack3();
        mystack3.push(1);
        mystack3.push(2);
        mystack3.push(3);
        System.out.println(mystack3.pop());// 3
        System.out.println(mystack3.peek());// 2
    }
}

3.Java中的栈Stack

 Java中提供了现成的栈供我们使用

代码演示

// 栈的创建  栈在Java中就是一个类!!!
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        // 使用构造器
        Iterator<Integer> it= stack.iterator();
        while (it.hasNext()) {
            System.out.print(it.next()+" ");// 1 2 3 4
        }
        System.out.println();
        System.out.println("============================");
        // 重写了toString方法  直接传对象 即可打印内容
        System.out.println(stack);// 1 2 3 4
        // pop会删除栈顶元素
        stack.pop();
        System.out.println(stack);// 1 2 3
        // peek  瞄一眼  不会把top删除
        int x = stack.peek();
        System.out.println(x);// 3
    }

4.栈的应用场景

1.括号匹配问题

分析:

代码实现:

class Solution {
    public static boolean isValid(String s) {
        if(s.length() % 2 != 0) return false;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            // 获取当前字符
            char ch = s.charAt(i);
            // 左括号
            if(ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            }else {// 右括号
                if(stack.isEmpty()) {
                   return false;
                }else {
                    // 要进行括号匹配
                    char top = stack.peek();
                    if(ch == '}' && top == '{' || ch == ')' && top == '(' ||ch == ']' && top == '[') {
                        stack.pop();
                    }else {
                        return false;
                    }
                }
            }
        }
        return stack.isEmpty();
    }
}

也可以使用顺序表实现

class Solution {
    public static boolean isValid(String s) {
        if(s.length() % 2 != 0) return false;
        List<Character> list = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            // 获取当前字符
            char ch = s.charAt(i);
            // 左括号
            if(ch == '(' || ch == '{' || ch == '[') {
                list.add(ch);
            }else {// 右括号
                if(list.isEmpty()) {
                   return false;
                }else {
                    // 要进行括号匹配
                    char top = list.get(list.size()-1);
                    if(ch == '}' && top == '{' || ch == ')' && top == '(' ||ch == ']' && top == '[') {
                        list.remove(list.size()-1);
                    }else {
                        return false;
                    }
                }
            }
        }
        return list.isEmpty();
    }
}

2.后缀表达式

代码实现:

class Solution {
    public int evalRPN(String[] tokens) {
        // 遇到数字存放到栈中
        Stack<Integer> stack = new Stack<>();
        // 循环遍历所给字符串
        for(String s : tokens) {
            // 数字
            if(!isOperation(s)) {
                // 是数字就push
                stack.push(Integer.parseInt(s));
            }else {// 运算符
            // 先弹出的作右运算符  后弹出的是左运算符
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch(s) {
                    case "+":
                        stack.push(num1+num2);
                        break;
                    case "-":
                        stack.push(num1-num2);
                        break;
                    case "*":
                        stack.push(num1*num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;    
                }
            }
        }
        // 遍历完  返回栈的最后一个(唯一一个)元素
        return stack.pop();
    }
    // 判断是否是运算符
    private boolean isOperation(String s) {
        if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
            return true;
        }
        return false;
    }
}

3.最小栈

分析思路:

代码实现:使用两个栈

class MinStack {
        //思路1 使用两个栈
        private Stack<Integer> stack;
        private Stack<Integer> minstack;// 存放过程中的最小值
        public MinStack() {
            this.stack = new Stack<>();
            this.minstack = new Stack<>();
        }
        public void push(int val) {
            if(minstack.isEmpty()) {
                minstack.push(val);
            }else {
                if (val <= minstack.peek()) {
                    minstack.push(val);
            }
            }
            stack.push(val);
        }
        public void pop() {
            if(!stack.isEmpty()) {
                int top = stack.pop();
                if (top == minstack.peek()) {
                    minstack.pop();
            }
            }
        }
        public int top() {
            if(stack.empty()) {
            return -1;
        }
            return stack.peek();
        }
        public int getMin() {
            if (minstack.isEmpty()) {
                return -1;
            }
            return minstack.peek();
        }
    }

思路2:使用链表实现

画图分析

代码实现

class MinStack {
        // 使用链表实现
        private class Node{
            int val;
            int min;
            Node next = null;
            public Node(int val, int min) {
                this.val = val;
                this.min = min;
            }
        }
        private Node head;
        public void push(int x) {
            if(head == null) {
                head = new Node(x,x);
            }else {
                Node newNode = new Node(x,Math.min(x,head.min));
                newNode.next = head;
                head = newNode;
            }
        }
        public void pop() {
            head = head.next;
        }
        public int top() {
            return head.val;
        }
        public int getMin() {
            return head.min;
        }
    }

4.用栈实现队列

232. 用栈实现队列 - 力扣(LeetCode)

class MyQueue {
    // 只需要转移一次就能实现顺序的完全颠倒
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    public void push(int x) {
        // stack1的栈底元素才是我第一个要出的元素
        stack1.push(x);
    }
    public int pop() {
        // 只有当s2为空的时候才需要从s1中转移数据,否则就一直出s2中的数据即可
        if(stack2.empty()) {
            while(!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
    public int peek() {
        if (stack2.empty()) {
            while(!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
    public boolean empty() {
        return stack2.empty() && stack1.empty();
    }
}

5.栈的压入、弹出序列

栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

使用一个辅助站来模拟栈的入栈和出栈

代码实现

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型一维数组 
     * @param popV int整型一维数组 
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        // 使用辅助栈 模拟出栈的过程
        Stack<Integer> stack = new Stack<>();
        // j去遍历入栈数组
        int j = 0;
        for (int i = 0; i < pushV.length; i++) {
            // 当j没有遍历完  &&(栈为空 || 栈顶和出栈的数组的元素不同)--入栈
            while(j< pushV.length &&(stack.isEmpty() || stack.peek()!=popV[i])) {
                stack.push(pushV[j++]);
            }
            // 出循环  栈顶和popV[i]相等
            if(stack.peek() == popV[i]) {
                stack.pop();
            }else {
                return false;
            }
        }
        return true;
    }
}

思路2:开辟辅助栈  遍历入栈序列  相等就出栈  最后判断栈是否为空

public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        // 使用辅助栈 模拟出栈的过程
        Stack<Integer> stack = new Stack<>();
        int j = 0;// 遍历出栈序列
        for (int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
            while (!stack.isEmpty() && stack.peek() == popV[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }

思路3:使用size来抽象代替栈的元素个数

 把入栈序列遍历完,最后看是否为空

public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        int size = 0,j=0;
        for (int num:pushV) {
            pushV[size] = num;
            // 出栈序列和栈顶元素相等  模拟出栈
            while(size >=0 && popV[j] == pushV[size]) {
                size--;
                j++;
            }
            size++;
        }
        return size == 0;
    }

使用下标+数组可以模拟栈的操作,使空间复杂度为0(1)

目录
打赏
0
0
0
0
2
分享
相关文章
|
3月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
359 9
|
3月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
58 1
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
146 77
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
50 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
49 9
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
42 7
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
103 5
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
122 21
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等