栈 | 如何使用数组和链表实现“栈”
栈 | 如何使用数组和链表实现“栈”
栈是用来存储逻辑关系为 "一对一" 数据的线性存储结构
后进去先出来。
栈的存储结构中关键的在于：存与取。 栈只能从表的一端存取数据，另一端是封闭的 在栈中，无论是存数据还是取数据，都必须遵循"先进后出（LIFO）"的原则，即最先进栈的元素最后出栈。上图 的栈来说，从图中数据的存储状态可判断出，元素 1 是最先进的栈。因此，当需要从栈中取出元素 1 时，根据"先进后出"的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1。
把上图的栈立起来就是这样子的（这样或许更好理解）。
实现一个栈的数据结构，使其具有以下方法：压栈、弹栈、取栈顶元素、判断栈是否为空以及获取栈中元素个数。下面是一个栈的入栈和出栈整个过程
栈的实现有两种方法，分别为采用数组来实现和采用链表来实现。下面分别详细介绍这两种方法。
数组实现
分析
在采用数组来实现栈的时候，栈空间是一段连续的空间。实现思路如下图所示
从上图中可以看出，可以把数组的首元素当作栈底，同时记录栈中元素的个数size，假设数组首地址为arr，压栈的操作其实是把待压栈的元素放到数组arrsize中，然后执行size++操作；同理，弹栈操作其实是取数组arrsize-1元素，然后执行size--操作。根据这个原理可以非常容易实现栈。
代码实现
/**
* 数组使用栈
*
* @author tian
* @date 2020/4/26
*/
public class MyStackDemo {
public static void main(String[] args) {
ArrayStack<Integer> stackDemo = new ArrayStack();
//入栈两个元素
stackDemo.push(1);
stackDemo.push(2);
System.out.println("栈顶元素：" + stackDemo.top());
System.out.println("栈大小：" + stackDemo.size());
stackDemo.pop();
System.out.println("栈第一次弹出元素");
stackDemo.pop();
System.out.println("栈第二次弹出元素");
stackDemo.pop();
}
}
class ArrayStack<T> {
private ArrayList<T> arrayList;
private int stackSize;
public ArrayStack() {
this.stackSize = 0;
this.arrayList = new ArrayList<>();
}
int size() {
return stackSize;
}
boolean isEmpty() {
return this.stackSize == 0;
}
//返回栈顶元素
T top() {
if (isEmpty()) {
return null;
}
return arrayList.get(stackSize - 1);
}
//元素出栈
T pop() {
if (stackSize > 0) {
return arrayList.get(--stackSize);
} else {
System.out.println("栈中无元素了");
return null;
}
}
//元素入栈
void push(T item) {
arrayList.add(item);
stackSize++;
}
}运行输出
链表实现
分析
在创建链表的时候经常采用一种从头结点插入新结点的方法，可以采用这种方法来实现栈，最好使用带头结点的链表，这样可以保证对每个结点的操作都是相同的，实现思路如下图所示。
在上图中，在进行压栈操作时，首先需要创建新的结点，把待压栈的元素放到新结点的数据域中，然后只需要（1）和（2）两步就实现了压栈操作（把新结点加到了链表首部）。同理，在弹栈的时候，只需要进行步骤（3）的操作就可以删除链表的第一个元素，从而实现弹栈操作。
代码实现
/**
* 数组实现栈
*
* @author tian
* @date 2020/4/26
*/
public class NodeStackDemo<T> {
private MyNode<T> head;
public NodeStackDemo() {
this.head = new MyNode<>();
head.data = null;
head.next = null;
}
//判断栈是否为空
boolean isEmpty() {
return head == null;
}
//栈的大小
int size() {
int size = 0;
MyNode<T> p = head.next;
while (p != null) {
p = p.next;
size++;
}
return size;
}
void push(T e) {
MyNode<T> temp = new MyNode<>();
temp.data = e;
temp.next = head.next;
head.next = temp;
}
//出栈，同时返回栈顶元素
T pop() {
MyNode<T> temp = head.next;
if (temp != null) {
head.next = temp.next;
return temp.data;
}
System.out.println("占中已经不存元素了");
return null;
}
//获取栈顶元素
T top() {
if (head.next != null) {
return head.next.data;
}
System.out.println("栈中不存在元素");
return null;
}
public static void main(String[] args) {
NodeStackDemo<Integer> stackDemo = new NodeStackDemo();
stackDemo.push(1);
stackDemo.push(3);
stackDemo.push(5);
System.out.println("栈顶元素：" + stackDemo.top());
System.out.println("栈大小：" + stackDemo.size());
stackDemo.pop();
System.out.println("栈第一次弹出元素");
stackDemo.pop();
System.out.println("栈第二次弹出元素");
stackDemo.pop();
System.out.println("栈第二次弹出元素");
stackDemo.pop();
}
}
class MyNode<T> {
T data;
MyNode<T> next;
}运行结果
两种方法的对比
采用数组实现栈的优点：一个元素值占用一个存储空间；它的缺点：如果初始化申请的存储空间太大，会造成空间的浪费，如果申请的存储空间太小，后期会经常需要扩充存储空间，扩充存储空间是个费时的操作，这样会造成性能的下降。采用链表实现栈的优点：使用灵活方便，只有在需要的时候才会申请空间。它的缺点：除了要存储元素外，还需要额外的存储空间存储指针信息。
算法性能分析：这两种方法压栈与弹栈的时间复杂度都为O（1）。