Java 利用棧來(lái)反轉(zhuǎn)鏈表和排序的操作

更新時(shí)間：2021年02月04日 10:34:22 作者：luffy5459

這篇文章主要介紹了Java 利用棧來(lái)反轉(zhuǎn)鏈表和排序的操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧

棧是一個(gè)特殊的數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)是先進(jìn)后出(First In Last Out 簡(jiǎn)稱FILO)，這種特殊的數(shù)據(jù)結(jié)構(gòu)，可以用在對(duì)鏈表做反轉(zhuǎn)中，或者字符串逆序，因?yàn)橐杨^變成尾，尾變成頭，棧這種結(jié)構(gòu)最合適不過(guò)了，下面來(lái)看看如何用棧來(lái)做鏈表的反轉(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+")";
 }
}

運(yùn)行程序，結(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)->

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

具體思路就是：將棧中的數(shù)據(jù)依次放入輔助棧中，放入輔助棧的要求是按照數(shù)據(jù)從大到小的排列（或者從小到大），先進(jìn)入的是較大的數(shù)，后進(jìn)入的是較小的數(shù)，如果原棧中沒(méi)有數(shù)據(jù)了，說(shuō)明數(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ù)再次壓入原棧中。

算法示例代碼如下：

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

原始棧：

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

排序之后的棧：

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

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

1. 問(wèn)題：

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

2.思路（使用插入法）

思路：從鏈表的第二個(gè)節(jié)點(diǎn)開(kāi)始，把遍歷到的節(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)：

package LinkedList.Reverse;
/*
 這里使用插入法進(jìn)行反轉(zhuǎn)鏈表
 思路：從鏈表的第二個(gè)節(jié)點(diǎn)開(kāi)始，把遍歷到的節(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 先保存起來(lái)
   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;
}

使用遞歸法

//使用遞歸法
 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è)參考，也希望大家多多支持腳本之家。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教。

您可能感興趣的文章: