반복 된 vaules을 제거합니다 _stack & array

Question

사용자가 입력 한 정수를 받아들이는 배열 기반 스택을 구현하는 프로그램을 작성하고 싶습니다. 프로그램은 사용자가 주어진 값의 발생을 식별하고 스택, (자바 프로그래밍 언어 사용).

나는 당신의 도움 (가치 방법 제거)을 예를 들어 써주세요. 입력 6 2 3 4 3 8 출력 : 6 2 4 8

Answer 1

Collection.contains가 고려 (가능한 Arrays.asList과 함께, 그렇게 불행 인 경우), HashMap 또는 Set.

정말 당신이 가지고있는 것, 실제로 가고있는 곳, 숙제/교사가 요구하는 어리석은 제한에 달려 있습니다. "배열 기반 스택 구현하기"라고 말하면서 바보 같은 위임이 있다고 가정하고 있는데, 사용자 정의 arrayContains 헬퍼 메소드를 작성하거나 보조 데이터 구조 (해시/세트)를 사용하여 추적 할 것을 고려합니다. '본'. 당신은 위의 asList /를 사용할 수 있습니다 * 당신은 "없는 괜찮다면

function addItem (i) begin 
    if not contains(stack, i) then 
     push(stack, i) 
    end if 
end 

포함 : 당신이 삽입시 체크를 할 경우

는, 그것은 당신의 가정 작업 :-) 단지 (메타 코드의 것 매우 효율적 "이지만 Java는 Arrays에 대한 지원이 거의 없으므로 헬퍼에 대한 권장 사항은 헬퍼에 대한 권장 사항이며 배열에 대한 루프는 값이 발견되면 true를 반환하고 그렇지 않으면 false를 반환합니다. (또는 아마도 인덱스가 발견 반환 -1 ...은 "노 중복"로직 스택 자체의 한 부분이라고 가정

Answer 2

:-) 코드, 나는 다음을 수행합니다 :

을 이 방법은 어레이를 스캔해야하며,이 아이템을 찾으면 거꾸로 모든 후속 항목이 하나의 위치를 ​​이동하여 배열을 축소한다

private boolean remove(int item) 

1) 헬퍼 메소드를 구현한다. 반환 값은 제거가 수행되었는지 여부를 나타냅니다. 내 솔루션은 어레이에 충분한 공간이 항상 있다고 가정

public void push(int item) { 
    if (!remove(item)) { 
     arr[topPos++] = item; 
    } 
} 

참고 :

2) 지금은 푸시 방법을 쉽게 구현할 수있다. 적절한 구현은 필요한 경우 배열의 크기를 조정해야합니다.

Answer 3

이 질문은 스택 제약을 강요하기 위해 스택의 정신을 깨뜨리는 흥미로운 (또는 문제가있는) 질문입니다. 순수 스택은 최상위 요소에 대해서만 쿼리 할 수 ​​있습니다.

결과적으로이 작업을 수행하려면 스택을 스택이 아닌 다른 데이터 구조로 처리해야하거나 스택의 모든 데이터를 다른 중간 데이터 구조로 최소한 전송해야합니다.

스택 클래스 자체에서이 작업을 수행하려면 다른 사용자의 응답이 유용 할 것입니다.당신은 스택 인터페이스 (푸시()와 팝())의 전통적인 방법을 사용하여 스택의 외부에서이 작업을 수행하려면

, 알고리즘은 다음과 같이 보일 수 있습니다

1. 만들기 지금까지 만난 값을 추적하는 정수 세트.
2. 일시적으로 값을 보관할 두 번째 스택을 만듭니다.
3. 스택이 비어 있지 않은 동안
   1. 맨 위 요소를 팝핑하십시오.
   2. 집합에 아직 해당 요소가 포함되어 있지 않으면 집합에 추가하고 두 번째 스택으로 밀어 넣습니다.
   3. 세트에 요소가 포함되어 있으면 이미 해당 요소를 발견 했으므로이 요소가 중복되었음을 의미합니다. 그러니 무시하십시오.
4. 두 번째 스택이 비어 있지 않은 반면,
   1. 팝 오프 최상위 요소
   2. 밀어 원래 스택에 요소입니다.

는이 작업을 수행하는 다양한 방법이 있습니다,하지만 난 모든 스택 아닌 일부 보조 데이터 구조를 필요로 생각합니다.

Answer 4

재정의 푸시 방식과는 값이 이미 존재하는지 여부를 확인하기 위해 스택을 통해 실행해야합니다. 그렇다면 true를 반환하고 그렇지 않으면 true를 반환합니다 (반환 값을 부울 값으로 사용하려는 경우).

기본적으로,이 씨 슈나이더에 의해 게시 대답의 정신에 있지만 배열을 축소하거나 전혀 스택을 수정 왜 그냥 새 항목이 중복인지 여부를 판단 할 수 있는지? 중복 된 경우 추가하지 않고 배열을 수정할 필요가 없습니다. 내가 놓친 게 있니?