큐 / 스택

[WonYong-Jang]

원형큐 ( Circular Queue )

• 원형 큐는 선형 큐의 문제점을 보완하기 위한 자료구조 입니다. 선형큐의 문제점은 rear가 가르키는 포인터가 배열의 마지막 인덱스를 가르키고 있을 때 앞쪽에서 Dequeue로 발생한 배열의 빈 공간을 활용 할수가 없었습니다.

public class Circular_Queue {

    int rear = 0;            //최초 0에서부터 시작
    int front = 0;            //최초 0에서부터 시작
    int maxsize = 0;        //배열의 크기
    int[] circular_Queue;          //배열

    public Circular_Queue(int maxsize)
    {
        this.maxsize = maxsize;
        circular_Queue = new int[this.maxsize];
    }

    public boolean Isempty()    //배열이 공백 상태인지 체크하는 메서드입니다.
    {
        if(rear == front)
        {
            return true;
        }
        return false;
    }
    public boolean Isfull()        //배열이 포화 상태인지 체크하는 메서드입니다.
    {
        if((rear+1)%maxsize == front)
        {
            return true;
        }
        return false;
    }

    public void EnQueue(int num)
    {
        if(Isfull())            //배열이 포화상태일경우
        {
            System.out.println("큐가 가득 찼습니다");
        }
        else                //배열이 포화상태가 아닐경우
        {
            rear = (rear+1) % maxsize;
            circular_Queue[rear]=num;
        }
    }

public int DeQueue()
    {
        if(Isempty())         //배열이 공백상태이면 -1반환
        {
            return -1;
        }
        else                 //배열이 공백상태가 아니라면
        {
            front = (front+1)%maxsize;
            return circular_Queue[front];
        }
    }
}

링크드리스트를 이용하여 큐 구현

원형큐를 이용하여 선형큐의 단점을 극복하였지만, 원형큐의 경우도 원소가 없을 때도 배열의 크기를 유지하고 있어야하므로 메모리 낭비가 있을수 있다는 단점이 있다.

public class LinkedQueue{
    Node front;
    Node rear;
    public class Node {
        int data;
        Node next;
    }
    public LinkedQueue() {
        front = null;
        rear = null;
    }    

    @Override
    public boolean isEmpty() {
        return (front==null);
    }

    @Override
    public void enQueue(int item) {
        QueueNode node = new QueueNode(item);

        if(isEmpty()){ // 처음 만든 경우는 font rear 같은 노드로 설정
            front = node;
            rear = node;
        }else{
            rear.next = node;
            rear = node;
        }
    }

    @Override
    public char deQueue() {
        if(isEmpty()){
            System.out.println("큐의 내용이 존재하지 않습니다.");
            return 0;
        }else{
            int item = front.item;
            front = front.next;
            if(front==null){ // 삭제전 front 랑 rear 같은 위치에 있었던 경우 해당 노드가 삭제됬으니 rear null
                rear=null;
            }
            return item;
        }
    }

[WonYong-Jang]

스택 문제 응용 / leetcode

• 32 Longest Valid Parentheses
• 739 dailyTemperatures
• 155 Min Stack
• 716 Max Stack

스택 문제 응용 중요!

503. Next Greater Element II
504. Reverse Substrings Between Each Pair of Parentheses
505. Basic Calculator II
506. Remove Duplicate Letters

[WonYong-Jang]

Stack 두개로 Queue 만들기

해커랭크 Queues: A Tale of Two Stacks leetcode 232

Queue로 Stack 만들기

leetcode 225

원형 큐

622. Design Circular Queue

원형 Deque

641. Design Circular Deque

[WonYong-Jang]

히스토그램에서 가장 큰 직사각형구하기 (스택 )

• 스택에 막대를 하나씩 넣으면서, 스택의 top 보다 다음 막대의 높이가 크다면, push 한다 -그렇지 않다면, 다음 막대의 높이를 기준으로, 스택을 pop 하면서, 넓이를 비교한다.
• 이과정에서 top이 직사각형의 왼쪽 끝이 되고, i가 오른쪽 끝이 된다.

https://mygumi.tistory.com/177