数据结构--栈详解

前言

          大家好呀，今天我们学习数据结构之栈篇，这是一种很简单的数据结构，今天我们将从概念，用法和模拟实现三个面开始学习

一，概念和性质

       栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
      压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
      出栈：栈的删除操作叫做出栈。出数据在栈顶。

在实际应用中一定要注意栈的先进后出的性质

二，栈的使用

栈主要有以下几种方法

我们可以自己构造一个栈测试他的功能

import java.util.Stack;public class Main {public static void main(String[] args) {Stack<Integer> stack=new Stack<>();stack.push(0);stack.push(1);stack.push(2);for (Integer x : stack) {System.out.printf(x+" ");}System.out.println();stack.pop();for (Integer x : stack) {System.out.printf(x+" ");}System.out.println();System.out.println(stack.peek());stack.pop();stack.pop();System.out.println(stack.empty());}
}

三，栈的模拟实现

        Java中的栈底层是一个基于数组的动态数据结构。但是，值得一提的是，因为性能问题和不支持泛型，Stack类已经不推荐使用，ArrayDeque作为栈的替代，ArrayDeque支持两端出入，因此既可以作为栈也可以作为队列使用，当然，当ArrayDeque作为栈时，用法和Stack相同。

       我们可以通过数组，链表，和双向链表实现栈，本文使用数组实现，用链表和双向链表也十分简单，我们只需注意用链表实现栈时，需要把头节点作为栈顶，这样才能实现O（1）时间复杂度的插入和删除

模拟实现

class MyStack{int[] stack;int Size;MyStack(){stack=new int[3];}private boolean Full(){return stack.length==Size;}private void Grow(){this.stack= Arrays.copyOf(stack,2*stack.length);}public void push(int val){if(Full()) {Grow();}else {stack[Size]=val;Size++;}}public int pop(){if(empty()){return -1;}else{int x=stack[Size-1];Size--;return stack[x];}}public int peek(){if(empty()){return -1;}else{return stack[Size-1];}}public boolean empty(){return Size==0;}}

四，栈的相关练习

1.最小括号. - 力扣（LeetCode）

2.波兰表达式求值. - 力扣（LeetCode）

3.出栈入栈次序匹配栈的压入、弹出序列_牛客题霸_牛客网

答案可参考
CCSDNhttps://mp.csdn.net/mp_blog/creation/editor/140336572https://mp.csdn.net/mp_blog/creation/editor/140336572和CSDN

两篇博文，那么今天博文就到这里，谢谢大家