本文共 1070 字，大约阅读时间需要 3 分钟。

数据结构和算法系列共八篇

1.什么是栈

栈其实特殊的线性表。被限制了只能头操作

表的一端进行插入和删除操作，不允许在其他任何位置进行插入、查找、删除等操作。

java的栈内存就是很好的例子

特点：

• 先进后出 FILO (First In Last Out)，后进先出 LIFO
• 只对栈顶操作。不能操作其他地方

常见操作

• size: 大小
• isEmpty: 是否为空
• push : 入栈
• pop : 弹栈
• peek： 取栈顶元素

2.存储结构

• 顺序栈结构
• 链栈结构

2-1.顺序栈结构

顺序栈是使用顺序存储结构实现的堆栈，即利用一组地址连续的存储单元依次存放堆栈中的数据元素。

栈只对栈顶(顺序表一端)操作，所以入栈、出栈等时间复杂度为Ο(1)。

2-2.链栈结构

当采用单链表存储线性表后，根据单链表的操作特性选择单链表的头部作为栈顶。时间复杂度也为Ο(1)。

• 使用带头结点的单链表时，结点的插入和删除都在头结点之后进行；
• 使用不带头结点的单链表时，结点的插入和删除都在链表的首结点上进行。

3.演示

我们直接使用java提供的类来演示

• Stack类：已经过时了
• Deque：双端队列（栈操作）

java种使用Deque来操作栈，因为栈是双端队列的一种特例(只操作一端，即栈了)

Deque是接口，使用了LinkedList来实列化对象。因为LinkedList实现了Deque

``java

public static void main(String[] args) {    Deque
   
     stack = new LinkedList
    
     ();    stack.push("a");    stack.push("b");    stack.push("c");    stack.push("d");    while (!stack.isEmpty()) {        System.out.print(stack.pop());    }}
    
   

}

结果：dcba

4.进入一步深造

下一步如何再深造呢?

去看java的Dque的实现类ArrayDeque、ListList、LinkedBlockingDeque等源码

5.推荐

能读到文章最后，首先得谢谢您对本文的肯定，你的肯定是对博主最大的鼓励。

你觉本文有帮助，那就点个👍

转载地址：http://wkhws.baihongyu.com/