用链表实现栈(Java)
程序员文章站
2022-03-25 18:48:31
...
思路:
1.创建节点,节点内容包括值、前一节点、后一节点;
2.用双向链表模拟,每次在链表末尾插入元素并将栈顶的index+1;
3.显示栈元素:用一个临时节点tempNode从末尾curNode开始向前遍历输出,直到tempNode.preNode==null;
4.出栈:记录链表末尾值,末尾节点指向前一节点,并将其后节点置为null、栈顶的index-1;
public class LinkListStackDemo {
public static void main(String[] args) {
LinkListStack linkListStack = new LinkListStack();
linkListStack.setMaxSize(5);
linkListStack.push(2);
linkListStack.push(32);
linkListStack.push(2543);
linkListStack.list();
System.out.println("---------------------");
System.out.println("出栈元素为:"+linkListStack.pop());
System.out.println("出栈元素为:"+linkListStack.pop());
System.out.println("出栈元素为:"+linkListStack.pop());
try {
int res = linkListStack.pop();
System.out.println("出栈元素为:"+res);
} catch (Exception e) {
System.out.println("栈空,么得出了");
}
linkListStack.list();
}
}
//用链表模拟栈
class LinkListStack{
private int maxSize;//最大容量
private int top = -1;//栈顶index
private Node headNode = new Node(0);//创建头节点
private Node curNode = headNode;//当前栈顶节点,一开始指向头节点
public int getMaxSize() {
return maxSize;
}
public void setMaxSize(int maxSize) {
this.maxSize = maxSize;
}
public Node getHeadNode() {
return headNode;
}
public void setHeadNode(Node headNode) {
this.headNode = headNode;
}
public boolean isEmpty() {
return top==-1;
}
public boolean isFull() {
return top == maxSize -1;
}
//向栈中添加元素
public void push(int value) {
//判断是否栈满,若已满,就返回并提示
if (isFull()) {
System.out.println("Stack is full!!! Can't push");
return;
}
top++;
Node newNode = new Node(value);//创建一个新节点
//将新节点加入链表
curNode.setNext(newNode);
newNode.setPreNode(curNode);
//栈顶节点指向新节点
curNode = newNode;
}
public int pop() {
//判断是否栈空,空栈无法出栈
if (isEmpty()) {
throw new RuntimeException("Stack is empty!!!");
}
//用popValue保存栈顶的元素值
int popValue = curNode.getValue();
//栈顶指向前一元素
curNode = curNode.getPreNode();
//栈顶后节点置为null
curNode.setNext(null);
top--;//栈顶的index--
return popValue;
}
public void list() {
if (isEmpty()) {
System.out.println("栈空,无法显示");
}
//从链表尾倒着读取元素
Node tempNode = curNode;
while (tempNode.getPreNode() != null) {
System.out.println(tempNode.getValue());
tempNode = tempNode.getPreNode();
}
}
}
class Node {
private int value;
private Node preNode = null;
private Node nextNode = null;
public void setValue(int value) {
this.value = value;
}
public int getValue() {
return value;
}
public Node getNext() {
return nextNode;
}
public void setNext(Node next) {
this.nextNode = next;
}
public Node getPreNode() {
return preNode;
}
public void setPreNode(Node pre) {
this.preNode = pre;
}
public Node(int val) {
this.value = val;
}
}