一、什么是栈？
栈是一种“操作受限”的线性表，只允许在一端插入和删除数据，后进者先出，先进者后出。
无论是数组或者是链表都可以实现栈的功能，栈只是一种特性的数据结构，可以理解为封装好的数组或者是封装好的链表。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这时我们就应该首选“栈”这种数据结构。
二、实现栈
栈的主要操作是入栈和出栈，入栈和出栈，也就是在栈顶插入一个数据和从栈顶删除一个数据。
实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。
一.顺序栈的实现（由数组封装）
这段代码是大佬自己写的，我参考一下，并写一个自己的顺序栈，链式栈的我自己写。
//大佬的代码
// 基于数组实现的顺序栈
public class ArrayStack {
private String[] items; // 数组
private int count; // 栈中元素个数
private int n; //栈的大小
// 初始化数组，申请一个大小为n的数组空间
public ArrayStack(int n) {
this.items = new String[n];
this.n = n;
this.count = 0;
}
// 入栈操作
public boolean push(String item) {
// 数组空间不够了，直接返回false，入栈失败。
if (count == n) return false;
// 将item放到下标为count的位置，并且count加一
items[count] = item;
++count;
return true;
}
// 出栈操作
public String pop() {
// 栈为空，则直接返回null
if (count == 0) return null;
// 返回下标为count-1的数组元素，并且栈中元素个数count减一
String tmp = items[count-1];
--count;
return tmp;
}
}
//我自己的代码
package stackdemo;
public interface Stack<T> {
/**
* 栈是否为空
* @return
*/
boolean isEmpty();
/**
* data元素入栈
* @param data
*/
boolean push(T data);
/**
* 返回栈顶元素,未出栈
* @return
*/
T peek();
/**
* 出栈,返回栈顶元素,同时从栈中移除该元素
* @return
*/
T pop();
}
package stackdemo;
import java.io.Serializable;
public class ArrayStack<T> implements Stack<T>, Serializable {
/**
* 容量大小默认为10
*/
private int defaultLength = 10;
/**
* 存放元素的数组
*/
private T[] array;
/**
* 栈内元素个数
*/
private int stackSize;
/**
* 带参构造
*/
public ArrayStack(int defaultLength) {
array = (T[]) new Object[defaultLength];
}
/**
* 无参构造
*/
public ArrayStack() {
array = (T[]) new Object[defaultLength];
}
/**
* 栈是否为空
*/
@Override
public boolean isEmpty() {
if (stackSize == 0)
return true;
return false;
}
/**
* 入栈
*/
@Override
public boolean push(T data) {
//这里可以设置为自动扩容
if (stackSize == defaultLength) {
return false;
}
array[stackSize]=data;
stackSize++;
return true;
}
/**
* 返回栈顶元素
*/
@Override
public T peek() {
if (stackSize == 0) {
return null;
} else {
T t = array[stackSize - 1];
return t;
}
}
/**
* 出栈
*/
@Override
public T pop() {
if (stackSize == 0) {
return null;
} else {
T t = array[stackSize-1];
array[stackSize - 1] = null;
stackSize--;
return t;
}
}
}
package stackdemo;
/**
* 测试
*/
public class ArrayStackTest {
public static void main(String[] args) {
ArrayStack<String> arrayStack=new ArrayStack<String>();
System.out.println(arrayStack.isEmpty());
System.out.println(arrayStack.push("1234567"));
System.out.println(arrayStack.isEmpty());
System.out.println(arrayStack.peek());
System.out.println(arrayStack.pop());
System.out.println(arrayStack.isEmpty());
}
}
执行结果
二.链式栈的实现（由链表封装）
package stackdemo;
import java.io.Serializable;
import java.util.LinkedList;
public class ListStack<T> implements Stack<T>, Serializable {
private LinkedList<T> linkedList;
private int listSize;
public ListStack() {
linkedList=new LinkedList<T>();
}
@Override
public boolean isEmpty() {
if (linkedList.isEmpty())
return true;
return false;
}
@Override
public boolean push(T data) {
//add加在尾部，push加在头部
linkedList.add(data);
listSize++;
return true;
}
@Override
public T peek() {
if (linkedList.isEmpty())
return null;
return linkedList.get(listSize - 1);
}
@Override
public T pop() {
if (linkedList.isEmpty())
return null;
T t = linkedList.remove(listSize - 1);
listSize--;
return t;
}
}
package stackdemo;
/**
* 测试
*/
public class ArrayStackTest {
public static void main(String[] args) {
// ArrayStack<String> arrayStack=new ArrayStack<String>();
// System.out.println(arrayStack.isEmpty());
// System.out.println(arrayStack.push("1234567"));
// System.out.println(arrayStack.isEmpty());
// System.out.println(arrayStack.peek());
// System.out.println(arrayStack.pop());
// System.out.println(arrayStack.isEmpty());
ListStack<String> listStack = new ListStack<String>();
System.out.println(listStack.isEmpty());
System.out.println(listStack.push("1234567"));
System.out.println(listStack.isEmpty());
System.out.println(listStack.peek());
System.out.println(listStack.pop());
System.out.println(listStack.isEmpty());
}
}
执行结果：
三、栈的应用
四、数据结构堆栈和内存中的堆栈的区别
内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象的数据存储结构。
内存空间在逻辑上分为三部分：代码区、静态数据区和动态数据区，动态数据区又分为栈区和堆区。
代码区：存储方法体的二进制代码。高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）控制代码区执行代码的切换。
静态数据区：存储全局变量、静态变量、常量，常量包括final修饰的常量和String常量。系统自动分配和回收。
栈区：存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。
堆区：new一个对象的引用或地址存储在栈区，指向该对象存储在堆区中的真实数据。
版权声明：本文不是「本站」原创文章，版权归原作者所有 | 原文地址: