'Algorithm&DataStructures/Stack'에 해당되는 글 6건

스택(Stack) - 스택을 이용한 이진수변경(ConvertDecimalIntoBinary)

- 십 진수를 이진 수로 변경한다

1. DynamicStackImpl.class

class DynamicStackImp{ private int top; private int stackSize; private int[] stackArr; public DynamicStackImp(int size){ this.top = -1; this.stackSize = size; this.stackArr = new int[stackSize]; } public void push(int element){ if(this.isStackFull()){ System.out.println("Stack is full"); this.increaseCapacity(); } stackArr[++top] = element; } public int pop()throws Exception{ if(this.isStackEmpty()){ throw new Exception("Stack is empty"); } return stackArr[top--]; } public boolean isStackEmpty(){ return(top == -1); } public boolean isStackFull(){ return(top == stackSize -1); } public void increaseCapacity(){ int[] newArry = new int[stackSize * 2]; for(int i = 0; i<stackSize; i++){ newArry[i] = stackArr[i]; } System.out.println("Stack size is extended"); this.stackArr = newArry; this.stackSize = stackSize *2; } }

2. ConvertDecimalIntoBinary.class

1) converter()

public String converter(int element) throws Exception{ DynamicStackImp stack = new DynamicStackImp(5); StringBuilder add = new StringBuilder(); int remainder = 0; int quotient = element; boolean flag = true; while(flag){ remainder = quotient%2; quotient = quotient/2; stack.push(remainder); if(quotient == 0 || quotient == 1){ stack.push(quotient); flag = false; } } while(!stack.isStackEmpty()){ add.append(stack.pop()); } return add.toString(); }  

2) main()

public static void main(String[]args) throws Exception{ ConvertDecimalIntoBinary convert = new ConvertDecimalIntoBinary(); System.out.println(convert.converter(41)); }  

스택을 이용한 괄호 체크(delimiter matching)

- 스택을 이용하여 특정한 식의 괄호가 맞는지 체크한다

1. Stack.class

class StackImp{ private int top; private int stackSize; private char[] stackArr; public StackImp(int size){ this.top = -1; this.stackSize = size; this.stackArr = new char[stackSize]; } public void push(char element)throws Exception{ this.stackArr[++top] = element; } public char pop()throws Exception{ return this.stackArr[top--]; } public boolean isStackEmpty(){ return (top == -1); } public boolean isStackFull(){ return(top == stackSize -1); } }

2. DelimiterMatching .class

1) isDelimiterMatching()

public boolean isDelimiterMatching(String element) throws Exception{ int size = element.length(); StackImp stack = new StackImp(size); boolean flag = true; for(int i = 0; i<size; i++){ char target = element.charAt(i); switch(target){ case '(': case '[': case '{': stack.push(target); break; case ')': case ']': case '}': //괄호가 틀린지 맞는지 체크 if(!stack.isStackEmpty()){ char bb = stack.pop(); if((bb == '(' && target != ')')|| (bb == '{' && target != '}') || (bb == '[' && target != ']')){ flag = false; } }else{ //오른쪽에 괄호가 더 있는지 체크한다 flag = false; } break; default: break; } } //왼쪽에 괄호가 많은지 체크한다 if(!stack.isStackEmpty()){ flag = false; } return flag; }  

2) main()

public static void main(String[]args) throws Exception{ boolean result; DelimiterMatching aa = new DelimiterMatching(); result = aa.isDelimiterMatching("((a+b))-[a+b]"); System.out.println(result); }  

입력된 문자 뒤집기(Reverse a word)

- 입력된 문자를 스택을 이용해 뒤집어서 출력한다

1. Stack class

1) 변수 정의

private int top; private int stackSize; private char[] stackArr; public Stack(int size){ this.top = -1; this.stackSize = size; this.stackArr = new char[stackSize]; }

2) push(), isStackFull()

public void push(char element)throws Exception{ if(this.isStackFull()){ throw new Exception("Stack is full"); } this.stackArr[++top] = element; } public boolean isStackFull(){ return(top == stackSize -1); }  

3) pop(), isStackEmpty()

public char pop()throws Exception{ if(this.isStackEmpty()){ throw new Exception("Stack is empty"); } return stackArr[top--]; } public boolean isStackEmpty(){ return (top == -1); }  

2. Reverse class

1) reverseWord()

public String reverseWord(String word) throws Exception{ StringBuilder sb = new StringBuilder(); int size = word.length(); Stack st = new Stack(size); for(int i = 0; i<size; i++){ st.push(word.charAt(i)); } while(!st.isStackEmpty()){ sb.append(st.pop()); } return sb.toString(); }  

- Stringbuilder 사용

2) main()

public static void main(String[]args) throws Exception{ ReverseAword aaa=new ReverseAword(); Scanner word = new Scanner(System.in); String a = word.next(); System.out.println(a+">>>>>"+aaa.reverseWord(a)); word.close(); }  

- Scanner를 이용하여 입력받는다

스택(Stack) - 제네릭스택(Stack Using Generic)

- 제네릭을 이용하여 String, int 등 다양하게 받을 수 있다

1. 구현

1) 초기화

public class StackUsingGeneric <T extends Object>{ private int stackSize; private int top; private T[] stackArr; public StackUsingGeneric(int size){ this.stackSize = size; this.top = -1; this.stackArr = (T[]) new Object[stackSize]; }

- T 로 선언하여 객체 형태의 따라 받을 수 있게 한다

2) push(), isStackFull(), increaseCapacity()

public void push(T element){ if(this.isStackFull()){ System.out.println("Stack is full"); this.increaseCapacity(); } System.out.println("adding:"+element); this.stackArr[++top] = element; } public boolean isStackFull(){ return (this.stackSize -1 == top); } public void increaseCapacity(){ T[] newArr = (T[]) new Object[stackSize * 2]; for(int i = 0; i<stackSize; i++){ newArr[i] = stackArr[i]; } this.stackArr = newArr; this.stackSize = this.stackSize *2; }  

3) pop(), isStackEmpty(), peek()

public T pop()throws Exception{ if(this.isStackEmpty()){ throw new Exception("Stack is empty"); } System.out.println("removing:"+stackArr[top]); return stackArr[top--]; } public T peek(){ System.out.println("peeking:"+this.stackArr[top]); return this.stackArr[top]; }  

4) main()

public static void main(String[]args){ StackUsingGeneric<Integer> a1 = new StackUsingGeneric(2); try{ a1.push(1); a1.push(2); a1.peek(); a1.push(3); a1.pop(); }catch(Exception e){ System.out.print(e.getMessage()); } StackUsingGeneric<String> a2 = new StackUsingGeneric(2); try{ a2.push("a"); a2.push("b"); a2.peek(); a2.push("c"); a2.pop(); }catch(Exception e){ System.out.print(e.getMessage()); } }  

- 객체를 String, Integer 두개로 생성