[자료구조] 스택과 큐

CS/Data Structure

[자료구조] 스택과 큐

창문닦이 2020. 2. 2. 17:19

이전에 정리한 내용이 있지만, 책을 보며 예제 풀이를 진행하는 것이라 한 번 더 포스팅한다.

[4장. 스택과 큐]

1. 스택

스택이란?

스택은 데이터를 일시적으로 저장하기 위한 자료구조이다.
후입 선출 방식(LIFO)으로 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.
push : 스택에 데이터를 넣는 작업
pop : 스택에서 데이터를 꺼내는 작업
top : push와 pop을 하는 위치
bottom : 스택의 가장 아랫부분

스택 만들기

생성자 IntStack : 생성자는 스택 본체용 배열을 생성하는 등 준비작업을 수행한다. 생성시 스택은 비어있으므로 스택 포인터는 0을 가리킨다.
푸시 메소드 push : 스택에 데이터를 넣는 메소드이다. 스택이 가득차서 푸시할 수 없을 경우는 예외처리를 해준다. 포인터값이 잘못 입력되면 max를 초과할 수 있기 때문이다.
팝 메소드 pop : 스택 꼭대기에서 데이터를 제거하고 그 값을 반환하는 메소드이다. 스택이 비어있는 경우 예외를 던진다.
피크 메소드 peek : 스택에 꼭대기 있는 데이터를 몰래 엿보는 메소드이다.
검색 메소드 indexOf : 스택본체의 배열에 특정 데이턱 포함되어있는지, 포함되어 있다면 배열에 어디에 들어있는지를 조사하는 메소드이다. top부터 bottom으로 선형 검색을 수행한다. (꼭대기 쪽에서 스캔하는 이유는 먼저 pop이 되는 데이터를 찾기 위함이다.)
스택의 모든 요소 삭제 메소드 clear : 스택에 쌓여있는 모든 데이터를 삭제한다.
용량 확인 메소드 capacity : 스택의 용량을 확인한다.
데이터 수를 확인하는 메소드 size : 현재 스택에 쌓여있는 데이터 수를 반환한다.
스택이 비어있는지 검사하는 메소드 isEmpty : 비어있으면 true, 그렇지 않으면 false를 반환한다.
스택이 가득 찼는지 검사하는 메소드 isFull : 가득찼으면 true, 그렇지 않으면 false를 반환한다.
스택 안에있는 모든 데이터를 표시하는 메소드 dump : 스택에 쌓인 모든 데이터를 바닥에서 꼭대기 순으로 표시한다.

public class IntStack {

	private int max;	//스택용량
	private int ptr; 	//스택포인터
	private int[] stk;	//스택본체
	
	//실행 시 예외 : 스택이 비어있음
	public class EmptyIntStackException extends RuntimeException {
		public EmptyIntStackException() {
			
		}
	}
	
	//실행 시 예외 : 스택이 가득참
	public class OverflowIntStackException extends RuntimeException {
		public OverflowIntStackException () {
			
		}
	}
	
	//생성자
	public IntStack(int capacity) {
		ptr = 0;
		max = capacity;
		try {
			stk = new int[max];			// 스택 본체용 배열을 생성
		} catch (OutOfMemoryError e) {	// 생성할 수 없음
			max = 0;
		}
	}
	
	//스택에 x를 푸시
	public int push(int x) throws OverflowIntStackException {
		if (ptr >= max) {
			throw new OverflowIntStackException();
		}
		return stk[ptr++] = x;//스택 포인터 증가. 반환값은 푸시한 값
	}
	
	//스택에 데이터를 팝.(정상에 있는 데이터를 꺼냄)
	public int pop() throws EmptyIntStackException{
		if (ptr <= 0) {
			throw new EmptyIntStackException();//스택이 비어있음
		}
		return stk[--ptr];
	}
	
	//스택에 데이터를 피크(정상에 있는 데이터를 들여다봄)
	public int peek() throws EmptyIntStackException{
		if (ptr <= 0) {
			throw new EmptyIntStackException();//스택이 비어있음
		}
		return stk[ptr-1];//데이터의 입력이나 출력이 없으므로 스택 포인터는 변화없음
	}
	
	//스택에서 x를 찾아 인덱스(없으면 -1)를 반환
	public int indexOf(int x) {
		for(int i=ptr-1;i>=0;i--) { //top부터 선형검색
			if(stk[i] == x) {
				return i;//검색성공
			}
		}
		return -1;//검색실패
	}
	
	//스택을 비움
	public void clear() {
		ptr = 0;
	}
	
	//스택의 용량을 반환
	public int capacity() {
		return max;
	}
	
	//스택에 쌓여있는 데이터 수를 반환
	public int size() {
		return ptr;
	}
	
	//스택이 비어있는가?
	public boolean isEmpty() {
		return ptr <= 0;
	}
	
	//스택이 가득 찼는가?
	public boolean isFull() {
		return ptr >= max;
	}
	
	//스택안의 모든 데이터를 바닥 -> 꼭대기 순서로 출력
	public void dump() {
		if(ptr <= 0) {
			System.out.println("스택이 비어 있습니다.");
		} else {
			for(int i=0; i <ptr; i++) {
				System.out.print(stk[i]+" ");
			}
			System.out.println();
		}
	}
}

//int형 스택 사용 예시
public class IntStackTester {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		IntStack stack = new IntStack(64); //최대 64개를 푸시할 수 있는 스택
		
		
		while (true) {
			System.out.println("현재 데이터 수 : "+ stack.size() + "/" + stack.capacity());
			System.out.print("(1)push\t(2)pop\t(3)peek\t(4)dump\n");
			System.out.print("(5)indexOf\t(6)clear\t(7)isEmpty\t(8)isFull\t(9)quit :");
			int menu = sc.nextInt();
			if(menu == 0)
				break;
			
			int x;
			switch (menu) {
			
			case 1:
				System.out.print("입력데이터 : ");
				x = sc.nextInt();
				try {
					stack.push(x);
				} catch (IntStack.OverflowIntStackException e) {
					System.out.println("스택이 가득 찼습니다.");
				}
				break;
				
			case 2:
				try {
					x = stack.pop();
					System.out.println("pop 결과 데이터 : " + x);
				} catch (IntStack.EmptyIntStackException e) {
					System.out.println("스택이 비었습니다.");
				}
				break;
				
			case 3:
				try {
					x = stack.peek();
					System.out.println("peek 결과 데이터 : " + x);
				} catch (IntStack.EmptyIntStackException e) {
					System.out.println("스택이 비었습니다.");
				}			
				break;
				
			case 4:
				stack.dump();
				break;
				
			case 5:
				//indexOf
				System.out.print("입력데이터 : ");
				int search = sc.nextInt();
				x = stack.indexOf(search);
				if (x > 0) {
					System.out.printf("%d는 스택에 [idx:%d] 존재합니다.", search, x);
				}
				break;
			case 6:
				//clear
				stack.clear();
				break;
			case 7:
				//isEmpty
				System.out.println("스택은 "+ (stack.isEmpty()?"비었습니다":"비지 않았습니다."));
				break;
			case 8:
				//isFull
				System.out.println("스택은 "+ (stack.isFull()?"꽉 찼습니다":"꽉 차지 않았습니다."));
				break;
			default:
				break;
			}
		}
		sc.close();
	}
}

Generic stack 클래스 만들기

package com.doit.ds.chapter04;
/*
 * 연습문제Q2 Generic Stack 클래스 생성하기
 * */
public class Gstack<T extends Object> {

	private int max;	//스택용량
	private int ptr; 	//스택포인터
	private T[] stk;	//스택본체
	
	//생성자
	public Gstack (int capacity) {
		ptr = 0;
		max = capacity;
		try {
			stk = (T[])new Object[capacity];// 스택 본체용 배열을 생성
		} catch (OutOfMemoryError e) {		// 생성할 수 없음
			max = 0;
		}
	}
	
	//스택에 x를 푸시
	public T push(T x) throws Exception {
		if (ptr >= max) {
			throw new Exception();
		}
		return stk[ptr++] = x;//스택 포인터 증가. 반환값은 푸시한 값
	}
	
	//스택에 데이터를 팝.(정상에 있는 데이터를 꺼냄)
	public T pop() throws Exception{
		if (ptr <= 0) {
			throw new Exception();//스택이 비어있음
		}
		return stk[--ptr];
	}
	
	//스택에 데이터를 피크(정상에 있는 데이터를 들여다봄)
	public T peek() throws Exception{
		if (ptr <= 0) {
			throw new Exception();//스택이 비어있음
		}
		return stk[ptr-1];//데이터의 입력이나 출력이 없으므로 스택 포인터는 변화없음
	}
	
	//스택에서 x를 찾아 인덱스(없으면 -1)를 반환
	public int indexOf(T x) {
		for(int i=ptr-1;i>=0;i--) { //top부터 선형검색
			if(stk[i] == x) {
				return i;//검색성공
			}	
		}
		return -1;//검색실패
	}
	
	//스택을 비움
	public void clear() {
		ptr = 0;
	}
	
	//스택의 용량을 반환
	public int capacity() {
		return max;
	}
	
	//스택에 쌓여있는 데이터 수를 반환
	public int size() {
		return ptr;
	}
	
	//스택이 비어있는가?
	public boolean isEmpty() {
		return ptr <= 0;
	}
	
	//스택이 가득 찼는가?
	public boolean isFull() {
		return ptr >= max;
	}
	
	//스택안의 모든 데이터를 바닥 -> 꼭대기 순서로 출력
	public void dump() {
		if(ptr <= 0) {
			System.out.println("스택이 비어 있습니다.");
		} else {
			for(int i=0; i <ptr; i++) {
				System.out.print(stk[i]+" ");
			}
			System.out.println();
		}
	}
}

// TODO 연습문제 3 이후 풀이 예정

2. 큐

큐란?
- 큐도 스택과 마찬가지로 데이터를 일시적으로 저장하기 위한 자료구조이다.
- 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출방식(FIFO)이다.
- 예시 : 은행 창구 대기열, 마트 계산 대기열
- 인큐 Enqueue : 큐에 데이터를 넣는 작업
- 디큐 Dequeue : 큐에 데이터를 꺼내는 작업
- 프론트 front : 데이터를 꺼내는 족
- 리어 rear : 데이터를 넣는 쪽

배열로 큐 만들기
- 배열 요소를 앞쪽으로 옮기지 않는 큐를 구현하자. 이를 위해 사용하는 자료구조가 ring buffer이다.
- 논리적으로 어떤 요소가 첫번째 요소이고 어떤 요소가 마지막 요소인지 식별하기 위한 변수 : 프론트와 리어.
- 이 변수들의 의미하는 것은 배열의 물리적 요소의 순서가 아닌 논리적인 데이터의 순서이다.
- 프론트(front) : 맨 처음 요소의 인덱스
- 리어(rear) : 맨 끝 요소의 하나 뒤의 인덱스(다음 요소의 인큐할 위치를 미리 지정)
큐 클래스 만들기 IntQueue
- 큐로 사용할 배열 que : 인큐하는 데이터를 저장하기 위한 큐 본체를 참조하는 배열
- 큐의 최대 용량 max : 큐의 최대 용량을 저장하는 필드
- 프론트 front : 인큐하는 데이터 가운데 첫번째 요소의 인덱스를 저장하는 필드
- 리어 rear : 인큐한 데이터 가운데 맨 나중에 넣은 요소의 하나 뒤의 인덱스를 저장하는 필드
- 현재 데이터 수 num : 큐에 쌓아놓은 데이터 수를 나타내는 필드
- 생성자 intQueue : 큐 본체용 배열을 생성하는 준비 작업을 수행. 생성시 큐는 비어있으므로 데이터 수, 프론트, 리어 모두 0이다.
- 인큐 메소드 enque : 큐에 데이터를 인큐하는 메소드. 인큐에 성공하면 인큐한 값을 그대로 반환. 큐가 가득차서 인큐할 수 없으면 예외를 던진다.
- 디큐 메소드deque : 큐에서 데이터를 디큐하고 그 값을 반환하는 메소드. 큐가 비어있어 디큐할 수 없으면 예외 던진다.
- 피크 메소드peek : 맨 앞에 데이터(디큐에서 꺼낼 데이터)를 확인하는 메소드. 값을 조사하고 꺼내지는 않으므로 front,rear,num의 값이 변화하지 않는다. 비어있으면 예외를 던진다.
- 검색 메소드indexOf : 큐의 배열에서 특정 변수와 동일한 데이터가 있는 위치를 알아내는 메소드. front -> rear 쪽으로 선형검색을 처리한다. 스캔할때 idx를 (i+front)%max 로 계산한다.
- 모든 데이터 삭제 메소드 clear : 현재 큐의 모든 데이터를 삭제하는 메소드이다.
- 최대 용량 확인 메소드 capacity : 큐의 최대 용량을 반환하는 메소드이다.
- 데이터 수를 확인하는 메소드 size : 현재 큐의 데이터 수를 반환하는 메소드이다.
- 큐가 비어있는지 검사하는 메소드 isEmpty : 큐가 비어있는지 판단하는 메소드이다.
- 큐가 가득 찼는지 검사하는 메소드 isFull : 큐가 가득 찼는지 판단하는 메소드이다.
- 큐안에 있는 모든 데이터를 표시하는 메소드 dump : 큐에 인큐된 모든 데이터를 프론트에서 리어 순으로 출력하는 메소드
링 버퍼로 큐 만들기

연습문제 Q5~8 풀이 예정

링 버퍼의 활용

링 버퍼는 오래된 데이터를 버리는 용도로 사용가능하다.
정수 입력(인큐)은 무한히 가능하지만 저장되는 데이터는 가장 최근에 입력한 데이터요소 중 배열의 크기만큼 남아있다.

문제 출처는 Do it! 자료구조와 함께 배우는 알고리즘 입문 자바 편입니다.
연습문제 풀이는 직접 작성하였습니다. 잘못된 부분이 있다면 댓글 부탁드립니다.

'CS > Data Structure' 카테고리의 다른 글

[자료구조] B-트리 B+트리 B*트리 (0)	2021.09.15
[자료구조] 재귀 알고리즘 (0)	2020.02.10
[자료구조] 검색 (0)	2019.12.05
[자료구조] 기본 자료구조(배열, 클래스) (0)	2019.11.26
[자료구조] 알고리즘이란 (0)	2019.11.09

현재글[자료구조] 스택과 큐

창문을 열심히 닦아요

[자료구조] 스택과 큐

[4장. 스택과 큐]

1. 스택

2. 큐

'CS > Data Structure' 카테고리의 다른 글

'CS/Data Structure'의 다른글

티스토리툴바

[자료구조] 스택과 큐

[4장. 스택과 큐]

1. 스택

2. 큐

'CS > Data Structure' 카테고리의 다른 글

'CS/Data Structure'의 다른글

관련글

티스토리툴바