Java 스택 및 큐 구현 방법

1. 순환 큐 구현

[OJ 링크]

원형 큐는 일반적으로 배열을 통해 구현됩니다. 우리는 몇 가지 문제를 해결해야 합니다.

(1) 배열 첨자는 루프

a를 구현합니다. 첨자는 마지막이고 그 다음은 뒤로 옵니다(오프셋은 array.length보다 작음). 인덱스 = (인덱스 + 오프셋) % array.length. 더 간단하게 말하면, 배열의 크기가 8이고 첨자가 7에 도달하면 나중에 0으로 돌아가는 방법은 (index+1)%8로 달성할 수 있습니다.

b. 첨자가 ​​맨 먼저 나오고 그 다음이 앞으로 오면 특별히 판단하여 배열 크기에서 1을 뺀 값으로 설정합니다.

(2) 가득 찬 대기열과 빈 대기열 구별

배열의 위치를 ​​예약할 수 있습니다. 후면+1=전면이면 대기열이 가득 찼음을 의미하고, 후면=전면이면 대기열이 비어 있음을 의미합니다. 이 경우 배열 크기를 정의할 때 대기열 크기를 고려해야 하며, 원래 크기보다 하나 더 커야 합니다.

【코드는 다음과 같습니다】

class MyCircularQueue {
    public int front;
    public int rear;
    public int[] array;
 
    //构造方法
    public MyCircularQueue(int k) {
       //因为预留位置的缘故，数组的大小要定义为k+1
       this.array=new int[k+1];
    }
    //入队
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        this.array[this.rear]=value;
        this.rear=(this.rear+1)%this.array.length;
        return true;
    }
    //出队
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        this.front=(this.front+1)%this.array.length;
        return true;
    }
    //获取队头
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return this.array[front];
    }
    //获取队尾
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        int index=-1;
        if(this.rear==0){
            index=this.array.length-1;
        }else{
            index=this.rear-1;
        }
        return this.array[index];
    }
    //判断是否为空
    public boolean isEmpty() {
        if(this.front==this.rear){
            return true;
        }
        return false;
    }
    //判断队列是否满
    public boolean isFull() {
        if((this.rear+1)%this.array.length==this.front){
            return true;
        }
        return false;
    }
}

2.Queue 구현 스택

【OJ 링크】

스택의 선입선출 원칙과 선입선출 원칙 때문에 대기열의 아웃 원칙. 스택을 구현하려면 두 개의 대기열이 필요합니다. 두 대기열이 모두 비어 있으면 스택도 비어 있습니다.

• 푸시: 처음으로 스택에 푸시해도 상관없습니다. 두 대기열 모두 비어 있습니다. 나중에 스택에 푸시할 때 대기열이 분명히 있을 것입니다. 비어있지 않은 큐를 발견하면, 빈 큐(Empty queue)를 수행하여 enqueue 작업을 수행합니다.

• Pop: 먼저 스택이 비어 있으면 팝 작업을 수행할 수 없습니다. 스택이 비어 있지 않으면 비어 있는 큐(queue1)가 하나 있고 비어 있지 않은 큐(queue2)가 하나 있어야 합니다. Put queue1을 size-1 요소에 queue2로 팝하고(특히 queue1의 크기를 찾는 함수는 루프에 넣을 수 없다는 점에 유의하세요. 큐가 대기열에서 제거되면 크기가 변경됩니다) 마지막으로 queue1의 마지막 요소가 대기열에서 제거됩니다. . 가장 많이 반환된 값입니다.

• 스택의 최상위 요소 가져오기(top): 스택을 터뜨리는 것과 거의 동일하므로 자세히 설명하지 않겠습니다

[코드는 다음과 같습니다]

class MyStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;
 
    //构造方法
    public MyStack() {
        queue1=new LinkedList<>();
        queue2=new LinkedList<>();
    }
    //入栈
    public void push(int x) {
        if(!queue2.isEmpty()){
            queue2.offer(x);
        }else{
            queue1.offer(x);
        }
    }
    //出栈
    public int pop() {
        if(empty()){
            return -1;
        }
        if(queue1.isEmpty()){
            int size=queue2.size();
            for(int i=0;i<size-1;++i){
                int x=queue2.poll();
                queue1.offer(x);
            }
            return queue2.poll();
        }else{
            int size=queue1.size();
            for(int i=0;i<size-1;++i){
                int x=queue1.poll();
                queue2.offer(x);
            }
            return queue1.poll();
        }
    }
    //获取栈顶元素
    public int top() {
        if(empty()){
            return -1;
        }
        if(queue1.isEmpty()){
            int x=-1;
            int size=queue2.size();
            for(int i=0;i<size;++i){
                x=queue2.poll();
                queue1.offer(x);
            }
           return x;
        }else{
            int size=queue1.size();
            int x=-1;
            for(int i=0;i<size;++i){
                x=queue1.poll();
                queue2.offer(x);
            }
            return x;
        }
    }
    //判断栈是否为空
    public boolean empty() {
        if(queue1.isEmpty()&&queue2.isEmpty()){
            return true;
        }
        return false;
    }
}

3. queue

[OJ 링크]

위와 동일하게 2개의 스택(stack1, stack2)이 필요합니다. 스택 큐 구현과 달리 큐에 넣기는 동일한 스택에서만 작동할 수 있습니다. 두 스택이 모두 비어 있으면 대기열도 비어 있습니다.

• 팀 입장(푸시) : 팀 가입 시 stack1을 사용한다고 명시되어 있습니다. 대기열에 참가할 때마다 stack1을 스택에 밀어넣으면 됩니다.

• 대기열 제거(팝): 대기열 제거 작업을 수행하려면 stack2가 필요합니다. 대기열이 비어 있으면 대기열 제거 작업을 수행할 수 없습니다. stack2가 비어 있으면 stack1의 모든 요소를 ​​stack2로 팝한 다음 stack2를 팝해야 합니다. stack2가 비어 있지 않으면 stack2를 직접 팝하십시오.

• 큐의 시작 요소 가져오기(peek): 팝 작업과 동일하며 결국 stack2의 최상위 요소만 가져오면 됩니다.

[코드는 다음과 같습니다]

class MyQueue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    //构造方法
    public MyQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }
    //入队操作
    public void push(int x) {
        stack1.push(x);
    }
    //出队操作
    public int pop() {
        if(stack2.empty()){
            int size=stack1.size();
            for(int i=0;i<size;++i){
                int x=stack1.pop();
                stack2.push(x);
            }
        }
        return stack2.pop();
 
    }
    //获取队列开头的元素
    public int peek() {
        if(stack2.empty()){
            int size=stack1.size();
            for(int i=0;i<size;++i){
                int x=stack1.pop();
                stack2.push(x);
            }
        }
        return stack2.peek();
    }
    //判断队列是否为空
    public boolean empty() {
        if(stack1.empty()&&stack2.empty()){
            return true;
        }
        return false;
    }
}

4. 최소 스택 구현

[OJ 링크]

실제로는 O(1)의 시간 복잡도 내에서 스택의 최소 요소를 찾는 것입니다. . 이를 구현하려면 두 개의 스택이 필요하며, 하나의 스택은 팝핑 및 푸시 작업에 사용됩니다. 어떻게 작동하든 다른 스택의 최상위 요소가 현재 스택의 가장 작은 요소인지 확인하세요.

스택 1과 스택 2가 있습니다. 스테이션의 작업은 모두 스택 1에 있습니다.

• 푸싱: 처음으로 스택에 푸시되면 이후에도 스택 2에 넣어야 합니다. 요소는 스택으로 푸시됩니다. stack2의 최상위 요소와 비교하여 stack2의 최상위 요소보다 작으면 stack2에 넣습니다.

• Pop: stack1을 팝할 때 stack2의 최상위 요소와 비교하여 stack2의 최상위 요소와 같으면 stack2를 팝합니다.

이렇게 하면 stack2의 최상위 요소가 항상 stack1의 가장 작은 요소가 됩니다. 참고: 두 개의 동일한 최소 요소가 stack1에 푸시되는 경우 stack2를 스택에 푸시해야 합니다.

【코드는 다음과 같습니다】

class MinStack {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    //构造方法
    public MinStack() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }
    //入栈
    public void push(int val) {
        stack1.push(val);
        if(stack2.empty()){
            stack2.push(val);
        }else{
            if(val<=stack2.peek()){
                stack2.push(val);
            }
        }
    }
    //出栈
    public void pop() {
        int x=stack1.pop();
        if(x==stack2.peek()){
            stack2.pop();
        }
    }
    //获取栈顶元素
    public int top() {
        return stack1.peek();
    }
    //获取栈的最小元素
    public int getMin() {
        return stack2.peek();
    }
}

위 내용은 Java 스택 및 큐 구현 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!