Java 實(shí)現(xiàn)棧的三種方式
更新時(shí)間：2020年12月04日 17:54:24 作者：Survivior_Y
這篇文章主要介紹了棧：LIFO（后進(jìn)先出），自己實(shí)現(xiàn)一個(gè)棧，要求這個(gè)棧具有push()、pop()（返回棧頂元素并出棧）、peek() （返回棧頂元素不出棧）、isEmpty()這些基本的方法,需要的朋友可以參考下
棧：LIFO（后進(jìn)先出），自己實(shí)現(xiàn)一個(gè)棧，要求這個(gè)棧具有push()、pop()（返回棧頂元素并出棧）、peek() （返回棧頂元素不出棧）、isEmpty()這些基本的方法。
一、采用數(shù)組實(shí)現(xiàn)棧
提示：每次入棧之前先判斷棧的容量是否夠用，如果不夠用就用Arrays.copyOf()進(jìn)行擴(kuò)容
import java.util.Arrays;
/**
* 數(shù)組實(shí)現(xiàn)棧
* @param <T>
*/
class Mystack1<T> {
//實(shí)現(xiàn)棧的數(shù)組
private Object[] stack;
//數(shù)組大小
private int size;
Mystack1() {
stack = new Object[10];//初始容量為10
}
//判斷是否為空
public boolean isEmpty() {
return size == 0;
}
//返回棧頂元素
public T peek() {
T t = null;
if (size > 0)
t = (T) stack[size - 1];
return t;
}
public void push(T t) {
expandCapacity(size + 1);
stack[size] = t;
size++;
}
//出棧
public T pop() {
T t = peek();
if (size > 0) {
stack[size - 1] = null;
size--;
}
return t;
}
//擴(kuò)大容量
public void expandCapacity(int size) {
int len = stack.length;
if (size > len) {
size = size * 3 / 2 + 1;//每次擴(kuò)大50%
stack = Arrays.copyOf(stack, size);
}
}
}
public class ArrayStack {
public static void main(String[] args) {
Mystack1<String> stack = new Mystack1<>();
System.out.println(stack.peek());
System.out.println(stack.isEmpty());
stack.push("java");
stack.push("is");
stack.push("beautiful");
stack.push("language");
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
System.out.println(stack.peek());
}
}
二、采用鏈表實(shí)現(xiàn)棧
/**
* 鏈表實(shí)現(xiàn)棧
*
* @param <T>
*/
class Mystack2<T> {
//定義鏈表
class Node<T> {
private T t;
private Node next;
}
private Node<T> head;
//構(gòu)造函數(shù)初始化頭指針
Mystack2() {
head = null;
}
//入棧
public void push(T t) {
if (t == null) {
throw new NullPointerException("參數(shù)不能為空");
}
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() {
T t = head.t;
head = head.next;
return t;
}
//棧頂元素
public T peek() {
T t = head.t;
return t;
}
//?？?
public boolean isEmpty() {
if (head == null)
return true;
else
return false;
}
}
public class LinkStack {
public static void main(String[] args) {
Mystack2 stack = new Mystack2();
System.out.println(stack.isEmpty());
stack.push("Java");
stack.push("is");
stack.push("beautiful");
System.out.println(stack.peek());
System.out.println(stack.peek());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
}
}
三、采用LinkedList實(shí)現(xiàn)棧
push-----addFirst()
pop-------removeFirst()
peek-----getFirst()
isEmpty-isEmpty()
import java.util.LinkedList;
/**
* LinkedList實(shí)現(xiàn)棧
*
* @param <T>
*/
class ListStack<T> {
private LinkedList<T> ll = new LinkedList<>();
//入棧
public void push(T t) {
ll.addFirst(t);
}
//出棧
public T pop() {
return ll.removeFirst();
}
//棧頂元素
public T peek() {
T t = null;
//直接取元素會(huì)報(bào)異常，需要先判斷是否為空
if (!ll.isEmpty())
t = ll.getFirst();
return t;
}
//?？?
public boolean isEmpty() {
return ll.isEmpty();
}
}
public class LinkedListStack {
public static void main(String[] args) {
ListStack<String> stack = new ListStack();
System.out.println(stack.isEmpty());
System.out.println(stack.peek());
stack.push("java");
stack.push("is");
stack.push("beautiful");
System.out.println(stack.peek());
System.out.println(stack.pop());
System.out.println(stack.isEmpty());
System.out.println(stack.peek());
}
}
接著分享java使用兩種方式實(shí)現(xiàn)簡(jiǎn)單棧
兩種棧的不同點(diǎn)
基于數(shù)組實(shí)現(xiàn)的棧需要指定初始容量，棧的大小是有限的（可以利用動(dòng)態(tài)擴(kuò)容改變其大?。阪湵韺?shí)現(xiàn)的棧則是沒(méi)有大小限制的。
基于數(shù)組實(shí)現(xiàn)棧
數(shù)組實(shí)現(xiàn)棧的主要方法就是標(biāo)識(shí)棧頂在數(shù)組中的位置，初始化時(shí)可以將棧頂指向?yàn)?1的虛擬位置，元素入棧則棧頂元素加1，出棧則棧頂元素減一，棧的元素容量為棧頂指針當(dāng)前位置加1，且不能超過(guò)底層數(shù)組的最大容量。
/**
* 以數(shù)組為底層實(shí)現(xiàn)棧
* @param <T>
*/
public class MyStackOfArray<T> {
private Object[] data;//底層數(shù)組
private int maxSize = 0;//棧存儲(chǔ)的最大元素個(gè)數(shù)
private int top = -1;//初始時(shí)棧頂指針指向-1
//默認(rèn)初始化容量為10的棧
public MyStackOfArray(){
this(10);
}
//初始化指定大小的棧
public MyStackOfArray(int initialSize){
if(initialSize >= 0){
this.maxSize = initialSize;
data = new Object[initialSize];
top = -1;
}else{
throw new RuntimeException("初始化容量不能小于0" + initialSize);
}
}
//入棧，棧頂指針先加一再填入數(shù)據(jù)
public boolean push(T element){
if(top == maxSize - 1){
throw new RuntimeException("當(dāng)前棧已滿，無(wú)法繼續(xù)添加元素");
}else{
data[++top] = element;
return true;
}
}
//查看棧頂元素
public T peek(){
if(top == -1)
throw new RuntimeException("棧已空");
return (T) data[top];
}
//出棧，先彈出元素再將棧頂指針減一
public T pop(){
if(top == -1)
throw new RuntimeException("棧已空");
return (T) data[top--];
}
//判斷當(dāng)前棧是否為空，只需判斷棧頂指針是否等于-1即可
public boolean isEmpty(){
return top == -1;
}
public int search(T element){
int i = top;
while (top != -1){
if(peek() != element)
top--;
else
break;
}
int result = top + 1;
top = i;
return top;
}
public static void main(String[] args) {
MyStackOfArray<Integer> myStackOfArray = new MyStackOfArray<>(10);
for(int i = 0; i < 10; i++){
myStackOfArray.push(i);
}
System.out.println("測(cè)試是否執(zhí)行");
for(int i = 0; i < 10; i++){
System.out.println(myStackOfArray.pop());
}
}
}
基于鏈表實(shí)現(xiàn)棧
基于鏈表實(shí)現(xiàn)棧只要注意控制棧頂指針的指向即可。
/**
* 鏈表方式實(shí)現(xiàn)棧
* @param <E>
*/
public class MyStack<E> {
/**
* 內(nèi)部節(jié)點(diǎn)類(lèi)
* @param <E>
*/
private class Node<E>{
E e;
Node<E> next;
public Node(){}
public Node(E e, Node<E> next){
this.e = e;
this.next = next;
}
}
private Node<E> top;//棧頂指針
private int size;//棧容量
public MyStack(){
top = null;
}
//入棧，將新節(jié)點(diǎn)的next指針指向當(dāng)前top指針，隨后將top指針指向新節(jié)點(diǎn)
public boolean push(E e){
top = new Node(e, top);
size++;
return true;
}
//判斷棧是否為空
public boolean isEmpty(){
return size == 0;
}
//返回棧頂節(jié)點(diǎn)
public Node<E> peek(){
if(isEmpty())
throw new RuntimeException("棧為空");
return top;
}
//出棧，先利用臨時(shí)節(jié)點(diǎn)保存要彈出的節(jié)點(diǎn)值，再將top指針指向它的下一個(gè)節(jié)點(diǎn)，并將彈出的節(jié)點(diǎn)的next指針賦空即可
public Node<E> pop(){
if(isEmpty())
throw new RuntimeException("棧為空");
Node<E> value = top;
top = top.next;
value.next = null;
size--;
return value;
}
//返回當(dāng)前棧的大小
public int length(){
return size;
}
public static void main(String[] args) {
MyStack<Integer> myStack = new MyStack<>();
for(int i = 0; i < 10; i++){
myStack.push(i);
}
for(int i = 0; i < 10; i++){
System.out.println(myStack.pop().e);
}
}
}
到此這篇關(guān)于Java 實(shí)現(xiàn)棧的三種方式的文章就介紹到這了,更多相關(guān)Java 實(shí)現(xiàn)棧內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
- 詳解java中jvm虛擬機(jī)棧的作用
- 深入JVM剖析Java的線程堆棧
- Java數(shù)據(jù)結(jié)構(gòu)之棧的線性結(jié)構(gòu)詳解
- java數(shù)據(jù)結(jié)構(gòu)基礎(chǔ):棧
- Java數(shù)組與堆棧相關(guān)知識(shí)總結(jié)
- java中利用棧實(shí)現(xiàn)字符串回文算法
- java括號(hào)匹配算法求解（用棧實(shí)現(xiàn)）
- JAVA jvm系列--java內(nèi)存區(qū)域
- JAVA JVM運(yùn)行時(shí)數(shù)據(jù)區(qū)詳解
- Java 內(nèi)存模型(JVM)
- Java的最大棧深度與JVM核心知識(shí)介紹
相關(guān)文章
TF-IDF理解及其Java實(shí)現(xiàn)代碼實(shí)例
這篇文章主要介紹了TF-IDF理解及其Java實(shí)現(xiàn)代碼實(shí)例，簡(jiǎn)單介紹了tfidf算法及其相應(yīng)公式，然后分享了Java實(shí)現(xiàn)代碼，具有一定參考價(jià)值，需要的朋友可以了解下。2017-11-11
SpringBoot如何實(shí)現(xiàn)word文檔轉(zhuǎn)pdf
這篇文章主要介紹了SpringBoot如何實(shí)現(xiàn)word文檔轉(zhuǎn)pdf，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-07-07
Java 數(shù)據(jù)庫(kù)時(shí)間返回前端顯示錯(cuò)誤(差8個(gè)小時(shí))的解決方法
本文主要介紹了Java 數(shù)據(jù)庫(kù)時(shí)間返回前端顯示錯(cuò)誤(差8個(gè)小時(shí))的解決方法,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-08-08
Java軟件生產(chǎn)監(jiān)控工具Btrace使用方法詳解
這篇文章主要介紹了Java軟件生產(chǎn)監(jiān)控工具Btrace使用方法詳解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-07-07
Springboot-Starter造輪子之自動(dòng)鎖組件lock-starter實(shí)現(xiàn)
這篇文章主要為大家介紹了Springboot-Starter造輪子之自動(dòng)鎖組件lock-starter實(shí)現(xiàn)詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-05-05
Java泛型在集合使用與自定義及繼承上的體現(xiàn)和通配符的使用
泛型又稱參數(shù)化類(lèi)型，是Jdk5.0 出現(xiàn)的新特性,解決數(shù)據(jù)類(lèi)型的安全性問(wèn)題，在類(lèi)聲明或?qū)嵗瘯r(shí)只要指定好需要的具體的類(lèi)型即可。Java泛型可以保證如果程序在編譯時(shí)沒(méi)有發(fā)出警告，運(yùn)行時(shí)就不會(huì)產(chǎn)生ClassCastException異常。同時(shí)，代碼更加簡(jiǎn)潔、健壯2021-09-09
什么是POM？這篇文章主要介紹了Maven的配置文件pom.xml，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-06-06
SpringBoot實(shí)現(xiàn)PPT格式文件上傳并在線預(yù)覽功能
本文介紹SpringBoot實(shí)現(xiàn)PPT格式文件上傳并在線預(yù)覽功能，通過(guò)上傳接口，可在C盤(pán)的tempfile目錄下找到上傳的文件，預(yù)覽時(shí)會(huì)在同級(jí)目錄下創(chuàng)建一個(gè)相同文件名后綴為pdf的文件，每次預(yù)覽會(huì)先查找文件是否存在，存在則直接預(yù)覽，不存在則會(huì)走上面的處理,需要的朋友可以參考下2022-02-02
這篇文章主要介紹了spring security自定義決策管理器的實(shí)現(xiàn)代碼，需要的朋友參考下吧2017-09-09
這篇文章主要介紹了spring拓展之如何定義自己的namespace方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-09-09