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

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

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Queue 큐, array로 구현하기 (java)  (0) 2020.01.05
[Data Structure] Stack 스택, array 로 구현하기 (java)  (0) 2020.01.05
[Data Structure] HashSet, LinkedHashSet, TreeSet  (0) 2019.12.22
[Data Structure] ArrayList, LinkedList, Vector  (0) 2019.12.20
[Data Structure] HashMap, HashTable, LinkedHashMap, TreeMap  (0) 2019.12.20

Queue

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

일상생활에서 Queue와 가장 밀접한 예로 줄을 서는 행위를 들 수 있다. 

보통 줄을 설 때 줄을 가장 먼저 선 사람이 가장 먼저 처리되므로 Queue와 같다.(Queue 라는 단어 자체가 줄을 서다 라는 뜻을 갖는 동사, 대기줄이라는 뜻을 갖는 명사 이다)

 

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

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
package algo_datastructure.queue.queuebyarray;
 
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class Main {
    public static void main(String[] args) {
        
        System.out.println("Queue---------");
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(1);
        q.add(2);
        System.out.println(q.peek());
        while(!q.isEmpty()) {
            System.out.print(q.poll() + " ");
        }
        
        System.out.println("\nPriorityQueue (default : ascending)---------");
        Queue<Integer> q2 = new PriorityQueue<Integer>();
        q2.add(1);
        q2.add(3);
        q2.add(2);
        System.out.println(q2.peek());
        while(!q2.isEmpty()) {
            System.out.print(q2.poll() + " ");
        }
        
        System.out.println("\nPriorityQueue (Descending)---------");
        Queue<Integer> q3 = new PriorityQueue<Integer>((o1, o2)->o2-o1);
        q3.add(1);
        q3.add(3);
        q3.add(2);
        System.out.println(q3.peek());
        while(!q3.isEmpty()) {
            System.out.print(q3.poll() + " ");
        }
    }
}
 
 cs

[실행결과]

Queue---------
1
1 2
PriorityQueue (default : ascending)---------
1
1 2 3
PriorityQueue (Descending)---------
3
3 2 1

Queue 는 입력된 순서대로 저장 및 출력되는(LinkedList 를 구현체로 사용) Queue 와

입력된 데이터들을 특정 기준에 의해 정렬된 상태로 저장 및 출력하는 PriorityQueue 가 있다.

위와 같이 PriorityQueue는 Comparator 인터페이스를 파라미터로 넘겨 정렬순서를 원하는대로 선택할 수 있다. (위 예제에선 람다로 처리)

Comparator 인터페이스를 넘겨주지 않을 경우, 오름차순 정렬(default)로 처리된다.

 

두가지 queue 모두 공통적으로 아래와 같은 메소드를 갖는다.

add() : queue 에 값을 넣는다. (값 넣기 실패시 exception 을 뱉는다)

offer() : add()와 같이 queue에 값을 넣는다. (값 넣기 실패시 false 를 리턴한다)

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

poll() : queue 내에서 가장 앞에 위치한 데이터를 꺼낸다.(데이터를 꺼내고 지운다)

 

[Array로 구현한 Queue]

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
package algo_datastructure.queue.queuebyarray;
 
public class Queue {
    
    private int[] array = new int[100];
int lastIdx = 0;
    
    public void add(int input) {
        array[lastIdx] = input;
        lastIdx++;
    }
    
    public int peek() {
        return array[0];
    }
    
    public int poll() {
        int rs = array[0];
        
        for(int i=1; i<=lastIdx; i++) {
            array[i-1] = array[i];
        }
        lastIdx--;
        
        return rs;
    }
    
    public boolean isEmpty() {
        return lastIdx==0?true:false;
    }
}
 
 cs

[사용]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package algo_datastructure.queue.queuebyarray;
 
public class Main {
    public static void main(String[] args) {
        
        Queue q = new Queue();
        q.add(1);
        q.add(2);
        q.add(3);
        System.out.println(q.peek());
        while(!q.isEmpty()) {
            System.out.print(q.poll() + " ");
        }
    }
}
 
 cs

 

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Stack 두 개로 Queue 구현하기  (0) 2020.01.06
[Data Structure] Stack 스택, array 로 구현하기 (java)  (0) 2020.01.05
[Data Structure] HashSet, LinkedHashSet, TreeSet  (0) 2019.12.22
[Data Structure] ArrayList, LinkedList, Vector  (0) 2019.12.20
[Data Structure] HashMap, HashTable, LinkedHashMap, TreeMap  (0) 2019.12.20

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

 

 

반응형
저작자표시 비영리

'Computer Science > data structure' 카테고리의 다른 글

[Data Structure] Stack 두 개로 Queue 구현하기  (0) 2020.01.06
[Data Structure] Queue 큐, array로 구현하기 (java)  (0) 2020.01.05
[Data Structure] HashSet, LinkedHashSet, TreeSet  (0) 2019.12.22
[Data Structure] ArrayList, LinkedList, Vector  (0) 2019.12.20
[Data Structure] HashMap, HashTable, LinkedHashMap, TreeMap  (0) 2019.12.20

+ Recent posts

티스토리툴바