棧是一個(gè)特殊的數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)是先進(jìn)后出(First In Last Out 簡稱FILO)，這種特殊的數(shù)據(jù)結(jié)構(gòu)，可以用在對(duì)鏈表做反轉(zhuǎn)中，或者字符串逆序，因?yàn)橐杨^變成尾，尾變成頭，棧這種結(jié)構(gòu)最合適不過了，下面來看看如何用棧來做鏈表的反轉(zhuǎn)。
|
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("反轉(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+")"; }} |
運(yùn)行程序，結(jié)果如下：
原始鏈表：
|
1
|
list:Node(a)->Node(b)->Node(c)->Node(d)->Node(e)->Node(f)->Node(g)-> |
反轉(zhuǎn)之后的鏈表：
|
1
|
list:Node(g)->Node(f)->Node(e)->Node(d)->Node(c)->Node(b)->Node(a)-> |
通過棧來反轉(zhuǎn)鏈表思路很簡單，這只是說了棧作為一種數(shù)據(jù)結(jié)構(gòu)，其實(shí)用途很廣泛。今天要介紹的另外一個(gè)棧的用途是如何通過棧來排序，利用棧來排序，需要有兩個(gè)棧，一個(gè)存放原始數(shù)據(jù)，一個(gè)是輔助排序用的。
具體思路就是：將棧中的數(shù)據(jù)依次放入輔助棧中，放入輔助棧的要求是按照數(shù)據(jù)從大到小的排列（或者從小到大），先進(jìn)入的是較大的數(shù)，后進(jìn)入的是較小的數(shù)，如果原棧中沒有數(shù)據(jù)了，說明數(shù)據(jù)已經(jīng)在輔助棧中排好序了，接著我們把數(shù)據(jù)再一次性放入原棧中，如果遍歷，就是一個(gè)排好序的數(shù)組了。
這里面把原棧中的數(shù)據(jù)放入輔助棧中，需要借助一個(gè)中間變量，原棧中彈出的數(shù)據(jù)放入中間變量中，而不是直接入輔助棧，如果棧頂?shù)脑匦∮谥虚g變量，那么將小于的數(shù)據(jù)再放入原棧中，再將中間變量放入輔助棧，接著再將原棧中的數(shù)據(jù)放入輔助棧，直到原棧為空。將中間變量放入輔助棧，類似插入排序，需要找到一個(gè)合適的位置，而移動(dòng)出一個(gè)合適的位置，就是把輔助棧中的數(shù)據(jù)再次壓入原棧中。
算法示例代碼如下：
|
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); }} |
運(yùn)行程序，打印信息如下：
原始棧：
|
1
|
stack:2->9->5->4->6->3->8->7->null |
排序之后的棧：
|
1
|
stack:2->3->4->5->6->7->8->9->null |
補(bǔ)充：Java數(shù)據(jù)結(jié)構(gòu)與算法-------鏈表反轉(zhuǎn)（如何實(shí)現(xiàn)鏈表的逆序）
1. 問題：
鏈表 head -->1-->2-->3-->4-->5-->6-->7, 如何反轉(zhuǎn)為head -->7-->6->5-->4-->3-->2-->1,
2.思路（使用插入法）
思路：從鏈表的第二個(gè)節(jié)點(diǎn)開始，把遍歷到的節(jié)點(diǎn)插入到頭結(jié)點(diǎn)的后面，直到遍歷結(jié)束。
假設(shè)原鏈表：head -->1-->2-->3-->4-->5-->6-->7,
在遍歷2的時(shí)候，鏈表變?yōu)閔ead -->2-->1-->3-->4-->5-->6-->7,
3.代碼實(shí)現(xiàn)：
|
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;/* 這里使用插入法進(jìn)行反轉(zhuǎn)鏈表 思路：從鏈表的第二個(gè)節(jié)點(diǎn)開始，把遍歷到的節(jié)點(diǎn)插入到頭結(jié)點(diǎn)的后面，直到遍歷結(jié)束。 假設(shè)原鏈表：head -->1-->2-->3-->4-->5-->6-->7, 在遍歷2的時(shí)候，鏈表變?yōu)閔ead -->2-->1-->3-->4-->5-->6-->7, */public class Reverse { public static void main(String[] args) { //定義頭結(jié)點(diǎn) LNode head=new LNode(); head.next=null; LNode temp=null; LNode cur=head; //構(gòu)造鏈表 for (int i = 1; i < 8; i++) { temp=new LNode(); //定義一個(gè)輔助節(jié)點(diǎn) temp.data=i; //temp數(shù)據(jù)為I temp.next=null; cur.next=temp; //頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為temp cur=temp; //cur后移 由head移動(dòng)到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é)點(diǎn)為空，或者頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為空，鏈表不用反轉(zhuǎn) return; } LNode cur=null;//定義一個(gè)當(dāng)前節(jié)點(diǎn) LNode next=null;//定義一個(gè)后繼節(jié)點(diǎn) //讓當(dāng)前節(jié)點(diǎn)指向第二個(gè)節(jié)點(diǎn) cur=head.next.next; //先把第一個(gè)節(jié)點(diǎn)設(shè)置成最后一個(gè)節(jié)點(diǎn) head.next.next=null; while (cur!=null){//如果當(dāng)前節(jié)點(diǎn)不為空 next=cur.next;//先保存當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn) 如 2 的后面一個(gè)節(jié)點(diǎn)3 先保存起來 cur.next=head.next;// 就是把2 的下一個(gè)節(jié)點(diǎn)指向1 head.next=cur;//把頭結(jié)點(diǎn)指向2 cur=next; //將當(dāng)前節(jié)點(diǎn)指向下一個(gè) 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){ //如果鏈表為空或者鏈表只有一個(gè)元素 if (head==null || head.next==null){ return head; }else { //反轉(zhuǎn)后面的節(jié)點(diǎn) LNode newHead = RecursiveReverse(head.next); //把前面遍歷的節(jié)點(diǎn)加到后面節(jié)點(diǎn)逆序后鏈表的尾部 head.next.next=head; head.next=null; return newHead; } } public static void Reverse(LNode head){ if (head==null){ return; } //獲取鏈表的第一個(gè)節(jié)點(diǎn) LNode firstNode=head.next; //對(duì)鏈表進(jìn)行逆序 LNode newhead = RecursiveReverse(firstNode); head.next=newhead; } |
以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持服務(wù)器之家。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教。
原文鏈接：https://blog.csdn.net/feinifi/article/details/94741276
