Java基础--基于链表实现栈_java链表实现栈

栈是一种基本数据结构，后进先出，对栈的操作都是在栈顶进行的，值得我们去学习，有很多算法问题都能用栈来实现，如LeetCode里面的括号问题的匹配就能用栈来实现。本文是基于上篇文章说的链表进行栈的实现

定义的栈的接口

public interface Stack<T> {
	//获取栈中的元素个数
	int getSize();
	//判断栈是否为空
	boolean isEmpty();
	//入栈
	void push(T ele);
	//出栈并返回栈顶元素
	T pop();
	//栈顶指针指向的元素
	T peek();
}
1
2
3
4
5
6
7
8
9
10
11
12

链表的定义和操作

这里的链表使用了虚拟头结点的方式来实现，这样比较方便进行操作，而且栈的操作：入栈和出栈都是在栈顶进行的，栈顶也对应链表中的头结点。此处的链表操作都是基于索引来进行操作。

package LinkedList;

public class DummyLinked<T> {
	private class Node{
		private T ele;
		private Node next;
		public Node(T t,Node next) {
			this.ele = t;
			this.next = next;
		}
		public Node(T t){
			this(t,null);
		}
	}
	private int size;     //链表元素个数
	private Node dummy;	  //链表的虚拟头结点
	public DummyLinked(){
		dummy = new Node(null,null);
		this.size = 0;
	}
	//获取链表元素的个数
	public int getSize(){
		return this.size;
	}
	//判断链表是否为空
	public boolean isEmpty(){
		return this.size == 0;
	}
	//向链表中间插入元素
	public void add(T ele,int index){
		if (index <0 || index >size){
			throw new IllegalArgumentException("index is error");
		}
			
		Node preNode = this.dummy;
		//找到要插入节点的前一个节点
		for(int i = 0; i < index; i++){
			preNode = preNode.next;
		}
		Node node = new Node(ele);
		//要插入的节点的下一个节点指向preNode节点的下一个节点
		node.next = preNode.next;
		//preNode的下一个节点指向要插入节点node
		preNode.next = node;
		this.size++;
			
	}
	//链表头部添加元素
	public void addFirst(T ele){
		this.add(ele, 0);
	}
	//向链表尾部插入元素
	public void addLast(T ele){
		this.add(ele, this.size);
	}
	//获取链表index位置的元素
	public T get(int index){
		if (index < 0 || index >= this.size){
			throw new IllegalArgumentException("index is error");
		}
		Node node = this.dummy.next;
		for(int i=0; i < index; i++){
			node = node.next;
		}
		return node.ele;
	}
	//获取链表的第一个元素
	public T getFirst(){
		return this.get(0);
	}
	//获取链表最后一个元素
	public T getLast(){
		return this.get(this.size-1);
	}
	//修改链表第index位置上的元素
	public void set(T ele, int index){
		if (index < 0 || index >= this.size){
			throw new IllegalArgumentException("set index is error");
		}
		Node node = this.dummy.next;
		for(int i = 0; i < index; i++){
			node = node.next;
		}
		node.ele = ele;
	}
	//判断链表是否包含某元素
	public boolean isContain(T ele){
		Node cur = this.dummy.next;
		while(cur != null){
			if (cur.ele.equals(ele)){
				return true;
			}
			cur = cur.next;
		}
		return false;
	}
		
	//删除链表index位置上的元素，并且返回删除元素
	public T remove(int index){
		Node pre = this.dummy;
		for (int i = 0; i < index; i++){
			pre = pre.next;
		}
		Node delNode = pre.next;
		pre.next = delNode.next;
		delNode.next = null;
		this.size--;
		return delNode.ele;
	}
	//删除链表的第一个元素
	public T removeFirst(){
		return this.remove(0);
	}
	//删除链表的最后一个元素
	public T removeLast(){
		return this.remove(this.size-1);
	}
	@Override
	public String toString() {
		StringBuffer sb = new StringBuffer();
		Node cur = this.dummy.next;
		while (cur != null){
			sb.append(cur.ele+"->");
			cur = cur.next;
		}
		sb.append("NULL");
		return sb.toString();
	}
}
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
121
122
123
124
125
126
127
128
129

栈的实现

实现定义好的栈的接口，并且实现该接口相关的方法就可以了。

栈的元素个数&&栈的判空操作

要获取栈中的元素个数，只需要调用链表中的getSize()方法就能很快的获取到了，判空操作也是直接调用链表的判空isEmpty()方法即可，大大简化了在实现栈这方面的操作。

@Override
	public int getSize() {
		return this.dummy.getSize();
	}
	@Override
	public boolean isEmpty() {
		return this.dummy.isEmpty();
	}
1
2
3
4
5
6
7
8

入栈&&出栈&&栈顶元素

入栈和出栈都是在栈顶实现的，也是在链表的头结点进行操做，我们只需要调用链表的addFirst()和removeFirst()方法就可以了，获取栈顶元素也是直接调用链表的getFirst(）方法就好，时间复杂度都是O(1)。

@Override
	public void push(T ele) {
		this.dummy.addFirst(ele);
	}
	@Override
	public T pop() {
		return  dummy.removeFirst();
	}
	@Override
	public T peek() {
		return this.dummy.getFirst();
	}
1
2
3
4
5
6
7
8
9
10
11
12

为了方便我们测试的时候能够清晰的看到效果，复写了toString方法

@Override
	public String toString() {
		StringBuffer sb = new StringBuffer();
		sb.append("stack top:");
		sb.append(this.dummy);
		return sb.toString();
	}
1
2
3
4
5
6
7

代码测试

public static void main(String[] args) {
		LinkedStack<Integer> stack = new LinkedStack<Integer>();
		for (int i =0; i < 5; i++){
			stack.push(i);
		}
		System.out.println(stack);
		System.out.println("栈顶元素："+stack.pop());
		System.out.println(stack);
		System.out.println("栈顶元素："+stack.peek());
		
	}
1
2
3
4
5
6
7
8
9
10
11

结果如下：
stack top:4->3->2->1->0->NULL
栈顶元素：4
stack top:3->2->1->0->NULL
栈顶元素：3

1
2
3
4
5
6

总结：这部分的实现比较简单，主要部分还是链表方面的熟悉度，熟练了链表这个也不成什么问题了（如上述有错的话，希望dalao改正）。