棧是一個特殊的數(shù)據(jù)結(jié)構，特點是先進后出(First In Last Out 簡稱FILO)，這種特殊的數(shù)據(jù)結(jié)構，可以用在對鏈表做反轉(zhuǎn)中，或者字符串逆序，因為要把頭變成尾，尾變成頭，棧這種結(jié)構最合適不過了，下面來看看如何用棧來做鏈表的反轉(zhuǎn)。

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('反轉(zhuǎn)之后的鏈表：'); display(head); }} class Node{ String val; Node next; public Node(String val) { this.val = val; } @Override public String toString() { return 'Node('+this.val+')'; }}運行程序，結(jié)果如下：

原始鏈表：

list:Node(a)->Node(b)->Node(c)->Node(d)->Node(e)->Node(f)->Node(g)->

反轉(zhuǎn)之后的鏈表：

list:Node(g)->Node(f)->Node(e)->Node(d)->Node(c)->Node(b)->Node(a)->

通過棧來反轉(zhuǎn)鏈表思路很簡單，這只是說了棧作為一種數(shù)據(jù)結(jié)構，其實用途很廣泛。今天要介紹的另外一個棧的用途是如何通過棧來排序，利用棧來排序，需要有兩個棧，一個存放原始數(shù)據(jù)，一個是輔助排序用的。

具體思路就是：將棧中的數(shù)據(jù)依次放入輔助棧中，放入輔助棧的要求是按照數(shù)據(jù)從大到小的排列（或者從小到大），先進入的是較大的數(shù)，后進入的是較小的數(shù)，如果原棧中沒有數(shù)據(jù)了，說明數(shù)據(jù)已經(jīng)在輔助棧中排好序了，接著我們把數(shù)據(jù)再一次性放入原棧中，如果遍歷，就是一個排好序的數(shù)組了。

這里面把原棧中的數(shù)據(jù)放入輔助棧中，需要借助一個中間變量，原棧中彈出的數(shù)據(jù)放入中間變量中，而不是直接入輔助棧，如果棧頂?shù)脑匦∮谥虚g變量，那么將小于的數(shù)據(jù)再放入原棧中，再將中間變量放入輔助棧，接著再將原棧中的數(shù)據(jù)放入輔助棧，直到原棧為空。將中間變量放入輔助棧，類似插入排序，需要找到一個合適的位置，而移動出一個合適的位置，就是把輔助棧中的數(shù)據(jù)再次壓入原棧中。

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); }}運行程序，打印信息如下：

原始棧：

stack:2->9->5->4->6->3->8->7->null

排序之后的棧：

stack:2->3->4->5->6->7->8->9->null

補充：Java數(shù)據(jù)結(jié)構與算法-------鏈表反轉(zhuǎn)（如何實現(xiàn)鏈表的逆序）

鏈表 head -->1-->2-->3-->4-->5-->6-->7, 如何反轉(zhuǎn)為head -->7-->6->5-->4-->3-->2-->1,

思路：從鏈表的第二個節(jié)點開始，把遍歷到的節(jié)點插入到頭結(jié)點的后面，直到遍歷結(jié)束。

假設原鏈表：head -->1-->2-->3-->4-->5-->6-->7,

在遍歷2的時候，鏈表變?yōu)閔ead -->2-->1-->3-->4-->5-->6-->7,

package LinkedList.Reverse;/* 這里使用插入法進行反轉(zhuǎn)鏈表 思路：從鏈表的第二個節(jié)點開始，把遍歷到的節(jié)點插入到頭結(jié)點的后面，直到遍歷結(jié)束。 假設原鏈表：head -->1-->2-->3-->4-->5-->6-->7, 在遍歷2的時候，鏈表變?yōu)閔ead -->2-->1-->3-->4-->5-->6-->7, */public class Reverse { public static void main(String[] args) { //定義頭結(jié)點 LNode head=new LNode(); head.next=null; LNode temp=null; LNode cur=head; //構造鏈表 for (int i = 1; i < 8; i++) { temp=new LNode(); //定義一個輔助節(jié)點 temp.data=i; //temp數(shù)據(jù)為I temp.next=null; cur.next=temp; //頭結(jié)點的下一個節(jié)點為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){//如果頭結(jié)點為空，或者頭結(jié)點的下一個節(jié)點為空，鏈表不用反轉(zhuǎn) return; } LNode cur=null;//定義一個當前節(jié)點 LNode next=null;//定義一個后繼節(jié)點 //讓當前節(jié)點指向第二個節(jié)點 cur=head.next.next; //先把第一個節(jié)點設置成最后一個節(jié)點 head.next.next=null; while (cur!=null){//如果當前節(jié)點不為空 next=cur.next;//先保存當前節(jié)點的后繼節(jié)點 如 2 的后面一個節(jié)點3 先保存起來 cur.next=head.next;// 就是把2 的下一個節(jié)點指向1 head.next=cur;//把頭結(jié)點指向2 cur=next; //將當前節(jié)點指向下一個 3 } }} class LNode{ LNode next; int data;}使用遞歸法

//使用遞歸法 private static LNode RecursiveReverse(LNode head){ //如果鏈表為空或者鏈表只有一個元素 if (head==null || head.next==null){ return head; }else { //反轉(zhuǎn)后面的節(jié)點 LNode newHead = RecursiveReverse(head.next); //把前面遍歷的節(jié)點加到后面節(jié)點逆序后鏈表的尾部 head.next.next=head; head.next=null; return newHead; } } public static void Reverse(LNode head){ if (head==null){ return; } //獲取鏈表的第一個節(jié)點 LNode firstNode=head.next; //對鏈表進行逆序 LNode newhead = RecursiveReverse(firstNode); head.next=newhead; }

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持好吧啦網(wǎng)。如有錯誤或未考慮完全的地方，望不吝賜教。