Stack 두 개(First In First Out)로 Queue(Last In First Out) 구현하기

 

스택 두 개를 다음과 같은 용도로 분리하여 사용.

inStack : 데이터를 저장

outStack : 데이터를 꺼낼 때 임시 버퍼로 사용

 

[Queue.class]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
package algo_datastructure.stack.queuebystack;
 
import java.util.Stack;
 
class Queue <T> {
    
    private Stack<T> inStack;
    private Stack<T> outStack;
    
    public Queue(){
        inStack = new Stack<T>();
    }
    
    public boolean add(T input) {
        return inStack.add(input);
    }
    
    public T poll() {
        if(!inStack.isEmpty()) {
            outStack = new Stack<T>();
        }
        while(!inStack.isEmpty()) {
            outStack.add(inStack.pop());
        }
        T topItem = outStack.pop();
        while(!outStack.isEmpty()) {
            inStack.add(outStack.pop());
        }
        return topItem;
    }
    
    public T peek() {
        if(!inStack.isEmpty()) {
            outStack = new Stack<T>();
        }
        while(!inStack.isEmpty()) {
            outStack.add(inStack.pop());
        }
        T topItem = outStack.peek();
        while(!outStack.isEmpty()) {
            inStack.add(outStack.pop());
        }
        return topItem;
    }
    
    public boolean isEmpty() {
        return inStack.isEmpty();
    }
    
}
 
cs

[poll() 메소드 설명]

1. 데이터 입력

add(1);

add(2);

add(3);

inStack
3
2
1

2. poll(); 호출

if(!inStack.isEmpty()) {
   outStack = new Stack();
}

inStack outStack
3  
2  
1  

while(!inStack.isEmpty()) {
   outStack.add(inStack.pop());
}

inStack outStack
  1
  2
  3

T topItem = outStack.pop();   //1

inStack outStack
   
  2
  3

while(!outStack.isEmpty()) {
   inStack.add(outStack.pop());
}

inStack outStack
   
3  
2  

 

[사용]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package algo_datastructure.stack.queuebystack;
 
public class Main {
 
    public static void main(String[] args) {
        
        Queue<Integer> q = new Queue<>();
        q.add(1);
        q.add(2);
        q.add(3);
        System.out.println("peek : "+q.peek());
        System.out.println("poll : "+q.poll());
        
        q.add(4);
        System.out.println("peek : "+q.peek());
        while(!q.isEmpty()) {
            System.out.println("poll : "+q.poll());
        }
        
    }
    
}
 
cs

[실행결과]

peek : 1
poll : 1
peek : 2
poll : 2
poll : 3
poll : 4

기술면접에서 단골 문제라고 하길래, 이렇게 구현하면 되지 않을까 하고 구현해보았습니다..

반응형

Stack

LIFO (Last In First Out : 후입선출) 형태를 갖는 자료구조.

임시로 자료를 저장하고 꺼내서 사용하는 임시 버퍼와 같다.

java 메모리구조에서 new 연산자로 생성된 인스턴스 등이 Stack 으로 관리된다.

 

일상생활에서 Stack과 가장 밀접한 예로 장독대를 들 수 있다.

김치를 넣고 꺼낼 때 가장 나중에 넣은 김치를 가장 먼저 꺼내야 하는 구조이므로 Stack과 같다.

 

[java.util.Stack 의 기본적인 사용예]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package algo_datastructure.stack;
 
import java.util.Stack;
 
public class BasicUsageOfStack {
    public static void main(String[] args) {
 
        Stack<Integer> s = new Stack<>();
        s.add(1);
        s.add(2);
        s.add(3);
 
        System.out.println(s.peek());
 
        while(!s.isEmpty()) {
            System.out.println(s.pop());;
        }
        
    }
}
 
cs

 

add로 stack에 값을 넣는다. (push와 같음)

peek으로 stack 내에서 가장 위에 위치한 데이터를 꺼낸다.(데이터는 그대로 둔다)

pop으로 stack 내에서 가장 위에 위치한 데이터를 꺼낸다.(데이터를 꺼내고 지운다)

 

 

[Array로 구현한 Stack]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package algo_datastructure.stack.stackbyarray;
 
public class Stack {
    private int[] array = new int[100];
    private int lastIdx = 0;
    
    public Stack () {
    }
    
    public void add(int input) {
        array[lastIdx] = input;
        lastIdx++;
    }
    
    public int pop() {
        lastIdx--;
        int top = array[lastIdx];
        array[lastIdx] = 0;
        
        return top;
    }
    
    public int peek() {
        return array[lastIdx-1];
    }
    
    public boolean isEmpty() {
        return lastIdx==0?true:false;
    }
}
 
cs

[사용]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package algo_datastructure.stack.stackbyarray;
 
public class Main {
    public static void main(String[] args) {
        Stack s = new Stack();
        s.add(1);
        s.add(2);
        s.add(3);
        System.out.println(s.peek());
        while(!s.isEmpty()) {
            System.out.println(s.pop());
        }
    }
}
 
cs

 

 

반응형

+ Recent posts