数据结构--栈详解
前言
大家好呀，今天我们学习数据结构之栈篇，这是一种很简单的数据结构，今天我们将从概念，用法和模拟实现三个面开始学习
一，概念和性质
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作
。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出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两篇博文，那么今天博文就到这里，谢谢大家
Ongwu博客 版权声明：以上内容未经允许不得转载！授权事宜或对内容有异议或投诉，请联系站长，将尽快回复您，谢谢合作！