Java数据结构与算法(2):栈
发布时间:2020-12-15 07:31:30 所属栏目:Java 来源:网络整理
导读:栈是一种线性表,特点在于它只能在一个位置上进行插入和删除,该位置是表的末端,叫做栈的顶(top)。因此栈是 后进先出的(FIFO) 。栈的基本操作有push、peek、pop。 栈的示意图 进栈和出栈都只能在一个位置进行操作。 基于数组的栈实现 /** * 基于数组的栈实
栈是一种线性表,特点在于它只能在一个位置上进行插入和删除,该位置是表的末端,叫做栈的顶(top)。因此栈是后进先出的(FIFO)。栈的基本操作有push、peek、pop。 栈的示意图
基于数组的栈实现/** * 基于数组的栈实现 */ public class MyArrayStack<T> { // 栈顶 private int top = -1; // 保存元素的数组 private T[] items; // 默认栈大小 private int DEFAULT_CAPACITY = 10; public MyArrayStack() { items = (T[]) new Object[DEFAULT_CAPACITY]; } public MyArrayStack(int size) { if (size <= 0) { throw new IllegalArgumentException(); } items = (T[]) new Object[size]; } public boolean isEmpty() { return top == -1; } public void push(T x) { if (top == items.length) { throw new FullStackException(); } items[++top] = x; } public T peek() { if (isEmpty()) { throw new EmptyStackException(); } return items[top]; } public T pop() { if (isEmpty()) { throw new EmptyStackException(); } return items[top--]; } } 基于链表的栈实现package org.zhugc.ds; /** * 基于链表的栈实现 * * @param <T> */ public class MyLinkedStack<T> { private Node<T> top; private int size; private class Node<T> { private T data; private Node<T> next; public Node(T data) { this.data = data; } } public boolean isEmpty() { return top == null; } public void push(T x) { Node<T> newNode = new Node<>(x); newNode.next = top; top = newNode; size++; } public T pop() { Node<T> delNode = top; top = top.next; size--; return delNode.data; } public int size() { return size; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |