双向链表模拟栈的实现

实现思路： 1、双向链表模拟栈 2、写一个实体类用来表示链表节点 3、入栈操作：将新的数据添加到链表末尾 4、出栈操作：将最后一个链表最后一个节点内容返回，并将前一个结点的后一个节点置为null。（一开始打算用单链表实现栈，但是在出栈时发现无法找到最后一个节点的前一个结点，所以用双向链表实现栈） 5、显示栈：链表打印时是正序打印，此时模拟栈的打印，栈的特点是先进后出，所以链表需要逆序打印 实现思路 (1)写一个方法计算出链表的长度 (2)将链表的节点存放在一个数组中 (3)逆序打印数组 大致思路如上，接下来开始写代码 实体类

class Data {
          
   
	private int no;
	private Data next;
	public Data prev;

	public Data(int no) {
          
   
		super();
		this.no = no;
	}

	public int getNo() {
          
   
		return no;
	}

	public void setNo(int no) {
          
   
		this.no = no;
	}

	public Data getNext() {
          
   
		return next;
	}

	public void setNext(Data next) {
          
   
		this.next = next;
	}

	public Data getPrev() {
          
   
		return prev;
	}

	public void setPrev(Data prev) {
          
   
		this.prev = prev;
	}

	@Override
	public String toString() {
          
   
		return "Data [no=" + no + "]";
	}

}

双向链表实现栈

class LinkedStack {
          
   
	private Data head = new Data(0);
	private int maxsize;

	public LinkedStack(int maxsize) {
          
   
		this.maxsize = maxsize;
	}

	// 判断栈是否为满
	public boolean isFull() {
          
   
		return size() == maxsize;
	}

	// 判断栈是否为空
	public boolean isEmpty() {
          
   
		return head.getNext() == null;
	}

	// 链表显示时是正序打印，栈显示时对于链表而言是逆序打印，这里写一个计算链表长度的方法用于逆序显示链表的内容
	public int size() {
          
   
		if (head.getNext() == null) {
          
   
			return 0;
		}
		int size = 0;
		Data temp = head;
		while (temp.getNext() != null) {
          
   
			size++;
			temp = temp.getNext();
		}
		return size;
	}

	// 显示栈
	public void show() {
          
   
		if (isEmpty()) {
          
   
			System.out.println("栈为空");
			return;
		}
		Data[] datas = new Data[size()];
		Data temp = head.getNext();
		for (int i = 0; i < size(); i++) {
          
   
			datas[i] = temp;
			temp = temp.getNext();
		}
		for (int i = size() - 1; i >= 0; i--) {
          
   
			System.out.println(datas[i]);
		}
	}

	// 入栈
	public void push(Data newData) {
          
   
		if (isFull()) {
          
   
			System.out.println("栈已满，无法添加数据");
			return;
		}
		Data temp = head;
		while (temp.getNext() != null) {
          
   
			temp = temp.getNext();
		}
		temp.setNext(newData);
		newData.setPrev(temp);
	}

	// 出栈
	public Data pop() {
          
   
		if (isEmpty()) {
          
   
			throw new RuntimeException("栈为空，无法出栈");
		}
		Data temp = head;
		while (temp.getNext() != null) {
          
   
			temp = temp.getNext();
		}
		temp.getPrev().setNext(null);
		return temp;
	}

	// 查看栈顶的元素
	public Data peek() {
          
   
		if (isEmpty()) {
          
   
			throw new RuntimeException("栈为空，栈顶无元素");
		}
		Data temp = head;
		while (temp.getNext() != null) {
          
   
			temp = temp.getNext();
		}
		return temp;
	}
}

写一个主方法测试

public class LinkedStackDemo {
          
   
	public static void main(String[] args) {
          
   
		Data data1 = new Data(1);
		Data data2 = new Data(2);
		Data data3 = new Data(3);
		LinkedStack stack = new LinkedStack(3);
		stack.push(data1);
		stack.push(data2);
		stack.push(data3);
		stack.show();
		System.out.println("栈顶的元素是"+stack.peek());
		System.out.println("从栈顶取出的元素是"+stack.pop());
//		System.out.println("从栈顶取出的元素是"+stack.pop());
		System.out.println("取出栈顶的元素后栈内的元素：");
		stack.show();
	}
}