栈是一个特殊的数据结构,特点是先进后出(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