1. 什么是栈?
栈(stack)是限定仅在表尾进行插入和删除操作的线性表。
2. 栈的特点:
1.) 栈又称为后进先出(Last In First out)的线性表,栈元素具有线性关系,即前驱后继关系。
2.) 栈的特殊之处在于:它的栈底是固定的,只允许在栈顶进行插入和删除操作。
3. 栈的顺序存储结构(Java数组实现):
// 栈的数组实现, 底层使用数组:
public class ArrayStack<T> {
private Object[] arr; // 数组首元素作为栈底,因为它变化小
private int length;
// 数据初始化
public ArrayStack(){
arr = new Object[16];
length = 0;
}
// 元素入栈
public boolean push(T data) {
if (length >= arr.length) { // 判断是否需要进行数组扩容
resize();
}
arr[length++] = data;
return true;
}
// 元素出栈
@SuppressWarnings("unchecked")
public T pop() {
if (length == 0) {
return null;
}
return (T) arr[--length];
}
// 将数组中的数据置为null, 方便GC进行回收
public void clear() {
for (int i = 0; i < length; i++) {
arr[length] = null;
}
length = 0;
}
// 数组扩充容量
private void resize() {
Object[] temp = new Object[arr.length * 3 / 2 + 1];
for (int i = 0; i < length; i++) {
temp[i] = arr[i];
arr[i] = null;
}
arr = temp;
}
// 获取栈中元素个数
public int length() {
return length;
}
// 判断数组是否为空
public boolean isEmpty() {
return length == 0;
}
// 打印栈中元素
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < length; i++) {
sb.append(arr[i].toString());
if (i != length - 1) {
sb.append(", ");
}
}
return sb.toString();
}
public static void main(String[] args) {
ArrayStack<Integer> stack = new ArrayStack<Integer>();
long start = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
stack.push(i); // 入栈
}
long temp = System.currentTimeMillis();
System.out.println("push time: " + (temp - start));
while (stack.pop() != null){
; // 出栈
}
System.out.println("pop time: " + (System.currentTimeMillis() - temp));
}
}
运行时间:
push time: 257ms
pop time: 5ms
4. 栈的链式存储结构(Java链表实现):
// 结点元素
public class Node<T> {
private Node<T> prev; // 记住当前结点的前一结点
private T data; // 数据域
public Node() {
}
public Node(T data, Node<T> prev) {
this.data = data;
this.prev = prev;
}
public Node<T> getPrev() {
return prev;
}
public void setPrev(Node<T> prev) {
this.prev = prev;
}
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
}
// 栈的链表实现, 底层使用单链表:
public class LinkedStack<T> {
private Node<T> top; // 栈顶指针(链表尾结点)
private int size; // 栈的长度
// 数据初始化
public LinkedStack() {
top = null;
size = 0;
}
// 结点入栈
public boolean push(T data) {
Node<T> newNode = new Node<T>(data,top); // 将top设置为新节点的前驱结点
top = newNode; // 将新结点设置为栈顶指针
size++;
return true;
}
// 结点出栈
public T pop() {
if (top != null) {
Node<T> tempNode = top;
top = top.getPrev(); // 将栈顶指针的前驱结点设置为栈顶指针
size--;
return tempNode.getData();
}
return null;
}
// 判断栈是否为空
public boolean isEmpty() {
return size == 0;
}
// 获取栈的长度
public int length() {
return size;
}
// 打印栈中元素
public String toString() {
Node<T> node = top;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < size; i++) {
sb.append(node.getData().toString());
if (i != size - 1) {
sb.append(", ");
}
node = node.getPrev();
}
return sb.reverse().toString();
}
public static void main(String[] args) {
LinkedStack<Integer> stack = new LinkedStack<Integer>();
long start = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
stack.push(i); // 入栈
}
long temp = System.currentTimeMillis();
System.out.println("push time: " + (temp - start));
while (stack.pop() != null){
; // 出栈
}
System.out.println("pop time: " + (System.currentTimeMillis() - temp));
}
}
运行时间:
push time: 986ms
pop time: 15ms
5. 两种实现方式比较:通过入栈和出栈时间比较可以看出,数组实现在性能上还是有明显优势的,这是因为数组实现的栈在增加和删除元素时并不需要移动大量的元素,只是在扩大数组容量时,需要进行拷贝。然而链表实现的栈在入栈时需要将数据包装成Node,出栈时需要从Node中取出数据,同时还要维护栈顶指针和前驱指针。
6. JDK API中的栈:
1.) java.util.Stack: 一个普通的顺序栈,底层基于数组实现。这个类是线程安全的。
2.) java.util.LinkedList: 一个双向链表,线程不安全,可以当做栈来使用。在多线程环境下可以使用Collections类的工具方法将其改造成线程安全类。
3.) 两个类都提供了push(),pop(),peek()等方法。
分享到:
相关推荐
数据结构 线性表 栈和队列 串 数和二叉树 图 查找 内部排序
只供博主个人学习
特别提醒:本文件为《大话数据分析:Tableau数据可视化实战》的数据集,并不是PDF书籍。
基于《大话数据结构》进行数据结构的学习
Android之大话设计模式——:抽象工厂模式借鉴.pdf
大话数据结构 .pptx
大话Oracle RAC:集群、高可用性、备份与恢复(带目录清晰中文完整版)
数据结构与算法问题 讲解生动 数据结构不在
大话Oracle RAC:集群、高可用性、备份与恢复。 此书被认为不可多得的好资料之一:大话Oracle RAC(PDF经典),看完之后深有感触,发出来共享一下。
博主是第一次在CSDN上发动态的小白,由于大话数据结构这本书是用C实现的,对于Java才学到初级的我决定在后面学习的时候尽量用Java实现书中的例子,希望对这个事情感兴趣的同学一起加入,大家可以一起学习和探讨。...
Android之大话设计模式——:抽象工厂模式参考.pdf
《大话数据结构》——C语言简单实现单链表结构及相关一些操作
初中语文文摘历史“大话王”郭台铭:被夏普狠狠摔了个大跟
查找算法,平衡二叉树,大话数据结构里面的。
《大话数据结构》———C语言简单实现KMP模式匹配算法
大话Oracle.RAC:集群、高可用性、备份与恢复(第2版)
大话存储2:存储系统架构与底层原理极限剖析》内容简介:网络存储是一个涉及计算机硬件以及网络协议/技术、操作系统以及专业软件等各方面综合知识的领域。目前国内阐述网络存储的书籍少之又少,大部分是国外作品,对...
数据结构
数据结构.mdaaa