一聚教程网:一个值得你收藏的教程网站

最新下载

热门教程

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){
 Stack stack = 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(Stack stack){
 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

热门栏目