淘宝api 做网站/代写平台在哪找
如何理解栈这种数据结构？
关于栈，我们生活中有非常多的例子，比如手枪弹夹中的子弹，往弹夹中一颗一颗从下往上压子弹，相当于入栈；而发射子弹只能从上面往下一颗一颗弹出子弹，相当于出栈。我们不能通过任何手段发射弹夹中间的子弹。先进着后出，后进着先出，这种结构就是典型的栈。
从上面的例子不难看出，栈是一种受限制的线性表，只允许在栈的顶端进行出栈和入栈操作。
为什么会出现栈这种数据结构？
我们前面学习过数组和链表，它们和栈一样都是线性表结构，而且没有栈在删除和添加时的操作限制。我们直接用数组和链表去代替栈是否可行？
答案是否定的，数组和链表可以在数据结构上代替栈，但是在一些需要使用到先进着后出，后进着先出业务场景的时候，数组和链表暴露了太多的接口去操作数据，可能会使数据不可控制。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选栈这种数据结构。
如何实现一个栈？
从栈的定义，我们不难看出栈有两种实现方式，分别是数组和链表。数组实现的栈是顺序栈，链表实现的栈是链式栈。
顺序栈(数组实现)
public class ArrayStack {
private int[] arr;//数组
private int count;//元素个数
private int size;//栈的大小
private final static int DEFAULT_SIZE=16; //默认容量
public ArrayStack(int size) {
this.arr=new int[size];
this.count=0;
this.size=size;
}
public ArrayStack() {
this.arr=new int[DEFAULT_SIZE];
this.count=0;
this.size=DEFAULT_SIZE;
}
/**
* 入栈
* @param a
*/
public void push(int a){
if (count==size){//如果栈满了，则申请一个2倍容量大小的数组，实现动态扩容
arr = Arrays.copyOf(arr, arr.length * 2);
}
arr[count]=a;
count++;
}
/**
* 出栈，将栈顶元素删除，并返回该元素
* @return 栈顶元素
*/
public int pop(){
if (count==0){//如果栈中元素为空
return -1;
}
int result=arr[count-1];
count--;
return result;
}
}
链式栈(链表实现)
/**
* 链式栈
*/
public class LinkedStack {
/**
* 定义一个链表
*/
private class Node{
private T data;
private Node next;
public Node() {
}
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
private Node topNode;//记录栈顶元素
private int size;//栈的大小
public LinkedStack() {
this.topNode = null;
this.size=0;
}
/**
* 入栈
* @param element
*/
public void push(T element){
topNode = new Node(element, topNode);//让新加入的节点指向老的节点
size++;
}
/**
* 移除栈顶元素并返回
* @return
*/
public T pop(){
Node oldTop=topNode;
topNode= topNode.next;
oldTop.next=null;
size--;
return oldTop.data;
}
}
链式栈(链表实现)
/**
* 链式栈
*/
public class LinkedStack {
/**
* 定义一个链表
*/
private class Node{
private T data;
private Node next;
public Node() {
}
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
private Node topNode;//记录栈顶元素
private int size;//栈的大小
public LinkedStack() {
this.topNode = null;
this.size=0;
}
/**
* 入栈
* @param element
*/
public void push(T element){
topNode = new Node(element, topNode);//让新加入的节点指向老的节点
size++;
}
/**
* 移除栈顶元素并返回
* @return
*/
public T pop(){
Node oldTop=topNode;
topNode= topNode.next;
oldTop.next=null;
size--;
return oldTop.data;
}
}
leetcode上关于栈的练习题：20,155,232,844,224,682,496.
本文是关于数据结构的栈，希望大家可以和我一起学习成长，早日找到自己想要的生活。
我是方褚，一个努力成长的程序员。
希望可以多多转发、收藏、关注！！