当前位置：首页 > news >正文

算法通关村第四关|青铜|自己实现栈

news 2025/7/20 20:50:54

1.自己实现栈——基于数组

top 有的地方指向栈顶元素，有的地方指向栈顶再往上的一个空单位，根据题目要求设计。

*这里将 top 设置为栈顶再往上的一个空单位。

import java.util.Arrays;
class Mystack<T> {private Object[]  stack;// 指向栈顶上的空位private int top = 0;Mystack() {stack = new Object[8];}// 判断是否为空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) {// 栈基于数组实现，当数组填满时需要扩容// top+1匹配stack.length，代表数组的最后一位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;// size大于len，则本次push已经没有位置了，需要扩容if (size > len) {// 扩容 50%size = size * 3 / 2 + 1;stack = Arrays.copyOf(stack, size);}}
}

2.自己实现栈——基于链表

class ListStack<T> {class Node<T> {public T t;public Node next;}// 基于链表实现栈，需要一直对头结点进行操作public Node<T> head;// 构造函数，初始化头指针ListStack() {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;}T t = head.t;return t;}// 判空public boolean isEmpty() {if (head == null) {return true;} else {return false;}}
}