快捷導(dǎo)航

java數(shù)據(jù)結(jié)構(gòu)基礎(chǔ):循環(huán)鏈表和棧

更新時(shí)間：2021年08月01日 11:31:15 作者：去吧貓頭夜鷹

這篇文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)之循環(huán)鏈表、棧的實(shí)現(xiàn)方法,結(jié)合實(shí)例形式分析了Java數(shù)據(jù)結(jié)構(gòu)中循環(huán)鏈表、棧、的功能、定義及使用方法,需要的朋友可以參考下

循環(huán)鏈表：

與單鏈表的最后一個(gè)節(jié)點(diǎn)的指針域?yàn)閚ull不同，循環(huán)鏈表的最后一個(gè)節(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)

實(shí)現(xiàn)思路：

初始化時(shí)將頭結(jié)點(diǎn)指向自身，添加節(jié)點(diǎn)到鏈表末尾時(shí)，將新節(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)

在遍歷鏈表時(shí)，判斷是否遍歷到鏈表末尾，需要判斷當(dāng)前指針的下一個(gè)節(jié)點(diǎn)是否為頭結(jié)點(diǎn)

代碼實(shí)現(xiàn)：

節(jié)點(diǎn)類CircleNode：

public class CircleNode {
	public int data;
	public CircleNode next;
	public CircleNode(int data) {
		this.data = data;
	}
	@Override
	public String toString() {
		return "CircleNode{" + "data=" + data + '}';
	}
}

循環(huán)鏈表類CircleLinkedList：

public class CircleLinkedList {
	public CircleNode head = new CircleNode(0);
	public CircleLinkedList() {
		head.next = head;
	}
	//添加節(jié)點(diǎn)
	public void add(CircleNode circleNode) {
		CircleNode temp = head;
		//找到鏈表最后一個(gè)節(jié)點(diǎn)
		while (temp.next != head) {
			temp = temp.next;
		}
		temp.next = circleNode;
		circleNode.next = head;
	}
	//刪除節(jié)點(diǎn)
	public void delete(int data) {
		CircleNode temp = head;
		boolean flag = false;    //標(biāo)志是否找到待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
		while (true) {
			if (temp.next == head) {
				//已經(jīng)遍歷到鏈表最后了
				break;
			} else if (temp.next.data == data) {
				//找到待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if (flag) {
			temp.next = temp.next.next;
		} else {
			System.out.println("要?jiǎng)h除的節(jié)點(diǎn)不存在");
		}
	}
	//輸出鏈表
	public void show() {
		//判斷鏈表是否為空
		if (head.next == head) {
			System.out.println("鏈表為空");
			return;
		}
		CircleNode temp = head.next;
		while (temp != head) {
			System.out.println(temp);
			temp = temp.next;
		}
	}
}

棧：

棧是一種受限制的線性表，只允許在表的一端進(jìn)行插入，另一端進(jìn)行刪除，具有“先入先出”的特性

棧是一種受限制的線性表

只允許在表的一端進(jìn)行插入和刪除，這一端稱作棧頂

具有先進(jìn)后出的特性

實(shí)現(xiàn)思路：

棧底層數(shù)據(jù)采用數(shù)組存儲

設(shè)置棧頂指針top指向棧頂?shù)脑?/p>

判滿：top = maxSize - 1

判空：top = -1

入棧：棧頂指針上移后寫入數(shù)據(jù)

出棧：用臨時(shí)變量保存棧頂數(shù)據(jù)，棧頂指針下移，返回棧頂數(shù)據(jù)

代碼實(shí)現(xiàn)：

public class ArrayStack {
	private int maxSize;    //數(shù)組的最大容量
	private int[] stack;    //存放數(shù)據(jù)
	private int top = -1;    //棧頂指針
	public ArrayStack(int maxSize) {
		this.maxSize = maxSize;
		stack = new int[this.maxSize];
	}
	//判斷棧是否滿
	public boolean isFull() {
		return top == maxSize - 1;
	}
	//判斷棧是否空
	public boolean isEmpty() {
		return top == -1;
	}
	//入棧
	public void push(int value) {
		//判斷是否棧滿
		if (isFull()) {
			System.out.println("棧滿");
			return;
		}
		top++;
		stack[top] = value;
	}
	//出棧
	public int pop() {
		if (isEmpty()) {
			throw new RuntimeException("棧空");
		}
		int value = stack[top];
		top--;
		return value;
	}
	//輸出棧，從棧頂開始顯示
	public void show() {
		if (isEmpty()) {
			System.out.println("?？?);
			return;
		}
		for (int i = top; i >= 0; i--) {
			System.out.printf("stack[%d] = %d\n", i, stack[i]);
		}
	}
}