자바 스 택 을 이용 하여 링크 와 정렬 을 반전 시 키 는 작업

스 택 은 특수 한 데이터 구조 로 선진 적 인 후에 나 오 는 것 이 특징 이다(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

보충:자바 데이터 구조 와 알고리즘----링크 반전(링크 의 역 순 서 를 어떻게 실현 합 니까)
1.문제:
링크 헤드-->1->2->3->4->5->6->7,헤드 로 반전 하 는 방법-->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.코드 구현:

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;
}

귀속 법 을 사용 하 다

//     
 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;
 
 }

이상 은 개인 적 인 경험 이 므 로 여러분 에 게 참고 가 되 기 를 바 랍 니 다.여러분 들 도 저 희 를 많이 응원 해 주시 기 바 랍 니 다.만약 잘못 이 있 거나 완전히 고려 하지 않 은 부분 이 있다 면 아낌없이 가르침 을 주시 기 바 랍 니 다.