栈的实现之用链表实现

用链表实现栈

上次我们用数组实现了栈，数组结构实现栈比较容易，那么用链表该如何实现栈呢？我们知道栈是遵循的先进后出原则，所以当我们要用链表实现的话也要采用先进后出的原则。所以在这里我们要用头插法来创建链表实现栈的先进后出的原则。

1. 创建节点类，首先需要创建链表的节点类，类中的成员包括编号和next指针。因为成员变量声明为私有的成员变量，所以需要获取一下set和get方法。

class stackNode{
    
	private int no;
	private stackNode headnext;
	public int getNo() {
    
		return no;
	}
	public void setNo(int no) {
    
		this.no = no;
	}
	public stackNode getHeadnext() {
    
		return headnext;
	}
	public void setHeadnext(stackNode headnext) {
    
		this.headnext = headnext;
	}
	public stackNode(int no) {
    
		// TODO Auto-generated constructor stub
		this.no = no;
	}
}

2. 创建链表实现入栈的功能，首先需要创建一个bottom栈底作为标识，然后需要创建一个top栈顶指针，如果添加进去新的节点top指针需要向上移动始终让top指针指向栈顶

class singleStack{
    
	//定义一个bottom栈底节点不用来存放数据，作为一个标识来识别栈底
	stackNode bottom = new stackNode(0);
	//定义栈顶指针
	stackNode top = bottom;
	//入栈
	public void push(stackNode stackNode) {
    
		//创建一个临时变量来指向栈顶
		stackNode tempNode = top;
		while(true)
		{
    
			//如果临时变量指向栈顶的话就说明找到了栈顶，从栈顶插入新的节点即可
			if (tempNode == top) {
    
				break;
			}
			//如果没有找到的话就继续去找
			tempNode = tempNode.getnext();
		}
		//新插入节点的next指向top
		stackNode.setnext(top);
		//top移动到新插入的节点标识栈顶
		top = stackNode;
	}
}

3. 出栈，出栈十分简单，也需要一个临时变量去指向栈顶，然后top断开即可。

//出栈
	public int pop() {
    
		stackNode tempNode = top;
		top = top.getnext();
		int no = tempNode.getNo();
		System.out.printf("出栈元素为：%d\n", no);
		return no;
	}

4. 遍历栈，遍历栈与遍历单链表是一样的，只不过输出的数据的和插入的数据是相反的，这也保持了栈的基本原则。

//遍历栈
	public void showStack() {
    
		//如果top的next为空的话则说明此栈为空
		if (top.getnext() == null) {
    
			System.out.println("这是一个空栈！！！");
			return;
		}
		//通过辅助变量去遍历栈
		stackNode tempNode = top;
		while(true)
		{
    
			if (tempNode.getnext() == null) {
    
				break;
			}
			//当不为空时输出结点信息，并将temp继续向下移动
			System.out.println(tempNode.getNo());
			tempNode = tempNode.getnext();
		}
	}

5. 测试代码

public class SingleStackDemo {
    
	public static void main(String[] args) {
    
		// TODO Auto-generated method stub
		singleStack stack = new singleStack();
		stackNode stackNode1 = new stackNode(1);
		stackNode stackNode2 = new stackNode(2);
		stackNode stackNode3 = new stackNode(3);
		stackNode stackNode4 = new stackNode(4);
		stack.push(stackNode1);
		stack.push(stackNode2);
		stack.push(stackNode3);
		stack.push(stackNode4);
		stack.showStack();
		stack.pop();
		stack.pop();
		System.out.println("元素出栈之后的栈的情况为：");
		stack.showStack();
	}
}

6. 测试结果