快捷導航

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

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

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

循環(huán)鏈表：

與單鏈表的最后一個節(jié)點的指針域為null不同，循環(huán)鏈表的最后一個節(jié)點的指針指向頭結(jié)點

實現(xiàn)思路：

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

在遍歷鏈表時，判斷是否遍歷到鏈表末尾，需要判斷當前指針的下一個節(jié)點是否為頭結(jié)點

代碼實現(xiàn)：

節(jié)點類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é)點
	public void add(CircleNode circleNode) {
		CircleNode temp = head;
		//找到鏈表最后一個節(jié)點
		while (temp.next != head) {
			temp = temp.next;
		}
		temp.next = circleNode;
		circleNode.next = head;
	}
	//刪除節(jié)點
	public void delete(int data) {
		CircleNode temp = head;
		boolean flag = false;    //標志是否找到待刪除節(jié)點的前一個節(jié)點
		while (true) {
			if (temp.next == head) {
				//已經(jīng)遍歷到鏈表最后了
				break;
			} else if (temp.next.data == data) {
				//找到待刪除節(jié)點的前一個節(jié)點
				flag = true;
				break;
			}
			temp = temp.next;
		}
		if (flag) {
			temp.next = temp.next.next;
		} else {
			System.out.println("要刪除的節(jié)點不存在");
		}
	}
	//輸出鏈表
	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;
		}
	}
}

棧：

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

棧是一種受限制的線性表

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

具有先進后出的特性

實現(xiàn)思路：

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

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

判滿：top = maxSize - 1

判空：top = -1

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

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

代碼實現(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]);
		}
	}
}