java數據結構基礎:循環鏈表和棧

Posted on by

循環鏈表：

與單鏈表的最後一個節點的指針域為null不同，循環鏈表的最後一個節點的指針指向頭結點

實現思路：

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

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

代碼實現：

節點類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 + '}';
	}
}

循環鏈表類CircleLinkedList：

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

棧：

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

棧是一種受限制的線性表

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

具有先進後出的特性

實現思路：

棧底層數據采用數組存儲

設置棧頂指針top指向棧頂的元素

判滿：top = maxSize – 1

判空：top = -1

入棧：棧頂指針上移後寫入數據

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

代碼實現：

public class ArrayStack {
	private int maxSize;    //數組的最大容量
	private int[] stack;    //存放數據
	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]);
		}
	}
}

總結

本篇文章就到這裡瞭，希望能給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容！

推薦閱讀：