배열, 링크 된 목록, 해시 테이블, 빨간색과 검은 나무 (이진 쿼리 트리)를 포함하여 여러 데이터 구조에 노출되었습니다. 오늘은 다른 데이터 구조 인 스택을 살펴 보겠습니다.
스택이란 무엇입니까? 먼저 예를 살펴 보겠습니다. 스택은 매우 좁은 목재 통에 해당합니다. 우리가 나무 배럴에 물건을 넣고 물건을 꺼낼 때, 우리는 처음에 바닥에 놓은 것이 우리가 방금 넣은 것이 첫 번째 일은 방금 넣은 것임을 알게 될 것입니다. 따라서 스택은 처음으로 안팎으로 (첫 번째로, 또는 나중에 처음으로) 컨테이너입니다. 그것은 입에 하나만 있고,이 입에 요소를 넣고,이 입에서 요소를 꺼냅니다. 그런 다음 다음 JDK에서 스택을 배우자.
1. 벡터 및 스택의 기본 소개 및 사용
먼저 JDK의 정의를 살펴 보겠습니다.
공개 클래스 스택 <e> vector <e> {위에서부터 스택이 벡터에서 상속되어 있음을 알 수 있으므로 벡터에 대한 특정 이해도 있어야합니다.
벡터 : 스레드 안전 동적 배열
스택 : 동적 배열을 기반으로 구현 된 스레드 안전 스택 인 벡터 상속;
1. 벡터 및 스택의 특징 :
벡터 및 Arraylist는 기본적으로 동일합니다. 차이점은 벡터가 스레드 안전하고 가능한 스레드-안전 메소드 전에 동기화 된 키워드를 추가한다는 것입니다.
벡터 : 빠른 임의의 액세스 속도, 열악한 삽입 및 제거 성능 (배열 특성); 널 요소를 지원합니다. 명령이있다; 요소를 반복 할 수 있습니다. 스레드-안전;
스택 : 첫 번째, 첫 번째는 일부 기본 스택 작업 방법을 구현합니다 (실제로는 벡터에서 상속되어 많은 작업이있을 수 있으며 어떤 의미에서는 스택이 아닙니다);
2. 벡터 및 스택 구조 :
벡터 클래스
기본적으로 ArrayList와 동일하며 나머지 주요 차이점은 다음과 같습니다.
1. 벡터는 스레드 안전입니다
2. 어레이리스트 성장은 벡터 성장과 일치하지 않습니다
건설 방법이 일관되지 않으면 벡터는 시공 방법을 통해 용량 인출을 초기화 할 수 있으며 인덱스의 방법과 같은 다른 방법이 있습니다. 벡터는 지정된 위치에서 검색 및 검색을 지원합니다. 또한 벡터는 부가 및 세트 멘탈 테 방법과 같은 중복 함수를 갖는 중복 방법을 갖는다. 그 이유는 역사적 이유 때문입니다. 예를 들어, AddElement 메소드는 이전에 남겨 둡니다. 컬렉션 프레임 워크가 소개되면 벡터는 컬렉션 패밀리에 가입하여 목록 인터페이스를 구현하도록 변경했습니다. 목록 인터페이스에 정의 된 일부 방법은 구현되어야합니다. 그러나 호환성의 이유로 이전 방법을 삭제할 수 없으므로 중복성이있는 오래된 방법이 나타납니다. 이제 ArrayList로 대체되었으며 기본적으로 거의 사용되지 않으므로 이해하십시오.
스택 클래스
스택의 기본 작동이 실현됩니다. 이 방법은 다음과 같습니다.
공개 스택 ();
빈 스택을 만듭니다
public synchronized e peek ();
스택 상단의 값을 반환합니다.
공개 E 푸시 (E 항목);
스택 작동;
public synchronized e pop ();
아웃 스택 작업;
공개 부울 빈 ();
스택이 비어 있는지 확인하십시오.
공개 동기화 된 int 검색 (Object O);
스택에서 물체의 위치를 반환합니다.
위의 스택의 경우 기본적으로 위의 방법 만 자주 사용합니다. 벡터를 물려 받고 많은 방법이 있지만 기본적으로 사용되지는 않지만 스택으로 처리됩니다.
3. 기본 사용
벡터의 일부 방법은 다음과 같이 사용됩니다. 또한, 벡터의 트래버스 방법은 ArrayList와 동일합니다. Foreach, Ierator 및 루프 트래버스에 사용할 수 있습니다.
import java.util.arrays; import java.util.iterator; import java.util.list; import java.util.listiterator; import java.util.vector; public class test {public static void main (string [] args) {vector <integer> vector = new Vector> (); for (int i = 0; i <10; i ++) {vector.add (i); } // print system.out.println (vector.toString ()); // size () system.out.println (vector.size ()); // system.out.println을 포함합니다 (vector.contains (2)); // iterator iterator <integer> iterator = vector.iterator (); while (iterator.hasnext ()) {system.out.print (iterator.next () + ""); } // toArray 객체 [] objarr = vector.toArray (); System.out.println ( "/nobjarr :" + arrays.aslist (objarr)); integer [] intarr = vector.toArray (new Integer [vector.size ()]); System.out.println ( "intarr :" + arrays.aslist (intarr)); // vector.add (5)를 추가합니다. // vector.remove (5)를 제거합니다. System.out.println (벡터); // 포함 된 System.out.println (vector.containsall (Arrays.aslist (5,6))); // addall vector.addall (arrays.aslist (555,666)); System.out.println (벡터); // removeall vector.removeall (arrays.aslist (555,666)); System.out.println (벡터); // addall method vector.addall (5, arrays.aslist (666,666, 6)); System.out.println (벡터); // 메소드 System.out.println을 얻습니다 (vector.get (5)); // 메소드 벡터 세트 세트 (5, 55); System.out.println (vector.get (5)); // method vector.add (0, 555) 추가; System.out.println (벡터); // 메소드 벡터를 제거합니다 .remove (0); System.out.println (벡터); // method system.out.println (vector.indexof (6)); // lastIndexof 메소드 System.out.println (vector.lastIndexof (6)); // ListIterator Method Listiterator <integer> listiterator = vector.listiterator (); System.out.println (listiterator.hasprevious ()); // ListIterator (index) 메소드 ListIterator <integer> ilistiterator = vector.listiterator (5); System.out.println (ilistiterator.previous ()); // Subrist Method.out.println (vector.sublist (5, 7)); // clear vector.clear (); System.out.println (벡터); }}스택의 일부 방법은 다음과 같이 사용됩니다. 스택은 벡터를 상속하기 때문에 스택은 벡터가 사용할 수있는 메소드를 사용할 수도 있습니다. 다음은 Stack의 고유 한 방법에 대한 몇 가지 예를 나열합니다. 매우 간단하며 스택의 기본 작업입니다. 벡터의 여러 트래버스 방법 외에도 스택은 고유 한 트래버스 방법 (빈 방법과 POP 방법을 사용하여 스택의 상단에서 바닥까지 트래버살을 달성)을 갖습니다.
import java.util.stack; public class test {public static void main (String [] args) {stack <integer> stack = new Stack <integer> (); for (int i = 0; i <10; i ++) {stack.add (i); } system.out.println (스택); System.out.println (stack.peek ()); stack.push (555); System.out.println (스택); System.out.println (stack.pop ()); System.out.println (스택); System.out.println (stack.empty ()); System.out.println (stack.search (6)); System.out.println ( "스택 트래버스 :"); while (! stack.empty ()) {system.out.print (stack.pop () + ""); }}}일부:
벡터는 스레드 안전하지만 성능이 좋지 않습니다. 일반적으로 특별한 요구 사항이없는 한 ArrayList가 사용됩니다.
스택을 스택으로 사용하려는 경우 스택의 여러 작동을 정직하고 엄격하게 따라야합니다. 그렇지 않으면 스택을 사용하는 것이 의미가 있으며 벡터를 사용하는 것이 좋습니다.
2. Vector & Stacke의 구조 및 기초 스토리지
Public Class vector <e>는 AbstractList를 확장합니다 <e>는 목록 <e>, randomaccess, clonable, java.io.serializable을 구현합니다
벡터는 구현 클래스 목록입니다. 실제로 벡터는 배열 구현을 기반으로 한 목록 컨테이너입니다. 기능 및 구현 코드는 기본적으로 ArrayList와 동일합니다. 그렇다면 다른 것은 무엇입니까? 하나는 배열이 확장되면 벡터가 *2이고 배열 목록은 *1.5+1이라는 것입니다. 다른 하나는 벡터가 스레드 안전하고 ArrayList는 그렇지 않다는 것입니다. 벡터의 스레드 안전 접근 방식은 각 방법에 동기화 된 키워드를 추가하여이를 확인하는 것입니다. 그러나 여기서 벡터는 더 이상 공식적으로 (모든 사람이 인정 함) 권장되지 않습니다. 스레드 안전 방법이 전체 방법을 잠그는 것이므로 효율성이 낮기 때문입니다. 더 나은 솔루션이 있습니까? 사실, 하나는 있다고 말할 수는 없지만 실제로는 collections.synchronizedList ()가 있습니다.
스택이 상속되고 벡터를 기반으로하므로 벡터의 일부 정의 및 메소드 소스 코드를 살펴 보겠습니다.
// 기본 레이어는 배열을 사용하여 데이터 보호 된 객체 [] ElementData를 저장합니다. // 요소 수를 보호 int ElementCount; // 컨테이너 확장 및 증분 크기 보호 된 int ApactionIncrement를 사용자 정의합니다. public 벡터 (int initialcapacity, int papactincrement) {super (); // 종료 한 바운드 (InitialCapacity <0)가 새로운 불법 행위 exception을 던지는 지 확인하십시오 ( "불법 용량 :" + initialcapacity); // 배열을 초기화 this.elementData = 새 개체 [초기 Capacity]; this.capacityIncrement = AppartionIncrement; } // 동기화 된 키워드 잠금 메소드를 사용하여 하나의 스레드만이 메소드를 동시에 조작 할 수 있는지 확인하십시오. // 확대 점검 EnseRecApacityHelper (ElementCount + 1); ElementData [ElementCount ++] = e; 진실을 반환하십시오. } private void ensurecapicationyHelper (int mincapacity) {// 현재 요소 int oldcapacity = elementData .length; // (minCapacity> OldCapacity) {Object [] OldData = ElementData; // 컨테이너 확장이 사용자 정의 된 경우 용량에 따라 용량을 확장하십시오. 그렇지 않으면 용량을 두 번 확장하십시오 (*2) int newCapacity = (ApactionIncrement> 0)? (OldCapacity + AppartionIncrement) : (OldCapacity * 2); if (newCapacity <mincapacity) {newCapacity = mincapacity; } // 배열 복사 elementData = arrays.copyof (ElementData, newCapacity); }}벡터는 단순히 이것을 봅니다. 다른 스택 방법이 호출되지 않으면 분석되지 않습니다. 이해하지 못하면 ArrayList 소스 코드 분석을 확인할 수 있습니다.
3 주요 방법의 분석
1.peek () - 스택 상단에있는 물체 가져 오기
/ ** * 스택 상단에 객체를 가져 오지만 삭제하지 마십시오 */ public synchronized e peek () {// 현재 컨테이너 요소 int len = size (); // 요소가없는 경우 (LEN == 0) 새로운 emptyStackexception ()을 던지면 직접 예외를 던지십시오. // 배열의 마지막 요소를 검색하려면 ElementAT 메소드를 호출합니다 (마지막 요소는 스택의 상단에 있습니다) retock Elementat (len -1); } / *** 색인 인덱스에 따라이 위치에서 요소를 가져 오십시오.이 메소드는 벡터* / public synchronized e emectat (int index) {// 경계를 종료 if (index> = elementCount) {wash new arrayindExoutOfBoundSexception (index + "> =" + elementCount); } // 요소를 가져옵니다 (e) ElementData [index]; }2.pop () - 스택을 팝업 (스택에서 튀어 나와 스택 상단에있는 물체를 가져 와서 컨테이너에서 객체를 삭제하십시오.
/ *** 스택을 범블, 스택 상단의 객체를 가져 와서 삭제하십시오*/ public synchronized e pop () {// 스택 e obj 상단에있는 객체를 기록합니다. // 현재 컨테이너 요소 int len = size (); // peek () 메소드 obj = peek ()를 통해 스택 OBJ의 상단에있는 객체를 가져옵니다. // removeElement 메소드를 호출하여 스택 removeElementat (len -1)의 상단에있는 객체를 삭제합니다. // 스택 상단에있는 객체로 돌아갑니다. return obj; } / *** 인덱스 인덱스에 따라 요소를 삭제합니다* / public synchronized void remodementat (int index) {modcount ++; // 바운드를 종료합니다 if (index> = elementCount) {wrach new arrayindExoutOfBoundSexception (index + "> =" + elementCount); } else if (index <0) {새로운 arrayindExoutOfBoundSexception (index); } // 이동할 배열 요소의 수를 계산합니다 int j = ElementCount -Index -1; if (j> 0) {// 배열을 이동하려면 중간에 배열을 삭제하므로 후속 요소를 앞으로 이동하십시오 (여기서 이동하면 삭제와 해당 인덱스 위치 요소를 직접 덮어 씁니다) 시스템. ArrayCopy (ElementData, Index + 1, ElementData, Index, J); } // 마이너스 1 ElementCount--; // 컨테이너의 마지막 요소를 비워 지도록 설정했습니다 (요소가 삭제되었고 인덱스의 요소가 앞으로 이동하여 마지막 요소는 쓸모가 없었기 때문에) ElementData [elementCount] = null; / * GC가 작업을 수행하도록하려면 */}3.push (e item) - (스택에) 푸시하고 컨테이너에 물체를 추가하고 반환합니다.
/ ** * 컨테이너에 객체를 추가하고 return */ public e 푸시 (e item) {// addElement를 addElement (item)로 호출합니다. // 요소 반환 항목을 반환합니다. } /*** 컨테이너에 요소를 추가합니다. 이 방법은 벡터*/ public synchronized void addlement (e obj) {modcount ++; // 확대 점검 EnseRecApacityHelper (ElementCount + 1); // 객체를 배열에 넣습니다. 요소 수 +1 ElementData [ElementCount ++] = obj; }4. 검색 (Object O) - 컨테이너의 물체의 위치를 반환하고 스택의 상단은 1입니다.
/ ** * 컨테이너의 객체 위치를 반환하면 스택의 상단은 1 */ public synchronized int search (오브젝트 o) {// int i = lastIndexof (o)의 마지막 발생에서 배열에서 요소를 찾습니다. // 스택의 상단은 1을 계산하기 때문에 (i> = 0) {return size () -I; } 반환 -1; }5.Empty () - 컨테이너는 비어 있습니다
/ *** 컨테이너가 비어 있는지 확인*/ public boolean empty () {return size () == 0; }일부:
이 시점에서 스택 방법은 분석됩니다. 스택은 궁극적으로 배열을 기반으로하기 때문에 여전히 이해하기 쉽습니다 (Arraylist를 기반으로하기 때문에).
JDK의 스택 소스 코드가 분석되었지만 여기에서 논의해야합니다. 여기서 스택이 매우 이상하다는 것을 알지 못합니다.
(1) 배열에 따라 스택이 구현되는 이유는 무엇입니까?
우리는 모두 배열의 특성을 알고 있습니다. 첨자 (임의의 액세스)를 기반으로 쿼리에 편리하지만 메모리는 고정되어 있고 용량 확장 효율은 낮습니다. 스택이 링크 된 목록을 사용하기에 가장 적합한 것을 생각하기 쉽습니다.
(2) 스택 스택은 왜 벡터를 상속합니까?
상속은 스택 스택이 벡터 메소드를 상속함으로써 스택과 스택이 약간 부적절하다고 느끼게합니다. 벡터를 상속 해야하는 경우 합리적인 접근 방식은 무엇입니까? 스택은 벡터를 상속하지는 않지만 벡터 자체에 대한 참조 만있는 경우 집계가 맞습니까?
유일한 설명은 스택이 JDK1.0에 의해 생성되었다는 것입니다. 그 당시 JDK의 컨테이너에는 Arraylist, LinkedList 등과 같은 벡터 만 있지 않았으며 이미 벡터가 있고 스택 함수를 구현할 수 있으므로 수행합니다. . . 링크 된 목록이있는 스택을 구현하는 것이 이상적이므로 시도해 봅시다.
java.util.linkedList 가져 오기; 공개 클래스 LinkedStack <e> {private linkedlist <e> 링크; public linkedstack () {this.linked = new LinkedList <e> (); } public e 푸시 (E 항목) {this.linked .addfirst (항목); 반품 항목; } public e pop () {if (this.linked.isempty ()) {return null; } reture this.linked.removeFirst (); } public e peek () {if (this.linked.isempty ()) {return null; } reture this.linked.getFirst (); } public int search (e item) {int i = this.linked.indexof (항목); 반환 i + 1; } public boolean empty () {return this.linked.isempty (); }}LinkedList가 구현 한 스택은 여기에서 사용됩니다. LinkedList에 언급 된 바와 같이 LinkedList는 Deque 인터페이스를 구현하여 스택 (첫 번째 및 아웃) 및 큐 (첫 번째 및 아웃)로 사용할 수 있습니다.
4. 벡터와 Arraylist의 차이
목록 인터페이스에는 세 가지 구현 클래스, 즉 ArrayList, Vector 및 LinkedList가 있습니다. 목록은 여러 요소를 저장하고 요소의 순서를 유지할 수 있으며 요소를 반복 할 수 있습니다.
세 가지 구현 클래스 간의 관련 차이점은 다음과 같습니다.
1. ArrayList는 가장 일반적으로 사용되는 목록 구현 클래스로, 배열을 통해 내부적으로 구현되어 요소에 빠르게 무작위로 액세스 할 수 있습니다. 배열의 단점은 각 요소 사이에 간격이 없다는 것입니다. 배열 크기가 만족되지 않으면 스토리지 용량을 증가시켜야합니다. 이미 배열의 데이터가 새로운 저장 공간에 복사되었다고 말해야합니다. Arraylist의 중간 위치에서 요소를 삽입하거나 삭제할 때 배열을 복사, 이동 및 비용이 상대적으로 높습니다. 따라서 삽입 및 삭제에 적합하지 않은 임의의 조회 및 횡단에 적합합니다.
2. 벡터는 또한 배열을 통해 구현되며, 차이점은 스레드 동기화를 지원한다는 것입니다. 즉, 특정 순간에 하나의 스레드만이 여러 스레드가 동시에 쓰기로 인한 불일치를 피하기 위해 벡터를 작성할 수 있지만 동기화를 구현하는 데 많은 비용이 들기 때문에 액세스는 어레이리스트에 액세스하는 것보다 느리게됩니다.
3. LinkedList는 링크 된 목록 구조를 사용하여 데이터를 저장하는데, 이는 데이터의 동적 삽입 및 삭제에 매우 적합하며 임의의 액세스 및 트래버스 속도는 비교적 느립니다. 또한 목록 인터페이스에 정의되지 않은 메소드를 제공하며 테이블 헤더 및 테일 요소를 작동하는 데 특별히 사용되며 스택, 큐 및 양방향 대기열로 사용할 수 있습니다.
5. 대기열 대기열, 이중 엔드 큐 Deque에 대한 간단한 이해
1. 대기열
일반적인 대기열 작업을 지원하기 위해 새로운 java.util.queue 인터페이스가 Java5에 추가되었습니다. 이 인터페이스는 java.util.collection 인터페이스를 확장합니다.
공개 인터페이스 큐 <e>는 수집 <e>을 확장합니다
기본 수집 작업 외에도 대기열은 다른 인서트, 추출 및 점검 작업을 제공합니다.
각 방법에는 두 가지 형식이 있습니다. 하나는 예외를 던지고 (조작이 실패한 경우), 다른 하나는 특수 값 (작동에 따라 NULL 또는 FALSE)을 반환합니다.
대기열은 일반적으로 개별 요소를 FIFO (First in First Out)에 정렬합니다. 그러나 우선 순위 대기열과 Lifo 대기열 (또는 스택)은 예외입니다. 전자는 제공된 비교기 또는 요소의 자연 순서에 따라 요소를 분류하고, 후자는 Lifo의 요소를 분류합니다 (First in First Out).
FIFO 대기열에서는 큐 끝에 모든 새로운 요소가 삽입되고 큐 헤더에서 제거 요소가 제거됩니다.
큐를 사용할 때는 add () 및 remove () 수집 메소드를 피하려고 시도하지만 제안 ()을 사용하여 요소를 추가하고 poll ()을 사용하여 요소를 얻고 제거하십시오. 그들의 장점은 값을 반환하여 성공을 달성하는지 여부를 결정할 수 있다는 것입니다. Add () 및 remove () 메소드는 실패 할 때 예외가 발생합니다. 요소를 제거하지 않고 프론트 엔드를 사용하려면 요소 () 또는 peek () 메소드를 사용하십시오.
제안 메소드는 요소를 삽입 할 수 있습니다. 그렇지 않으면 False를 반환합니다. 이는 Collection.add 메소드와 다릅니다.이 메소드는 선택되지 않은 예외를 던져 요소를 추가하지 못할 수 있습니다.
remove () 및 poll () 메소드는 큐의 헤더를 제거하고 반환합니다. 대기열에서 제거되는 요소는 큐 분류 정책의 기능이며, 이는 다양한 구현에서 다릅니다. remove () 및 poll () 메소드는 큐가 비어있는 경우에만 다르게 행동합니다. remove () 메소드는 예외가 발생하는 반면 poll () 메소드는 NULL을 반환합니다.
요소 () 및 peek () 반환하지만 큐 헤더를 제거하지 마십시오.
일부 구현 (링크드리스트)은 널의 삽입을 금지하지 않지만 큐 구현은 일반적으로 널 요소의 삽입을 허용하지 않습니다. NULL을 허용하는 구현에서도 NULL은 큐에 삽입되어서는 안됩니다. NULL은 설문 조사 방법의 특수 반환 값으로 사용되므로 대기열에 요소가 포함되어 있지 않음을 나타냅니다.
LinkedList 클래스는 큐 인터페이스를 구현하므로 LinkedList를 큐로 사용할 수 있습니다.
Java.util.queue 가져 오기; java.util.linkedList 가져 오기; public class testqueue {public static void main (String [] args) {queue <string> queue = new LinkedList <string> (); queue.offer ( "Hello"); queue.offer ( "World!"); queue.offer ( "hello!"); System.out.println (queue.size ()); 문자열 str; while ((str = queue.poll ())! = null) {system.out.print (str); } system.out.println (); System.out.println (queue.size ()); }}2. Deque
공개 인터페이스 deque <e>는 큐 <e>을 확장합니다
양쪽 끝에서 요소의 삽입 및 제거를 지원하는 선형 컬렉션.
Deque라는 이름은 "Double Ended Queue"의 약어이며 일반적으로 "데크"로 읽습니다.
대부분의 Deque 구현은 포함 할 수있는 요소 수에 고정 된 제한이 없지만이 인터페이스는 용량 제한 큐 및 고정 크기 제한없이 듀얼 엔드 큐를 모두 지원합니다.
이 인터페이스는 이중 엔드 큐의 양쪽 끝에서 요소에 액세스하는 메소드를 정의합니다. 요소를 삽입, 제거 및 검사하는 방법을 제공합니다. 이 인터페이스는 큐 인터페이스 큐를 상속 받기 때문에 각 방법에 대한 두 가지 형태가 있습니다. 하나는 작업이 실패 할 때 예외를 던지고 다른 하나는 특수 값 (작동에 따라 null 또는 false)을 반환합니다.
에이. 이중 끝 큐를 대기열로 사용하면 FIFO (First-in, First-Out) 동작이 나타납니다. 이중 엔드 큐 끝에 요소를 추가하고 이중 엔드 큐의 시작 부분에서 요소를 제거하십시오. 큐 인터페이스에서 상속 된 메소드는 다음 표에 표시된 것처럼 Deque 방법과 완전히 동일합니다.
비. Lifo (First in First Out) 스택으로 사용됩니다. 이 인터페이스는 레거시 스택 클래스가 아닌 먼저 사용해야합니다. 이중 엔드 큐를 스택으로 사용하면 요소가 이중 엔드 큐의 시작 부분으로 밀려 들어 이중 엔드 큐의 시작 부분에서 팝업됩니다. 스택 방법은 다음 표에서 볼 수 있듯이 Deque 방법과 완전히 동일합니다.