java实现链表栈_链表实现栈 java

前言

学会了数组栈后，链表栈就非常简单了，但这里还是做一些简单的介绍。

一、链表栈简单介绍

栈具有先入后出的特点，不仅可以用数组实现，也可以用链表实现，用链表的优点是栈的大小没有限制，可以不断的增长下去，数组想实现自动增长就需要多做一些工作。

二、链表栈图解

用链表实现一个栈非常简单，只需要在链表的基础上，使得添加元素和删除元素在链表尾部操作即可。

三、链表栈简单实现案例

在控制台模拟栈的入栈，出栈，显示栈，获取栈首元素等操作。

四、代码实现

1.测试代码

代码如下：

package com.yc.stack;

import java.util.Scanner;

public class LinkListStackDemo {
	public static void main(String[] args) {
		LinkListStack stack = new LinkListStack();
		String key = "";
		boolean loop = true;
		Scanner sc = new Scanner(System.in);
		while(loop){
			System.out.println("show:表示显示栈");
			System.out.println("peek:查看栈首元素");
			System.out.println("push:入栈");
			System.out.println("pop:出栈");
			System.out.println("exit:退出程序");
			System.out.println("请输入你的选择：");
			key = sc.next();
			switch (key) {
			case "show":
				stack.list();
				break;
			case "peek":
				System.out.println(stack.peek());
				break;
			case "push":
				System.out.println("请输入一个数");
				int val = sc.nextInt();
				stack.push(val);
				break;
			case "pop":
				System.out.printf("出栈元素为%d\n",stack.pop());
				break;
			case "exit":
				sc.close();
				loop = false;
				break;
			default:
				break;
			}
		}
		System.out.println("退出程序");
	}
}
class Node{
	int data;
	Node next;
}
class LinkListStack{
	int size;
	Node head = new Node();
	/**
	 * 入栈元素
	 * @param val
	 */
	public void push(int val){
		Node temp = head;
		Node hero = new Node();
		hero.data = val;
		while(temp.next!=null){
			temp = temp.next;
		}
		temp.next = hero;
		size++;
		return;
	}
	/**
	 * 判断栈是否为空
	 * @return
	 */
	public boolean isEmpty(){
		if(head.next==null){
			return true;
		}
		return false;
	}
	/**
	 * 查看栈首元素
	 * @return
	 */
	public int peek() {
		if(isEmpty()){
			throw new RuntimeException("栈为空，不能输出");
		}
		Node temp = head;
		while(temp.next!=null){
			temp = temp.next;
		}
		return temp.data;
	}
	/**
	 * 显示栈
	 */
	public void list(){
		Node temp = head.next;
		while(temp!=null){
			System.out.println(temp.data);
			temp = temp.next;
		}
		return;
	}
	/**
	 * 出栈元素
	 * @return
	 */
	public int pop(){
		if(head.next == null){
			throw new RuntimeException("栈为空，不能出栈");
		}
		Node temp = head;
		while(temp.next.next!=null){
			temp = temp.next;
		}
		int result = temp.next.data;
		temp.next = null;
		size--;
		return result;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

2.代码分析

代码十分简单，有兴趣的朋友可以把我的代码搞复杂点。

总结

这是第二种基础的栈，学会了这些基础的结构后，我相信以后的学习能够更加轻松。