算法刷题笔记-day4（数据结构基础）
2026/4/9大约 3 分钟
算法刷题笔记-day4（数据结构基础）
用数组实现基本的队列和栈及其常用方法
/**
* 用数组结构实现大小固定的队列和栈
*/
public class dataStructure {
/**
* 用数组实现了栈结构；
*/
public static class ArrayStack {
private Integer[] arr;
//用size记录栈内元素个数的情况
private Integer size;
public ArrayStack(int initSize) {
if (initSize < 0) {
throw new IllegalArgumentException("栈已满");
}
arr = new Integer[initSize];
size = 0;
}
/**
* 返回栈顶元素
*
* @return
*/
public Integer peak() {
if (size == 0) {
return null;
}
return arr[size - 1];
}
/**
* 向栈中添加元素
*
* @param obj
*/
public void push(Integer obj) {
if (size == arr.length) {
throw new ArrayIndexOutOfBoundsException("栈已满");
}
arr[size++] = obj;
}
/**
* 弹出栈顶元素
*
* @return
*/
public Integer pop() {
if (size == 0) {
throw new ArrayIndexOutOfBoundsException("栈已空");
}
return arr[--size];
}
}
/**
*
*/
public static class ArrayQueue {
private Integer[] arr;
//用size来记录队列内元素个数
private Integer size;
//first记录队列头的位置
private Integer first;
//last是遍历队列的指针
private Integer last;
public ArrayQueue(int initSize) {
if (initSize < 0) {
throw new IllegalArgumentException("队列长度小于0");
}
arr = new Integer[initSize];
size = 0;
first = 0;
last = 0;
}
/**
* 返回对列头元素
* @return
*/
public Integer peek() {
if (size == 0) {
return null;
}
return arr[first];
}
/**
* 元素入队列
* @param obj
*/
public void push(int obj) {
if (size == arr.length) {
throw new ArrayIndexOutOfBoundsException("对列已满");
}
size++;
arr[last]=obj;
last = last==arr.length ? 0 : last+1;
}
/**
* 队列头元素出队列
* @return
*/
public Integer poll(){
if (size==0){
throw new ArrayIndexOutOfBoundsException("队列已空");
}
size--;
int temp = first;
first = first==arr.length-1?0:first+1;
return arr[temp];
}
}
public static void main(String[] args) {
ArrayStack arrayStack = new ArrayStack(5);
arrayStack.push(5);
arrayStack.push(4);
arrayStack.push(3);
System.out.println(arrayStack.pop());
}
}树的遍历(用栈实现的非递归版)
import java.util.Stack;
public class PreInPosTraversal {
static class Node {
public int value;
public Node left;
public Node right;
public Node(int value) {
this.value = value;
}
}
/**
* 用栈实现的先序遍历
* <p>
* 先将头节点入栈，弹出栈顶，
* 再将头节点的左孩子入栈，
* 再将右孩子入栈，
* 再将左孩子看做新的头节点，
* 重复此过程
*
* @param head
*/
public static void preOrderUnRecur(Node head) {
System.out.print("先序遍历序列为：");
Stack<Node> preOrderStack = new Stack<Node>();
preOrderStack.push(head);
while (!preOrderStack.isEmpty()) {
head = preOrderStack.pop();
System.out.print(head.value + " ");
if (head.right != null) {
preOrderStack.push(head.right);
}
if (head.left != null) {
preOrderStack.push(head.left);
}
}
System.out.println();
}
/**
* 中序遍历栈结构
*
* 先将头节点入栈，
* 再将它的左节点枝都入栈，
* 然后弹出栈顶，
* 再将栈顶的右节点枝入栈，
* 再弹出栈顶，
* 重复此过程
*
* @param head
*/
public static void inOrderUnRecur(Node head) {
System.out.print("中序遍历序列为");
if (head != null) {
Stack<Node> inOrderStack = new Stack<Node>();
while (!inOrderStack.isEmpty() || head != null) {
if (head != null) {
inOrderStack.push(head);
head = head.left;
} else {
head = inOrderStack.pop();
System.out.print(head.value + " ");
head = head.right;
}
}
}
System.out.println();
}
/**
* 先将头节点入栈，
* 定义一个指针指向栈顶元素，
* 将栈顶元素的左子枝入栈，
* 指针随时指向栈顶元素，
* 指到叶子节点时，弹出叶子节点
* 将栈顶元素的右枝入栈，
* 指到叶子节点时，弹出叶子节点
* @param head
*/
public static void posOrderUnRecur(Node head) {
System.out.println("后序遍历序列为：");
if (head != null) {
Stack<Node> posOrderStack = new Stack<>();
posOrderStack.push(head);
Node temp = null;
while (!posOrderStack.isEmpty()) {
temp = posOrderStack.peek();
if (temp.left != null && head != temp.left && head != temp.right) {
posOrderStack.push(temp.left);
} else if (temp.right != null && head != temp.right) {
posOrderStack.push(temp.right);
}else {
System.out.print(posOrderStack.pop().value+" ");
head=temp;
}
}
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(5);
head.left = new Node(3);
head.right = new Node(8);
head.left.left = new Node(2);
head.left.right = new Node(4);
head.left.left.left = new Node(1);
head.right.left = new Node(7);
head.right.left.left = new Node(6);
head.right.right = new Node(10);
head.right.right.left = new Node(9);
head.right.right.right = new Node(11);
posOrderUnRecur(head);
}
}