栈和队列是比较特殊的线性表,又称之为访问受限的线性表。栈是很多表达式、符号等运算的基础,也是递归的底层实现。理论上递归能做的题目栈都可以,只是有些问题用栈会非常复杂。 栈底层实现仍然是链表或者顺序表,栈与线性表的最大区别是数据的存取的操作被限制了,其插入和删除操作只允许在线性表的一端进行。一般而言,把允许操作的一端称为栈顶(Top),不可操作的一端称为栈底(Bottom),同时把插入元素的操作称为入栈(Push),删除元素的操作称为出栈(Pop)。若栈中没有任何元素,则称为空栈,栈的结构如下图:
栈的常用操作主要有:
我们在设计自己的栈的时候,不管用数组还是链表,都要实现上面几个方法。 如果想测试一下自己对栈是否理解,做一下这道题就够了:
入栈顺序为1234,所有可能的出栈序列是什么? 这个题是什么意思呢?比如说,我先让1和2入栈,然后 2 和1出栈,然后再让3 和4 入栈再依次出栈,这样就得到了序列2143。 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种不可能,如上所示。
package AlgorithmForth;
import java.util.Arrays;
/**
* 利用数组实现栈
*/
public class MyStackByArray<T> {
// 实现栈的数组
private Object[] stack;
// 栈顶元素位置;
private int top;
MyStackByArray(){
// 初始容量为10;
stack = new Object[10];
}
// 判断是否为空
public boolean isEmpty(){
return top == 0;
}
// 返回栈顶元素
public T peek(){
T t = null;
if(top > 0)
t = (T) stack[top -1 ];
return t;
}
public void push(T t){
expandCapacity(top+1);
stack[top] = t;
top++;
}
// 出栈
public T pop(){
T t =peek();
if(top > 0){
stack[top-1] = null;
top --;
}
return t;
}
// 扩大容量
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) {
MyStackByArray<String> stack = new MyStackByArray<>();
System.out.println(stack.isEmpty());
stack.push("Java");
stack.push("is");
stack.push("beautiful");
System.out.println(stack.peek());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
}
}
package AlgorithmForth;
/**
* 基于链表实现栈
*/
public class MyStackByLinkedList<T> {
class Node<T> {
public T t;
public Node next;
}
public Node<T> head;
MyStackByLinkedList(){
head = null;
}
// 入栈
public void push(T t){
if(t == null){
throw new NullPointerException("参数不能为空");
}
if(head == null) {
head = new Node<T>();
head.t = t;
head.next = null;
} else {
Node<T> temp = head;
head = new Node<>();
head.t = t;
head.next = temp;
}
}
// 出栈
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;
}
// 栈空
public boolean isEmpty(){
return head == null;
}
public static void main(String[] args) {
MyStackByLinkedList<String> stack = new MyStackByLinkedList();
System.out.println(stack.isEmpty());
stack.push("Java");
stack.push("is");
stack.push("beautiful");
System.out.println(stack.peek());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
}
}
近期在自学 Java 做项目,加入了一个编程学习圈子,里面有编程学习路线和原创的项目教程,感觉非常不错。还可以 1 对 1 和大厂嘉宾交流答疑,也希望能对大家有帮助,扫 ⬇️ 二维码即可加入。
也可以点击链接:我正在「编程导航」和朋友们讨论有趣的话题,你⼀起来吧?
也可以加我QQ(2837468248)咨询说明来意!