[데이터 구조 와 알고리즘 01] 스 택

맨 앞 에 쓰 여 있다. 이른바 데이터 구조 란 한 그룹의 데이터 저장 방식, 요소 간 의 논리 관 계 를 통칭 하 는 것 이다.컴퓨터 의 물리 적 저장 방식 은 보통 배열 저장 과 링크 저장 으로 나 뉘 는데 요소 관 계 는 질서 있 고 무질서 하 게 나 뉜 다.실제 응용 수요 에 따라 우 리 는 저장 방식 과 요소 관 계 를 조합 하여 데이터 구 조 를 디자인 하여 우리 가 응용 하 는 수 요 를 만족시킨다.
정의: 데이터 저장 과 검색 을 위 한 선형 데이터 구조 만 접근 할 수 있 습 니 다.저장 방식 에 따라 순서 스 택 (배열 실현) 과 체인 스 택 (링크 실현) 으로 나 눌 수 있 습 니 다.
연산 제한: 후진 선 출.
기본 개념: 데이터 요소 가 없 는 스 택 을 빈 스 택 이 라 고 합 니 다.조작 데이터 의 한쪽 을 스 택 톱 이 라 고 합 니 다.
기본 연산:
                      1: 스 택 초기 화: 빈 스 택 을 만 듭 니 다.
                      2: 판 공.
                      3: 스 택 에 들 어가 기: 스 택 상단 지침 을 업데이트 하고 스 택 상단 데 이 터 를 추가 합 니 다.
                      4: 스 택 나 가기: 스 택 의 데 이 터 를 삭제 하고 스 택 의 포인터 업데이트.
                      5: 스 택 데이터 읽 기.
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------
순차 스 택 구현

public class SequenceStack implements Stack{
	private Integer[] array ;
	private int size ;
	private int top = -1 ;//    
	
	public SequenceStack(int size){
		this.size = size;
		this.array = new Integer[size];
	}
	
	@Override
	public boolean isEmpty() {
		return (top==-1);
	}
	
    //      ，    
	@Override
	public boolean isFull() {
		return (top==size-1);
	}
	
	//  
	@Override
	public void push(int value) throws Exception{
		if(isFull()) throw new ArrayIndexOutOfBoundsException(size);
		array[++top] = value ;
	}
	
	//         ，      
	@Override
	public Integer pop(){
		if(isEmpty()) return null;
		int a= array[top];
		array[top] = null;
		top--;
		return a ;
	}
	
	//      
	@Override
	public Integer top(){
		return isEmpty()?null:array[top];
	}
	
	@Override
	public String toString() {
		StringBuilder stringBuilder = new StringBuilder();
		for(Integer i : array){
			stringBuilder.append(i+",");
		}
		return stringBuilder.toString()
                .substring(0, stringBuilder.toString().length()-1);
	}
}

체인 스 택 구현

public class LinkStack implements Stack {
	
	private Link top;

	@Override
	public boolean isEmpty() {
		return (top==null);
	}

	@Override
	public boolean isFull() {
		return false;
	}

	@Override
	public void push(int value) throws Exception {
		Link newLink = new Link();
		newLink.data = value ;
		newLink.next = top ;
		top = newLink ;
	}

	@Override
	public Integer pop() {
		if(isEmpty()){
			return null;
		}
		Integer data = top.data;
		top = top.next;
		return data;
	}

	@Override
	public Integer top() {
		return isEmpty()?null:top.data;
	}

	static class Link{
		Integer data;
		Link next ;
	}
}

테스트 결과

public class Test {
	
	public static void main(String[] args) throws Exception {
		Stack sequenceStack = new SequenceStack(10);
		sequenceStack.push(999);
		System.out.println(sequenceStack);
		
		Stack linkstack = new LinkStack();
		System.out.println(linkstack.isEmpty());
		System.out.println(linkstack.pop());
		System.out.println(linkstack.top());
		linkstack.push(1);
		System.out.println(linkstack.pop());
		System.out.println(linkstack.top());
	}

}

999,null,null,null,null,null,null,null,null,null
true
null
null
1
null

일반적인 프로 그래 밍 응용 (java. util. Stack)
단어 역순 출력: 단 어 를 입력 하고 enter 후 알파벳 순서 가 뒤 바 뀐 단 어 를 표시 합 니 다.

public class StackForWordDesc {
	@SuppressWarnings("resource")
	public static void main(String[] args) {
		while (true) {
			//        
			System.out.println("   ：");
			Scanner scanner = new Scanner(System.in);
			String read = scanner.nextLine();
			
			Stack stack = new Stack<>();
			//             
			for(int i=0;i