当前位置:   article > 正文

Java基础--基于链表实现栈_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改正)。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/AllinToyou/article/detail/611845
推荐阅读
相关标签
  

闽ICP备14008679号