利用栈来反转链表和排序（Java实现）

清疚 2021-12-16 09:07 220阅读 0赞

栈是一个特殊的数据结构，特点是先进后出(First In Last Out 简称FILO)，这种特殊的数据结构，可以用在对链表做反转中，或者字符串逆序，因为要把头变成尾，尾变成头，栈这种结构最合适不过了，下面来看看如何用栈来做链表的反转。

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+")";
    	}
    }

运行程序，结果如下：

原始链表：
    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<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