stack, queue 정리

Stack

- 후입선출(LIFO) : 입출력은 맨 위에서만 일어남, 중간부분 데이터는 삭제 못함.

입출력이 이뤄지는 부분을 stack top, 바닥을 stack bottom, 스택에 저장되는 것을 elememt라고 함.

element가 없을 때는 empty stack이라 함.

 

push연산중에 stack이 가득차서 입력이 불가능하면 오류 발생.

pop연산중에 stack data가 없어서 출력이 불가능하면 역시 오류 발생

stack.empty()연산으로 비었는지 확인 후 pop

 

자료가 역순으로 출력되어야 하거나, 괄호검사에 이용.

배열과 연결리스트로 구현 가능.

 

Stack 구현

import java.util.EmptyStackException;
 
class Stack<T>{ //객체를 받을 때 데이터 타입을 명시하도록 함
    class Node<T>{
        private T data;
        private Node<T> next; //다음 노드
 
        public Node(T data) {
            this.data = data;
        }
    }
 
    //맨 위에 올라가 있는 주소
    private Node<T> top;
 
    public T pop(){
        if (top == null){
            throw new EmptyStackException();
        }
 
        //데이터 백업 후, 다음 노드를 탑으로 만들어줌
        T item = top.data;
        top = top.next;
        return item;
    }
 
    //1.push할 T type item하나 받는다.
    public void push(T item){
        //2.item으로 Node 생성
        Node<T> t = new Node<T>(item);
        //3.top앞에 그 노드를 위치시키고
        t.next = top;
        //4.그 노드가 top이 된다.
        top = t;
    }
 
    public T peek(){
        if(top == null){
            throw new EmptyStackException();
        }
        return top.data;
    }
 
    public boolean isEmpty(){
        return top == null;
    }
}
public class Main {
 
    public static void main(String[] args) {
        Stack<Integer> s = new Stack<Integer>();
 
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        System.out.println(s.pop());
        System.out.println(s.pop());
        System.out.println(s.peek());
        System.out.println(s.pop());
        System.out.println(s.isEmpty());
        System.out.println(s.pop());
        System.out.println(s.isEmpty());
    }
}
 

 

queue

- 선입선출(FIFO) : 매표소에서 줄 서는 것을 생각하자. 가장 먼저 들어온게 가장 먼저 나감. 삽입삭제가 같은 곳에서 일어남.

삭제가 일어나는 곳을 front, 삭제가 일어나는 곳을 rear라고 함.

선형큐, 우선순위 큐가 있음. 우선순위 큐는 우선순위가 부여된 queue!

 

배열로 구현된 queue는 front와 rear변수가 필요한데, 초기값이 -1에서 시작하고, 값이 계속 증가만 하기때문에 언젠가 배열의 끝에 도달하게 됨. 따라서 주기적으로 모든 요소들을 왼쪽으로 이동시켜줘야함.

따라서 연결리스트로 만들어진 queue를 사용하는 것이 편한데, 크기가 제한되지 않는다는 장점을 가짐.

but 링크필드때문에 더 많은 메모리 공간 가짐.

 

삭제 연산은 queue가 비어있는지(queue.empty())확인 후 꺼낸다.

 

*deque : double-ended queue의 줄임말.

queue의 front와 rear에서 모두 삽입삭제가 가능한 큐. 보통 이중 연겨리스트로 구현됨.

 

*우선순위 큐(priority queue)

높은 우선순위를 가진 원소가 먼저 처리됨. (우선순위가 높은 환자 먼저 치료)

배열, 연결리스트, Heap으로 구현 가능.

 

C++에서는 heap으로 구현되어있어 특정 원소를 push하는 정렬 과정은 O(logN),

큰 숫자가 먼저 출력되어 default가 내림차순으로 되어있음.

priority_queue<int, vector<int>, greater<int>> pq; , push(-4)처럼 -붙여주면 오름차순 정렬 가능

 

 

import java.util.NoSuchElementException;
 
class Queue<T>{
    class Node<T>{
        private T data;
        private Node<T> next;
 
        public Node(T data) {
            this.data = data;
        }
    }
 
    private Node<T> first;
    private Node<T> last;
 
    public void add(T item){
        Node<T> t = new Node<T>(item);
 
        if(last != null){
            last.next = t;
        }
        last = t;
        if(first==null){
            first=last;
        }
    }
 
    public T remove(){
        if(first == null){
            throw new NoSuchElementException();
        }
        T data = first.data;
        first= first.next;
 
        if(first==null){
            last=null;
        }
        return data;
    }
 
    public T peek(){
        if(first == null){
            throw new NoSuchElementException();
        }
        return first.data;
    }
 
    public boolean isEmpty(){
        return first==null;
    }
 
}
public class Main {
 
    public static void main(String[] args) {
        Queue<Integer> q = new Queue<Integer>();
        q.add(1);
        q.add(2);
        q.add(3);
        q.add(4);
        System.out.println(q.remove());
        System.out.println(q.remove());
        System.out.println(q.peek());
        System.out.println(q.remove());
        System.out.println(q.isEmpty());
        System.out.println(q.remove());
        System.out.println(q.isEmpty());
    }
}