스택 및 대기열 :
일반적으로 프로그래머가 수명주기가 짧고 런타임에만 생성되는 알고리즘의 개념을 지원하는 도구로 사용됩니다.
액세스가 제한되고 특정 순간에 하나의 데이터 만 읽거나 삭제할 수 있습니다.
배열 및 연결된 목록을 사용하여 스택을 구현하는 등 사용자에게는 보이지 않는 내부 구현 메커니즘을 갖춘 추상 구조입니다.
스택 구조를 시뮬레이션하십시오
동시에, 하나의 데이터 만 액세스 할 수 있으며, 스택 및 아웃 모두에 대한 후반기의 시간 복잡성은 O (1)입니다. 즉, 스택의 데이터 항목 수에 따라 다릅니다. 배열을 스택의 저장 구조로 사용하여 작동이 비교적 빠릅니다.
공개 클래스 스택 <t> {private int max; 개인 t [] ary; 개인 int 탑; // 포인터, 스택 공개 스택의 상단 요소에 대한 위시 (int size) {this.max = size; ary = (t []) 새 개체 [max]; 상단 = -1; } // public void push (t data) {if (! isfull ()) ary [++ top] = data; } // public t pop () {if (isempty ()) {return null; } return ary [top-]; } // 스택의 상단을보십시오 public t peek () {return ary [top]; } // 스택은 빈 공개 부울 isempty () {return top == -1; } // 스택은 전체 공개 부울 isfull () {return top == max -1; } // size public int size () {return top + 1; } public static void main (string [] args) {stacks <integer> stack = new Stacks <integer> (3); for (int i = 0; i <5; i ++) {stack.push (i); System.out.println ( "size :" + stack.size ()); } for (int i = 0; i <5; i ++) {integer peek = stack.peek (); System.out.println ( "Peek :" + Peek); System.out.println ( "size :" + stack.size ()); } for (int i = 0; i <5; i ++) {integer pop = stack.pop (); System.out.println ( "팝 :" + 팝); System.out.println ( "size :" + stack.size ()); } system.out.println ( "----"); for (int i = 5; i> 0; i-) {stack.push (i); System.out.println ( "size :" + stack.size ()); } for (int i = 5; i> 0; i-) {integer peek = stack.peek (); System.out.println ( "Peek :" + Peek); System.out.println ( "size :" + stack.size ()); } for (int i = 5; i> 0; i-) {integer pop = stack.pop (); System.out.println ( "팝 :" + 팝); System.out.println ( "size :" + stack.size ()); }}} 위의 예에서는 배열의 크기가 있어야하므로 최대 규정이 있습니다. 제한이 없으면 저장에 다른 구조를 사용할 수 있으며 물론 새 새로운 길이를 새로 제공 할 수도 있습니다.
예를 들어 LinkedList Storage를 사용하여 스택을 구현하십시오
Public Class Stacksss <t> {private linkedlist <t> datas; public stackss () {datas = new LinkedList <t> (); } // 스택을 공개 void push (t data) {datas.addlast (data); } // stack public t pop () {return datas.removelast (); } // 스택의 상단을 확인 public t peek () {return datas.getlast (); } // 스택이 빈 공개 부울 isempty () {return datas.isempty (); } // size public int size () {return datas.size (); } public static void main (string [] args) {stacks <integer> stack = new Stacks <integer> (3); for (int i = 0; i <5; i ++) {stack.push (i); System.out.println ( "size :" + stack.size ()); } for (int i = 0; i <5; i ++) {integer peek = stack.peek (); System.out.println ( "Peek :" + Peek); System.out.println ( "size :" + stack.size ()); } for (int i = 0; i <5; i ++) {integer pop = stack.pop (); System.out.println ( "팝 :" + 팝); System.out.println ( "size :" + stack.size ()); } system.out.println ( "----"); for (int i = 5; i> 0; i-) {stack.push (i); System.out.println ( "size :" + stack.size ()); } for (int i = 5; i> 0; i-) {stack.push (i); System.out.println ( "size :" + stack.size ()); } for (int i = 5; i> 0; i-) {integer peek = stack.peek (); System.out.println ( "Peek :" + Peek); System.out.println ( "size :" + stack.size ()); } for (int i = 5; i> 0; i-) {integer pop = stack.pop (); System.out.println ( "팝 :" + 팝); System.out.println ( "size :" + stack.size ()); }}}STATCK 구조를 사용하여 단어 역 순서
공개 클래스 WordReverse {public static void main (String [] args) {Reverse ( "Co., Ltd."); } static void reverse (string word) {if (word == null) return; stacksss <atirected> stack = new stackss <문자> (); char [] chararray = Word.tochararray (); int len = chararray.length; for (int i = 0; i <len; i ++) {stack.push (chararray [i]); } StringBuilder sb = new StringBuilder (); while (! stack.isempty ()) {sb.append (stack.pop ()); } system.out.println ( "반전 후 :" + sb.toString ()); }}인쇄:
반전 후 : 소셜 스타일
시뮬레이션 대기열 (일반 대기열, 이중 엔드 큐, 우선 순위 큐)
대기줄:
먼저, 대기열 문제를 다루십시오. 첫 번째 대기열, 첫 번째 프로세스, 첫 번째 행, 두 번째 행 등. 이전 프로세스가 완료되고 삽입 및 제거 작업의 시간 복잡성은 O (1)입니다. 뒷면에서 삽입하고 앞면에서 이중 엔드 큐를 제거하십시오.
즉, 큐의 양쪽 끝에서 삽입하고 제거 할 수 있습니다 : Insertleft, InserTright, Removeleft, Removeright
스택 및 대기열이 포함 된 기능. Insertleft 및 Removeleft를 제거하면 스택과 동일합니다. Insertleft 및 Removeright를 제거하면 대기열과 동일합니다. 일반적으로 사용 빈도는 낮고 시간 복잡성 O (1)
우선 큐 :
우선 순위별로 정렬 된 내부 시퀀스를 유지하십시오. 삽입 할 때 삽입 위치, 시간 복잡성 O (N), O (1)를 삭제해야합니다.
/** 먼저 큐는 먼저, 포인터는 삽입 위치를 나타내고, 포인터는 데이터 항목의 위치를 꺼내는 위치를 나타냅니다*/ public class queueq <t> {private int max; 개인 t [] ary; 개인 int 전선; // 팀장은 데이터 항목의 위치를 개인 int 후면에서 가져 오는 위치를 나타냅니다. // 팀의 꼬리는 데이터 항목의 위치가 삽입되는 위치를 나타냅니다. // 실제 데이터 항목 수 공개 Queueq (int size) {this.max = size; ary = (t []) 새 개체 [max]; 전면 = 0; 후면 = -1; nitems = 0; } // 대기열의 꼬리를 삽입 공용 void insert (t t) {if (rear == max -1) {// 실제 대기열의 끝에 도달했습니다. 시작부터 시작, 후면 = -1; } ary [++ 후면] = t; nitems ++; } // 팀의 헤드를 제거하여 public t remove () {t temp = ary [front ++]; if (front == max) {// 큐가 끝에 도달하고 처음부터 시작하고 처음부터 시작하고 처음부터 시작하고 시작, 0에서 시작하십시오. } nitems-; 반환 온도; } // 팀의 헤드보기 public t peek () {return ary [front]; } public boolean isempty () {return nitems == 0; } public boolean isfull () {return nitems == max; } public int size () {return nitems; } public static void main (String [] args) {queueq <integer> queue = new Queueq <integer> (3); for (int i = 0; i <5; i ++) {queue.insert (i); System.out.println ( "size :" + queue.size ()); } for (int i = 0; i <5; i ++) {integer peek = queue.peek (); System.out.println ( "Peek :" + Peek); System.out.println ( "size :" + queue.size ()); } for (int i = 0; i <5; i ++) {Integer remove = queue.remove (); System.out.println ( "제거 :" + 제거); System.out.println ( "size :" + queue.size ()); } system.out.println ( "----"); for (int i = 5; i> 0; i-) {queue.insert (i); System.out.println ( "size :" + queue.size ()); } for (int i = 5; i> 0; i-) {integer peek = queue.peek (); System.out.println ( "Peek :" + Peek); System.out.println ( "size :" + queue.size ()); } for (int i = 5; i> 0; i-) {integer remove = queue.remove (); System.out.println ( "제거 :" + 제거); System.out.println ( "size :" + queue.size ()); }}} /** 이중 엔드 큐 <span style = "white-space : pre"> </span> 양쪽 끝에서 삽입 및 삭제*/public class queueqt <t> {private linkedlist <t> 목록; public queueqt () {list = new LinkedList <t> (); } // 큐 헤드 삽입 공용 void insertleft (t t) {list.addfirst (t); } // 대기열 테일 삽입 공용 void InserTright (t t) {list.addlast (t); } // 큐 헤드를 제거하여 public t removeleft () {return list.removefirst (); } // 팀의 끝을 제거 public t removeright () {return list.removelast (); } // 팀의 헤드보기 public t peekleft () {return list.getfirst (); } // 팀의 끝보기 public t peekright () {return list.getLast (); } public boolean isempty () {return list.isempty (); } public int size () {return list.size (); }} /** 우선 순위 대기열은 우선 순위별로 정렬되며 주문한 큐*/ public class queueqp {private int max; 개인 int [] ary; 개인 intems; // 실제 데이터 항목 수 공개 queueqp (int size) {this.max = size; ary = new int [max]; nitems = 0; } // 큐의 끝을 삽입 공용 공개 void insert (int t) {int j; if (nitems == 0) {ary [nitems ++] = t; } else {for (j = nitems-1; j> = 0; j-) {if (t> ary [j]) {ary [j + 1] = ary [j]; // 다음을 다음에 할당하는 것은 삽입 정렬을 사용하는 것과 동일합니다. 주어진 시퀀스는 원래 순서대로 정렬되므로 효율 O (n)} else {break; }} ary [j + 1] = t; nitems ++; } system.out.println (arrays.tostring (ary)); } // 팀의 헤드를 제거하여 public int remove () {return ary [-nitems]; // 작은 우선 순위를 제거} // 팀의 가장 낮은 우선 순위를 봅니다. public int peekmin () {return ary [nitems -1]; } public boolean isempty () {return nitems == 0; } public boolean isfull () {return nitems == max; } public int size () {return nitems; } public static void main (String [] args) {queueqp queue = new QueueQp (3); queue.insert (1); queue.insert (2); queue.insert (3); int remove = queue.remove (); System.out.println ( "제거 :" + 제거); }}