[자료구조] 스택(Stack) / 큐(Queue)

스택(Stack)

■ 정의

- 데이터를 일시적으로 쌓아 놓는 자료구조
- 데이터의 입력과 출력 순서는 후입선출 (LIFO: Last In First Out)            

 

 

■ 메소드

Stack<Integer> s = new Stack<Integer>();
Stack<Integer> s = new Stack<Integer>(int capacity);                       // 스택의 capacity 결정

 

메소드	의미
push(int item)	스택에 데이터를 저장
pop()	스택의 꼭대기에 있는 데이터를 제거하고, 그 값을 반환
isFull()	스택이 empty 상태인지 확인
isEmpty()	스택이 full 상태인지 확인
clear()	스택의 모든 요소를 삭제
peek()	스택의 가장 최상위(마지막)에 위치한 데이터 출력
capacity()	스택의 용량 확인 (스택 전체 크기)
size()	스택의 크기 확인 (push된 만큼의 크기)
indexOf(int item)	item의 index 반환

 

■ Code

public class IntStack {
    private int[] stk;
    private int capacity;
    private int ptr;

    public class EmptyIntStackException extends RuntimeException{
        public EmptyIntStackException(){}
    }

    public class OverflowIntStackException extends RuntimeException{
        public OverflowIntStackException(){}
    }

    public IntStack(int maxlen){
        ptr = 0;
        capacity = maxlen;
        try{
            stk = new int[capacity];
        }catch (OutOfMemoryError e){
            capacity = 0;
        }
    }

    public int push(int x) throws OverflowIntStackException{
        if(ptr >= capacity)
            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];
    }

    public void clear(){
        ptr = 0;
    }

    public int indexOf(int x){
        for(int i = ptr - 1; i >= 0; i--)
            if(stk[i] == x)
                return i;
        return -1;
    }

    public int getCapacity(){
        return capacity;
    }

    public int size(){
        return ptr;
    }

    public boolean isEmpty(){
        return ptr <= 0;
    }

    public boolean isFull(){
        return ptr >= capacity;
    }

 

■ 백준 No.10828

10828번: 스택

 

---

큐 (Queue)

■ 정의

- 데이터를 일시적으로 쌓아 놓는 자료구조
- 데이터의 입력과 출력 순서는 선입선출 (FIFO: FirstIn First Out)

 

 

■ 메소드

Queue<Integer> q = new LinkedList<>();

 

메소드	의미
offer(int item), add(int item)	큐에 데이터를 저장
poll(), remove(),	큐의 맨 앞에 있는 데이터를 제거하고, 그 값을 반환
isFull()	큐가 empty 상태인지 확인
isEmpty()	큐가 full 상태인지 확인
clear()	큐의 모든 요소를 삭제
peek()	큐의 맨 앞에 위치한 데이터 출력
size()	큐의 크기 확인 (offer, add된 만큼의 크기)

 

■ Code

public class IntQueue {
    private int[] que;
    private int capacity;
    private int front;
    private int rear;
    private int num;

    public class EmptyIntQueueException extends RuntimeException{
        public EmptyIntQueueException(){}
    }

    public class OverflowIntQueueException extends RuntimeException{
        public OverflowIntQueueException(){}
    }


    public IntQueue(int maxlen){
        num = front = rear = 0;
        capacity = maxlen;
        try{
            que = new int[capacity];
        }catch (OutOfMemoryError e){
            capacity = 0;
        }
    }

    public int enque(int x) throws OverflowIntQueueException{		// offer, add
        if(num >= capacity)
            throw new OverflowIntQueueException();
        que[rear++] = x;
        num++;
        if(rear == capacity)
            rear = 0;
        return x;
    }

    public int deque() throws EmptyIntQueueException{			// poll, remove
        if(num < 0)
            throw new EmptyIntQueueException();
        int x = que[front++];
        num--;
        if(front == capacity)
            front = 0;
        return x;
    }

    public int peek() throws EmptyIntQueueException{
        if(num < 0)
            throw new EmptyIntQueueException();
        return que[front++];
    }

    public void clear(){
        num = front = rear = 0;
    }

    public int indexOf(int x){
        for(int i = 0; i < num; i++){
            int idx = (i + front) % capacity;
            if(que[idx] == x)
                return idx;
        }
        return -1;
    }

    public int getCapacity(){
        return capacity;
    }

    public int size(){
        return num;
    }

    public boolean isEmpty(){
        return num <= 0;
    }

    public boolean isFull(){
        return num >= capacity;
    }

 

■ 백준 No.18258

18258번: 큐 2