最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
Java利用栈来反转链表和排序操作代码
时间:2021-02-04 编辑:袖梨 来源:一聚教程网
本篇文章小编给大家分享一下Java利用栈来反转链表和排序操作代码,文章代码介绍的很详细,小编觉得挺不错的,现在分享给大家供大家参考,有需要的小伙伴们可以来看看。
栈是一个特殊的数据结构,特点是先进后出(First In Last Out 简称FILO),这种特殊的数据结构,可以用在对链表做反转中,或者字符串逆序,因为要把头变成尾,尾变成头,栈这种结构最合适不过了,下面来看看如何用栈来做链表的反转。
package com.xxx.algorithm.sort; import java.util.Stack; public class LinkedListReverse { public static Node reverseLinkedList(Node head){ Stackstack = new Stack (); while(head!=null){ stack.push(head); head = head.next; } if(!stack.isEmpty()) head = stack.pop(); Node cur = head; while(!stack.isEmpty()){ Node node = stack.pop(); node.next = null; cur.next = node; cur = node; } return head; } public static void display(Node head){ System.out.print("list:"); Node cur = head; while(cur!=null){ System.out.print(cur+"->"); cur = cur.next; } System.out.println(); } public static void main(String[] args) { Node a = new Node("a"); Node b = new Node("b"); Node c = new Node("c"); Node d = new Node("d"); Node e = new Node("e"); Node f = new Node("f"); Node g = new Node("g"); a.next = b; b.next = c; c.next = d; d.next = e; e.next = f; f.next = g; System.out.println("原始链表:"); display(a); Node head = reverseLinkedList(a); System.out.println("反转之后的链表:"); display(head); } } class Node{ String val; Node next; public Node(String val) { this.val = val; } @Override public String toString() { return "Node("+this.val+")"; } }
运行程序,结果如下:
原始链表:
list:Node(a)->Node(b)->Node(c)->Node(d)->Node(e)->Node(f)->Node(g)->
反转之后的链表:
list:Node(g)->Node(f)->Node(e)->Node(d)->Node(c)->Node(b)->Node(a)->
通过栈来反转链表思路很简单,这只是说了栈作为一种数据结构,其实用途很广泛。今天要介绍的另外一个栈的用途是如何通过栈来排序,利用栈来排序,需要有两个栈,一个存放原始数据,一个是辅助排序用的。
具体思路就是:将栈中的数据依次放入辅助栈中,放入辅助栈的要求是按照数据从大到小的排列(或者从小到大),先进入的是较大的数,后进入的是较小的数,如果原栈中没有数据了,说明数据已经在辅助栈中排好序了,接着我们把数据再一次性放入原栈中,如果遍历,就是一个排好序的数组了。
这里面把原栈中的数据放入辅助栈中,需要借助一个中间变量,原栈中弹出的数据放入中间变量中,而不是直接入辅助栈,如果栈顶的元素小于中间变量,那么将小于的数据再放入原栈中,再将中间变量放入辅助栈,接着再将原栈中的数据放入辅助栈,直到原栈为空。将中间变量放入辅助栈,类似插入排序,需要找到一个合适的位置,而移动出一个合适的位置,就是把辅助栈中的数据再次压入原栈中。
算法示例代码如下:
package com.xxx.algorithm.sort; import java.util.Iterator; import java.util.Stack; public class StackSortDemo { public static void sortByStack(Stackstack){ Stack help = new Stack (); while(!stack.isEmpty()){ int cur = stack.pop(); while(!help.isEmpty()&&help.peek() stack){ System.out.print("stack:"); Iterator it = stack.iterator(); while(it.hasNext()){ System.out.print(it.next()+"->"); } System.out.print("null"); System.out.println(); } public static void main(String[] args) { Stack stack = new Stack (); stack.push(2); stack.push(9); stack.push(5); stack.push(4); stack.push(6); stack.push(3); stack.push(8); stack.push(7); System.out.println("原始栈:"); display(stack); sortByStack(stack); System.out.println("排序之后的栈:"); display(stack); } }
运行程序,打印信息如下:
原始栈:
stack:2->9->5->4->6->3->8->7->null
排序之后的栈:
stack:2->3->4->5->6->7->8->9->null
相关文章
- SpringBoot自定义bean绑定解析 10-24
- Javaweb工程运行报错HTTP Status 404解决教程 10-20
- JAVA获取jvm和操作系统相关信息方法 10-20
- BeanFactory和FactoryBean的区别讲解 10-20
- 微信小程序的宿主环境实现教程 10-10
- dispatchEvent解决重叠元素响应事件教程 10-10