10.线性表之栈的概念及Java实现栈(顺序栈和链式栈)
2023-09-11 14:18:28 时间
1.栈的概念
后进先出法,简称 LIFO,last in first out ;
栈是一种只允许在一端进行插入或删除的线性表。
1、栈的操作端通常被称为栈顶,另一端被称为栈底。
2、栈的插入操作称为进栈(压栈|push);栈删除操作称为出栈(弹栈|pop)。
特点
栈就像一个杯子,我们只能从杯口放和取,所以栈中的元素是“先进后出”的特点。
存储结构
顺序存储的栈称为顺序栈;链式存储的栈称为链式栈。
实际上,栈就可以用数组来实现,也可以用链表来实现。用数组实现的叫做顺序栈,用链表实现的叫做链式栈。
2.java实现
我们可以围绕栈的4个元素来实现栈:
2个状态:是否栈空;是否栈满。
2个操作:压栈push;弹栈pop。
2.1顺序栈的实现
/**
* 数组实现栈
*/
class Mystack1<T> {
//实现栈的数组
private Object[] stack;
//数组大小
private int size;
//初始化数组
Mystack1() {
stack = new Object[10];//初始容量为10
}
//判断是否为空
public boolean isEmpty() {
return size == 0;
}
//返回栈顶元素
public T peek() {
T t = null;
if (size > 0)
t = (T) stack[size - 1];
return t;
}
//入栈
public void push(T t) {
expandCapacity(size + 1);
stack[size] = t;
size++;
}
//出栈
public T pop() {
//移到栈顶,准备出栈
T t = peek();
if (size > 0) {
stack[size - 1] = null;
size--;
}
return t;
}
//如果栈满了就需要扩大容量
public void expandCapacity(int size) {
int len = stack.length;
if (size > len) {
size = size * 2;//每次扩大一倍
//Java里面数组扩大的方法Arrays.copyOf()
stack = Arrays.copyOf(stack, size);
}
}
}
public class ArrayStack {
public static void main(String[] args) {
Mystack1<String> stack = new Mystack1<>();
System.out.println(stack.peek());
System.out.println(stack.isEmpty());
stack.push("java");
stack.push("is");
stack.push("beautiful");
stack.push("language");
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
System.out.println(stack.peek());
}
}
2.2 链式栈的实现
使用链表来实现栈,push进的数据添加至链表的头结点,pop数据时取的也是链表的头结点,这样就实现了栈的后进先出。代码如下:
package LinearTable.Stack;
/**
* 链表实现栈
*
* @param <T>
*/
class Mystack2<T> {
//定义链表
class Node<T> {
//定义数据类型泛型T
private T t;
//定义指针
private Node next;
}
//定义头节点
private Node<T> head;
//构造函数初始化头指针
Mystack2() {
head = null;
}
//入栈
public void push(T t) {
if (t == null) {
throw new NullPointerException("参数不能为空");
}
if (head == null) {
//创造的新节点
head = new Node<T>();
head.t = t;
//next指针指向下一个位置
head.next = null;
} else {
//头节点指向的位置
Node<T> temp = head;
//创建新节点
head = new Node<>();
head.t = t;
head.next = temp;
}
}
//出栈
public T pop() {
T t = head.t;
head = head.next;
return t;
}
//栈顶元素
public T peek() {
T t = head.t;
return t;
}
//栈空
public boolean isEmpty() {
if (head == null)
return true;
else
return false;
}
}
public class LinkStack {
public static void main(String[] args) {
Mystack2 stack = new Mystack2();
System.out.println(stack.isEmpty());
stack.push("Java");
stack.push("is");
stack.push("beautiful");
System.out.println(stack.peek());
System.out.println(stack.peek());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
}
}
相关文章
- Java异常--其他概念—throw、throws、Exception、RuntimeException、断言
- hadoop中datanode无法启动,报Caused by: java.net.NoRouteToHostException: No route to host
- JAVA学习(五):Java面向对象编程基础
- Java实现 LeetCode 509 斐波那契数
- Java实现 LeetCode 113 路径总和 II
- Java 实现 蓝桥杯 生兔子问题
- Java GUI 键盘事件
- Java实现 蓝桥杯 算法提高 判断名次
- java.sql.SQLException: null, message from server: “Host ‘xxx’ is not allowed to connect
- Java bean 是个什么概念?
- Java主要版本平台
- [Spring学习笔记 4 ] AOP 概念原理以及java动态代理
- 【JAVA】java中的length和length()
- 【JAVA】 01-Java基础知识
- 【Java】java使用反射访问对象方法和成员变量
- 在Java中可以使用自定义的java.net.InetAddress实现来解决虚拟hosts的问题
- java DefaultMutableTreeNode 树形结构 目录 1. Tree的概念1 1.1. treeNode接口,mutabletreenode接口1 1.2. 10-4:以T
- Atitit 研发体系 codelib 代码库的建设 目录 1. 概念与组成2 1.1. Java代码2 1.2. Js代码2 1.3. H5 代码 js+css+htm+txt2 1.4.
- Java递归基础案例-汉诺塔
- 【java】Java连接mysql数据库及mysql驱动jar包下载和使用
- 【java】Java 包(package)
- Java main方法_解释Java中的main方法,及其作用_一个java文件中可包含多个main方法
- java-信息安全(十二)-数字证书、CA证书【Java证书体系实现】
- JAVA语言之Java 中不同的并行实现的性能比较
- 【JAVA面试必会】JMM高并发详解(java内存模型、JMM三大特征、volatile关键字 )
- 【java】Java 继承
- JAVA开发讲义(二)-Java程序设计之数据之谜三
- JAVA开发讲义(一)-Java的自白