城厢区建设局网站,discuzq,泰州做网站价格,松江新城建设发展有限公司网站文章目录 前言1. 栈的基础概要1.1 栈的特征1.2 栈的操作1.3 Java中的栈 2. 栈的实现#xff08;手写栈#xff09;2.1 基于数组实现2.2 基于链表实现2.3 基于LinkedList实现 总结 前言 提示#xff1a;我自己一个人的感觉很好 我并不想要拥有你 除非你比我的独处更加宜人 --… 文章目录 前言1. 栈的基础概要1.1 栈的特征1.2 栈的操作1.3 Java中的栈 2. 栈的实现手写栈2.1 基于数组实现2.2 基于链表实现2.3 基于LinkedList实现 总结 前言 提示我自己一个人的感觉很好 我并不想要拥有你 除非你比我的独处更加宜人 --瓦尔桑·希雷
1. 栈的基础概要
1.1 栈的特征
栈和队列是比较特殊的线性表为什么特殊呢又称为访问受限的线性表。栈常用于表达式、符号等运算的基础也是递归的底层实现。理论上递归可以做的题目栈都是可以做的只是有些问题用栈相对复杂一些。
栈的底层实现是我们常见的链表或者顺序表栈与线性表的最大区别在于数据的存取操作被限制了其插入和删除操作只允许在线性表的一端进行。一般而言我们把允许操作的一端称为栈顶top不可以操作的一端称为栈底bottom同时插入元素的操作称为入栈push删除元素的操作称为出栈pop。若栈中没有任何元素则称为空栈栈的结构如图所示
1.2 栈的操作
栈的常见操作主要有
push(E):增加一个元素Epop():弹出元素Epeek():显示栈顶元素但是不出栈empty():判断栈是否为空
我们在设计自己的栈的时候不管是使用数组还是链表都需要实现以上的几个方法。
一道经典的题目入栈顺序为1234所有可能的出栈序列是什么
这个题是什么意思呢举个例子我们可以先让12入栈然后21出栈再让34入栈然后一次出栈就可以得到2143的序列。
4个元素的全排列有4 24栈要求符合先进后出根据这个条件我们可以排除
1234 √ 1243 √ 1324 √ 1342 √ 1423 × 1432 √
2134 √ 2143 √ 2314 √ 2341 √ 2413 × 2431 √
3124 × 3142 × 3214 √ 3241 √ 3412 × 3421 √
4123 × 4132 × 4213 × 4231 × 4312× 4321 √
14中可能10中不可能。
1.3 Java中的栈
Java中的栈uitl中就提供了栈Stack类使用起来也不复杂我们看一下例子 import java.util.Stack;public class MainTest {public static void main(String[] args) {StackInteger stack new Stack();// 入栈stack.push(1);stack.push(2);stack.push(3);stack.push(4);// 出栈stack.pop();while (!stack.isEmpty()) {// 展示但是不删除System.out.println(stack.peek());// 删除System.out.println(stack.pop());}}
}
2. 栈的实现手写栈
我们在学习栈的过程中需要了解一些问题top栈顶指针的指向有的地方指向栈顶再往上一个空位有的地方指向栈顶元素。我们确定好设计就行根据题目调整有时候也可以直接问面试官 top指向哪里这里采用指向栈顶空位置。
如果我们自己要实现栈可以使用数组链表Java中提供了LinkedList三种基本实现方式我们都可以看一下。
2.1 基于数组实现
采用顺序表实现的栈内部以数组为基础实现对元素的存取操作。在应用中还要之一每次入栈之前要确保栈的容量是否足够不够需要考虑扩容的问题。
我们画一下入栈的过程 出栈的过程 出栈先将栈顶元素取出然后top–
展示代码
import java.util.Arrays;
class MystackT {private Object[] stack;// 栈顶指针private int top;
public Mystack() {// 初始长度为10stack new Object[10];}
/*** 判断是否为空** return*/public boolean isEmpty() {return top 0;}
/*** 返回栈顶元素但是不删除** return*/public T peek() {T t null;if (top 0) {t (T) stack[top - 1];}return t;}
/*** 入栈操作** param t*/public void push(T t) {expandCapacity(top 1);stack[top] t;top;}
public T pop() {T t peek();if (!isEmpty()) {// 清除元素stack[top - 1] null;top--;}return t;}
/*** 确保容量** param size*/public void expandCapacity(int size) {int len stack.length;if (size len) {size size * 3 / 2 1;stack Arrays.copyOf(stack, size);}}
public static void main(String[] args) {MystackString stack new Mystack();System.out.println(stack.peek());// nullSystem.out.println(stack.isEmpty());// truestack.push(java);stack.push(is);stack.push(beautiful);stack.push(language);System.out.println(stack.pop());// languageSystem.out.println(stack.isEmpty());// falseSystem.out.println(stack.peek()); // beautiful}
}2.2 基于链表实现
链表用来实现栈也很简单头插法在头部操作链表就可以了。 我们先画个图 在链表的那一章我们介绍过没有虚拟节点时对链表头部元素进行插入和删除的操作不记得的可以回顾一下算法通过村第二关-链表青铜笔记_师晓峰的博客-CSDN博客这里基于链表实现栈的操作时完全一样的。
代码实现
class ListStackT {// 构造节点class NodeT {public T t;private Node next;}public NodeT head;ListStack() {head null;}/*** 入栈操作* param t*/public void push(T t) {if (t null) {throw new IllegalStateException(参数不能为空);}// 头节点为空if (head null) {head new NodeT();head.t t;head.next null;}else {NodeT temp head;head new NodeT();head.t t;head.next temp;}}/*** 出栈操作* return*/public T pop(){if (head null) {return null;}T t head.t;head head.next;return t;}public T peek(){if (head null) {return null;}return head.t;}/*** 判断是否为空** return*/public boolean isEmpty() {return head null;}public static void main(String[] args) {ListStack stack new ListStack();System.out.println(stack.isEmpty());// truestack.push(Java);stack.push(is);stack.push(beautiful);System.out.println(stack.peek());// beautifulSystem.out.println(stack.pop());// beautifulSystem.out.println(stack.isEmpty());// false}
}2.3 基于LinkedList实现
这里就很简单了直接上代码就行
import java.util.LinkedList;/*** 基于Java的LinkedList来实现栈* param T*/
public class LinkedListStackT {private LinkedListT ll;LinkedListStack(){ll new LinkedListT();}/*** 入栈操作* param t*/public void push( T t){ll.addFirst(t);}/*** 出栈但是不删除* return*/public T peek(){T t null;if (!ll.isEmpty()){t ll.peek();}return t;}public T pop(){return ll.removeFirst();}public boolean isEmpty(){return ll.isEmpty();}public static void main(String[] args) {LinkedListStackString stack new LinkedListStack();System.out.println(stack.isEmpty());//trueSystem.out.println(stack.peek());//nullstack.push(java);stack.push(is);stack.push(beautiful);System.out.println(stack.peek());//beautifulSystem.out.println(stack.pop());//beautifulSystem.out.println(stack.isEmpty());//false}
} 总结
提示记住栈的特性先进后出
