栈是一个特殊的数据结构，特点是先进后出(First In Last Out 简称FILO)，这种特殊的数据结构，可以用在对链表做反转中，或者字符串逆序，因为要把头变成尾，尾变成头，栈这种结构最合适不过了，下面来看看如何用栈来做链表的反转。
|
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 |
package com.xxx.algorithm.sort; import java.util.Stack; public class LinkedListReverse { public static Node reverseLinkedList(Node head){ Stack<Node> stack = new Stack<Node>(); 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+ ")" ; } } |
运行程序，结果如下：
原始链表：
|
1 |
list:Node(a)->Node(b)->Node(c)->Node(d)->Node(e)->Node(f)->Node(g)-> |
反转之后的链表：
|
1 |
list:Node(g)->Node(f)->Node(e)->Node(d)->Node(c)->Node(b)->Node(a)-> |
通过栈来反转链表思路很简单，这只是说了栈作为一种数据结构，其实用途很广泛。今天要介绍的另外一个栈的用途是如何通过栈来排序，利用栈来排序，需要有两个栈，一个存放原始数据，一个是辅助排序用的。
具体思路就是：将栈中的数据依次放入辅助栈中，放入辅助栈的要求是按照数据从大到小的排列（或者从小到大），先进入的是较大的数，后进入的是较小的数，如果原栈中没有数据了，说明数据已经在辅助栈中排好序了，接着我们把数据再一次性放入原栈中，如果遍历，就是一个排好序的数组了。
这里面把原栈中的数据放入辅助栈中，需要借助一个中间变量，原栈中弹出的数据放入中间变量中，而不是直接入辅助栈，如果栈顶的元素小于中间变量，那么将小于的数据再放入原栈中，再将中间变量放入辅助栈，接着再将原栈中的数据放入辅助栈，直到原栈为空。将中间变量放入辅助栈，类似插入排序，需要找到一个合适的位置，而移动出一个合适的位置，就是把辅助栈中的数据再次压入原栈中。
算法示例代码如下：
|
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 |
package com.xxx.algorithm.sort; import java.util.Iterator; import java.util.Stack; public class StackSortDemo {
public static void sortByStack(Stack<Integer> stack){ Stack<Integer> help = new Stack<Integer>(); while (!stack.isEmpty()){ int cur = stack.pop(); while (!help.isEmpty()&&help.peek()<cur){ stack.push(help.pop()); } help.push(cur); } while (!help.isEmpty()){ stack.push(help.pop()); } }
public static void display(Stack<Integer> stack){ System.out.print( "stack:" ); Iterator<Integer> 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<Integer> stack = new Stack<Integer>(); 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); } } |
运行程序，打印信息如下：
原始栈：
|
1 |
stack: 2 -> 9 -> 5 -> 4 -> 6 -> 3 -> 8 -> 7 -> null |
排序之后的栈：
|
1 |
stack: 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null |
补充：Java数据结构与算法-------链表反转（如何实现链表的逆序）
1. 问题：
链表 head -->1-->2-->3-->4-->5-->6-->7, 如何反转为head -->7-->6->5-->4-->3-->2-->1,
2.思路（使用插入法）
思路：从链表的第二个节点开始，把遍历到的节点插入到头结点的后面，直到遍历结束。
假设原链表：head -->1-->2-->3-->4-->5-->6-->7,
在遍历2的时候，链表变为head -->2-->1-->3-->4-->5-->6-->7,
3.代码实现：
|
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 |
package LinkedList.Reverse; /* 这里使用插入法进行反转链表 思路：从链表的第二个节点开始，把遍历到的节点插入到头结点的后面，直到遍历结束。 假设原链表：head -->1-->2-->3-->4-->5-->6-->7, 在遍历2的时候，链表变为head -->2-->1-->3-->4-->5-->6-->7, */ public class Reverse { public static void main(String[] args) { //定义头结点 LNode head= new LNode(); head.next= null ; LNode temp= null ; LNode cur=head; //构造链表 for ( int i = 1 ; i < 8 ; i++) { temp= new LNode(); //定义一个辅助节点 temp.data=i; //temp数据为I temp.next= null ; cur.next=temp; //头结点的下一个节点为temp cur=temp; //cur后移 由head移动到temp } System.out.println( "逆序前：" ); for (cur=head.next;cur!= null ;cur=cur.next){ System.out.println(cur.data+ " " ); } System.out.println( "逆序后：" ); Reverse(head); for (cur=head.next;cur!= null ;cur=cur.next){ System.out.println(cur.data+ " " ); }
} public static void Reverse(LNode head){ if (head== null || head.next== null ){ //如果头结点为空，或者头结点的下一个节点为空，链表不用反转 return ; } LNode cur= null ; //定义一个当前节点 LNode next= null ; //定义一个后继节点 //让当前节点指向第二个节点 cur=head.next.next; //先把第一个节点设置成最后一个节点 head.next.next= null ; while (cur!= null ){ //如果当前节点不为空 next=cur.next; //先保存当前节点的后继节点 如 2 的后面一个节点3 先保存起来 cur.next=head.next; // 就是把2 的下一个节点指向1 head.next=cur; //把头结点指向2 cur=next; //将当前节点指向下一个 3 } } }
class LNode{ LNode next; int data; } |
使用递归法
|
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 |
//使用递归法 private static LNode RecursiveReverse(LNode head){ //如果链表为空或者链表只有一个元素 if (head== null || head.next== null ){ return head; } else { //反转后面的节点 LNode newHead = RecursiveReverse(head.next); //把前面遍历的节点加到后面节点逆序后链表的尾部 head.next.next=head; head.next= null ; return newHead; } } public static void Reverse(LNode head){ if (head== null ){ return ; } //获取链表的第一个节点 LNode firstNode=head.next; //对链表进行逆序 LNode newhead = RecursiveReverse(firstNode); head.next=newhead;
} |
以上为个人经验，希望能给大家一个参考，也希望大家多多支持。如有错误或未考虑完全的地方，望不吝赐教。
原文链接：https://blog.csdn.net/feinifi/article/details/94741276
查看更多关于Java 利用栈来反转链表和排序的操作的详细内容...