알고리즘1-3. 스택(Stack)

스택(Stack)

- 데이터를 일시적으로 저장하기 위해 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(LIFO)이다.

- java 프로그램에서 메서드를 호출하고 실행할 때, 프로그램 내부에서는 스택을 사용한다.

- 검색할 때 위에서부터 차례대로 내려오는데 인덱스르 구해서 위치를 알려준다. 중복된 데이터가 있으면 최근에 저장된 순서대로(위에서부터)

 

3. isEmpty : 스택 구조에서 데이터가 없는 상태 인지 (텅 빈) 확인

4. push : 스택 구조에서 데이터를 삽입

5. peek : 스택 구조에서 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환

6. search : 전달된 객체가 존재하는 위치의 인덱스를 반환 (최상단 - 맨 마지막에 저장된 데이터 위치 1부터 시작) 

7. pop : 해당 스택의 제일 상단에 있는(제일 마지막으로 저장된) 요소를 반환하고, 해당 요소를 스택에서 제거

8. clear : 스택에 저장된 데이터를 초기화 (삭제)

9. contains(1) : stack에 값(1)이 들어있으면 true (없으면 false)

 

---

1. stack의 push, pop, peek, print, search, empty, info, 메서드 구현한 뒤에 메서드 호출

 

1) main메서드가 포함된 IntStackMain 파일과 stack에 필요한 메서드들을 선언한 (main메서드가 없는) IntStack 파일 생성

2) IntStackMain에서 먼저 stack의 크기(int max)를 입력받고, IntStack의 객체 생성

3) IntStack에서 생성자를 생성하고, 지역변수를 만들어서 초기화

 

public class IntStackMain {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		System.out.print("stack의 크기입력 = ");
		int max = scan.nextInt();

		// 스택객체 생성
		IntStack stack = new IntStack(max);
    }
}

 

public class IntStack {
	int capacity; // 최대로 저장할 수 있는 객체의 수
	int stk[]; // 정수를 저장할 수 있는 배열을 생성
	int point; // stack의 채워진 값의 위치+1 point == index

	IntStack() {}

	IntStack(int max) {
		capacity = max; // 값을 저장할 수 있는 크기(최대 용량)
		point = 0;      // point는 그 다음의 인덱스를 가리킨다.
		stk = new int[max]; // max의 크기만큼의 배열 생성
	}

 

4)  IntStack에서 현재 메모리(스택)의 데이터의 개수를 리턴하는 메서드와  메모리(스택)의 크기를 리턴하는 메서드 생성

5)  IntStackMain에서 현재 스택의 데이터 개수와 스택의 크기를 출력하고, 메뉴를 표시한다. (사용자가 8번을 누르면 스택 종료)

 

// 데이터의 수를 리턴하는 메서드
public int getSize() {
	return point;
}

// 메모리크기를 리턴하는 메서드
public int getCapacity() {
	return capacity;
}

 

public class IntStackMain {

	public static void main(String[] args) {while (true) {
    
        while (true) {
		// 현재스택의 데이터 개수와 스택의 크기를 출력하고
		System.out.print("데이터의 수 -> " + stack.getSize());
		System.out.println(", 메모리크기 -> " + stack.getCapacity());

		// 메뉴표시: push, pop, peek, print, search, empty, stack정보표시, 종료
		System.out.println("[메뉴]1.push, 2.pop, 3.peek, 4.print 5.search, 6.empty, 7.info 8.terminate");
		int menu = scan.nextInt();
		
        if (menu == 8) break;
        }
    }
}

 

6) IntStack에서 push 메서드를 생성하고 IntStackMain에서 호출, 오버플로우 발생시 예외처리 클래스 생성해야함

 

// 스택에 데이터를 추가하는 메서드
public int push(int data) throws OverflowIntStackException { // 예외 선언을 push 메서드가 호출한 곳으로 던짐
	if (point >= capacity) {        // 현재 데이터가 담겨져있는 데이터가 최대크기보다 크면
		throw new OverflowIntStackException(); // 예외발생 시킨다.
	}
	return stk[point++] = data; // 데이터가 담긴 다음번 위치
}

// 오버플로우 발생시 예외처리 클래스
class OverflowIntStackException extends RuntimeException {
	public OverflowIntStackException() {};
}

 

public class IntStackMain {

	public static void main(String[] args) {
    
	switch (menu) {
		case 1:// 스택에 값을 추가한다.
			System.out.print("스택에 추가할 데이터: ");
			int data = scan.nextInt();
			try {
				int result = stack.push(data);
				System.out.println("스택에 담은 데이터: " + result);
			} catch (OverflowIntStackException ofse) {  // 메서드에서 예외 선언한 것을 예외처리
				System.out.println("스택이 가득 찼습니다.");
			}
			break;
          }
     }
}

 

7) IntStack에서 pop 메서드를 생성하고 IntStackMain에서 호출, 스택이 비어있을 시 예외처리 클래스 생성해야함

 

// 스택에 제일 나중에 저장된 위치(point-1)의 값을 리턴하는 메서드
public int pop() throws EmptyIntStackException {
	// 스택이 비어 있으면 empty 예외 발생시킴	
    if (point <= 0) {  // point가 비어있다 == -1 
		throw new EmptyIntStackException();  // 스택이 비어있을 때 예외발생!
	}
	return stk[--point];  // -1 감소 먼저
}

// 스택이 비어있을 때 발생시킬 예외 클래스
class EmptyIntStackException extends RuntimeException {
	public EmptyIntStackException()  {};
}

 

public class IntStackMain {

	public static void main(String[] args) {
		case 2: // 스택에서 값을 얻어온다.
			try {
				int result = stack.pop();
				System.out.println("스택에서 " + result + " pop하였습니다.");
			} catch (EmptyIntStackException e) {
				System.out.println("스택이 비어있습니다.");
			}
			break;
      }
}

 

8) IntStack에서 peek 메서드와 print 메서드를 생성하고 IntStackMain에서 호출

 

// 현재 제일 위(point-1)에 있는 데이터를 리턴한다.
public int peek() throws EmptyIntStackException {
	if(point <= 0) {
		throw new EmptyIntStackException();  // 스택이 비어있을 때 예외 발생!
	}
	return stk[point-1];
}

// stack의 모든 데이터 출력하기
public void print() {
	if(point<=0) {
		System.out.println("스택이 비어있습니다.");
	} else {
		for(int i=0; i<point; i++) {
			System.out.println("stk["+i+"]" + stk[i]);
		}
	}
}

 

public class IntStackMain {

	public static void main(String[] args) {
		case 3: // 스택에서 제일 위에 있는 데이터 가져오기
			try {
				int result = stack.peek();
				System.out.println("현재 제일 위의 값은 " + result + "입니다.");
			} catch (EmptyIntStackException e) {
				System.out.println("스택이 비어있습니다.");
			}
			break;
            
       	case 4: // 스택의 모든 데이터 출력
			stack.print();
			break;
        }
}

 

9) IntStack에서 indexOf 메서드를 생성하고 IntStackMain에서 호출

 

// 데이터의 index구하기 
public int indexOf(int search) {
	for(int i=point-1; i>=0; i--) { // point-1, point-2, point-3... 위에서부터 값 읽기
		if(stk[i]==search) {    // search 값과 같다면 인덱스 반환
			return i;
		}
	}
	return -1;    // seach 값을 못찾았으면 -1 반환
}

 

public class IntStackMain {

	public static void main(String[] args) {
		case 5: // 검색 : 값을 입력하면 값이 위치한 index 구하기
			System.out.print("검색할 데이터: ");
		
    	    int search = scan.nextInt();
			int idx = stack.indexOf(search);
            
			if (idx >= 0) {  (idx 값이 있다면 -1이 아닌 정수가 나올 것임!)
				System.out.println(search + "는 스택의 " + idx + "위치에 존재합니다.");
			} else {
				System.out.println(search + "는 스택에 없습니다.");
			}
			break;
  	  }
}

 

10) IntStack에서 isEmpty 메서드를 생성하고 IntStackMain에서 호출

 

// 스택에 데이터가 존재하는지 확인하는 메서드
public boolean isEmpty() {
	// 비어있으면 true, 데이터가 있으면 false;
//	return (point<=0)? true:false;  삼항연산자로
	return point<=0;
}

 

public class IntStackMain {

	public static void main(String[] args) {
	    case 6: // 스택이 비어있는지 확인
		if(stack.isEmpty()) {
			System.out.println("스택에 데이터가 없습니다.");
		} else {
			System.out.println("스택에 데이터가 있습니다.");
		}
		break;
  	  }
}

 

11) IntStack에서 isFull 메서드를 생성하고 IntStackMain에서 스택 정보 표시(스택의 크기, 갯수, 데이터 존재 유무, 데티어 full 유무)를 만들고 호출, 종료

 

// 스택이 가득찼는지 확인 
public boolean isFull() {
	return point >= capacity;
}

 

public class IntStackMain {

	public static void main(String[] args) {
	    case 7: // 스택 정보 표시
		System.out.println("스택의 크기: " + stack.getCapacity());// 스택의 크기
		System.out.println("스택의 갯수: " + stack.getSize());// 데이터 갯수
		System.out.println("데이터의 존재 유무: " + (stack.isEmpty()?"비어있음":"데이터있음"));// 비어있는지 확인
		System.out.println("데이터가 Full 유무: " + (stack.isFull()?"가득찼음":"가득차지 않았음"));    // 가득찼는지 확인
		break;
        
        System.out.println("프로그램이 종료되었습니다.");
		scan.close();
        
  	  }
}

 

 

<IntStackMain 전체 코드> 

 

package stack_queue;

import java.util.Scanner;

public class IntStackMain {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);

		System.out.print("stack의 크기입력 = ");
		int max = scan.nextInt();

		// 스택객체 생성
		IntStack stack = new IntStack(max);

		while (true) {
			// 현재스택의 데이터 개수와 스택의 크기를 출력하고
			System.out.print("데이터의 수 -> " + stack.getSize());
			System.out.println(", 메모리크기 -> " + stack.getCapacity());

			// 메뉴표시: push, pop, peek, print, search, empty, stack정보표시, 종료
			System.out.println("[메뉴]1.push, 2.pop, 3.peek, 4.print 5.search, 6.empty, 7.info 8.terminate");
			int menu = scan.nextInt();

			if (menu == 8) break;
			// 변수, 수식, 상수 -> 정수형, char, String
			
			switch (menu) {
			case 1:// 스택에 값을 추가한다.
				System.out.print("스택에 추가할 데이터: ");
				int data = scan.nextInt();
				try {
					int result = stack.push(data);
					System.out.println("스택에 담은 데이터: " + result);
				} catch (OverflowIntStackException ofse) {
					System.out.println("스택이 가득 찼습니다.");
				}
				break;
				
			case 2: // 스택에서 값을 얻어온다.
				try {
					int result = stack.pop();
					System.out.println("스택에서 " + result + " pop하였습니다.");
				} catch (EmptyIntStackException e) {
					System.out.println("스택이 비어있습니다.");
				}
				break;
				
			case 3: // 스택에서 제일 위에 있는 데이터 가져오기
				try {
					int result = stack.peek();
					System.out.println("현재 제일 위의 값은 " + result + "입니다.");
				} catch (EmptyIntStackException e) {
					System.out.println("스택이 비어있습니다.");
				}
				break;
				
			case 4: // 스택의 모든 데이터 출력
				stack.print();
				break;

			case 5: // 검색 : 값을 입력하면 값이 위치한 index 구하기
				System.out.print("검색할 데이터: ");
				int search = scan.nextInt();
				int idx = stack.indexOf(search);
				if (idx >= 0) {
					System.out.println(search + "는 스택의 " + idx + "위치에 존재합니다.");
				} else {
				System.out.println(search + "는 스택에 없습니다.");
				}
				break;
				
			case 6: // 스택이 비어있는지 확인
				if(stack.isEmpty()) {
					System.out.println("스택에 데이터가 없습니다.");
				} else {
					System.out.println("스택에 데이터가 있습니다.");
				}
				break;
				
			case 7: // 스택 정보 표시
				System.out.println("스택의 크기: " + stack.getCapacity());// 스택의 크기
				System.out.println("스택의 갯수: " + stack.getSize());// 데이터 갯수
				System.out.println("데이터의 존재 유무: " + (stack.isEmpty()?"비어있음":"데이터있음"));// 비어있는지 확인
				System.out.println("데이터가 Full 유무: " + (stack.isFull()?"가득찼음":"가득차지 않았음"));    // 가득찼는지 확인
				break;
			}
		}
		System.out.println("프로그램이 종료되었습니다.");
		scan.close();
	}
}

 

<IntStack 전체 코드>

 

package stack_queue;

public class IntStack {
	int capacity; // 최대로 저장할 수 있는 객체의 수
	int stk[]; // 정수를 저장할 수 있는 배열을 생성
	int point; // stack의 채워진 값의 위치+1 point == index

	IntStack() {}

	IntStack(int max) {
		capacity = max; // 값을 저장할 수 있는 크기 입력받은 크기를 capacity에 넣기
		point = 0;
		stk = new int[max];
	}

	// 데이터의 수를 리턴하는 메서드
	public int getSize() {
		return point;
	}

	// 메모리크기를 리턴하는 메서드
	public int getCapacity() {
		return capacity;
	}

	// 스택에 데이터를 추가하는 메서드
	public int push(int data) throws OverflowIntStackException {
		if (point >= capacity) { // 현재 데이터가 담겨져있는 데이터가 최대크기보다 크면
			throw new OverflowIntStackException(); // 예외발생 시켜줌
		}
		return stk[point++] = data; // 데이터가 담긴 다음번 위치
	}

	// 스택에 제일 나중에 저장된 위치(point-1)의 값을 리턴하는 메서드
		public int pop() throws EmptyIntStackException {
			// 스택이 비어 있으면 empty 예외 발생시킴
			if (point <= 0) {
				throw new EmptyIntStackException();
			}
			return stk[--point];  // -1 감소 먼저
		}
		
	// 제일 위(point-1)에 있는 데이터를 리턴한다.
		public int peek() throws EmptyIntStackException {
			if(point <= 0) {
				throw new EmptyIntStackException();
			}
			return stk[point-1];
		}
		
	// stack의 모든 데이터 출력하기
		public void print() {
			if(point<=0) {
				System.out.println("스택이 비어있습니다.");
			} else {
				for(int i=0; i<point; i++) {
					System.out.println("stk["+i+"]" + stk[i]);
				}
			}
		}
		
	// 데이터의 index구하기 
		public int indexOf(int search) {
			for(int i=point-1; i>=0; i--) { // point-1, point-2, point-3...
				if(stk[i]==search) {
					return i;
				}
			}
			return -1;
		}
		
	// 스택에 데이터가 존재하는지 확인하는 메서드
		public boolean isEmpty() {
			// 비어있으면 true, 데이터가 있으면 false;
//			return (point<=0)? true:false;
			return point<=0;
		}
		
	// 스택이 가득찼는지 확인 
		public boolean isFull() {
			return point >= capacity;
		}
		
		
		// 오버플로우 발생시 예외처리 클래스
		class OverflowIntStackException extends RuntimeException {
			public OverflowIntStackException() {};
		}
		
		// 스택이 비어있을 때 발생시킬 예외 클래스
		class EmptyIntStackException extends RuntimeException {
			public EmptyIntStackException()  {};
		}

	}

 

 

2021.12.04 - [소소한 CS 지식/CS50] - 5: 메모리-5(메모리 교환, 스택,힙)

5: 메모리-5(메모리 교환, 스택,힙)

2021.12.11 - [소소한 CS 지식/CS50] - 6: 자료구조-8(스택, 큐, 딕셔너리)

6: 자료구조-8(스택, 큐, 딕셔너리)

2022.01.10 - [멀티캠퍼스 풀스택 과정/Java의 정석] - 자바의 정석8-3 스택과 큐/Iterator, ListIterator, Enumeration

자바의 정석8-3 스택과 큐/Iterator, ListIterator, Enumeration