it-swarm-ko.tech

두 개의 스택을 사용하여 큐를 구현하는 방법은 무엇입니까?

두 개의 스택과 다른 임시 변수가 없다고 가정합니다.

두 개의 스택만을 사용하여 큐 데이터 구조를 "구성"할 수 있습니까?

373
Nitin

2 스택을 유지하고 inboxoutbox이라고 부르 자.

Enqueue :

  • 새 요소를 inbox으로 푸시합니다.

Dequeue :

  • outbox이 비어 있으면 inbox에서 각 요소를 가져 와서 outbox으로 푸시하여 다시 채 웁니다.

  • outbox에서 최상위 요소를 팝 앤 리턴합니다.

이 방법을 사용하면 각 요소가 각 스택에 정확히 한 번씩 표시됩니다. 즉, 각 요소가 두 번 푸시되고 두 번 팝업되어 상각 된 일정 시간 작업이 수행됩니다.

다음은 Java로 구현 한 것입니다.

public class Queue<E>
{

    private Stack<E> inbox = new Stack<E>();
    private Stack<E> outbox = new Stack<E>();

    public void queue(E item) {
        inbox.Push(item);
    }

    public E dequeue() {
        if (outbox.isEmpty()) {
            while (!inbox.isEmpty()) {
               outbox.Push(inbox.pop());
            }
        }
        return outbox.pop();
    }

}
676
Dave L.

A - 스택을 뒤집는 방법

두 개의 스택을 사용하여 큐를 생성하는 방법을 이해하려면 스택을 투명하게 뒤집는 방법을 이해해야합니다. 스택 작동 방식을 기억하십시오. 부엌의 접시 더미와 매우 유사합니다. 마지막으로 씻은 접시는 L ast I n으로 불리는 깨끗한 스택 맨 위에 있습니다. 컴퓨터 과학에서 F irst O ut (LIFO).

우리의 스택을 아래와 같이 병처럼 상상해보십시오.

enter image description here

정수 1,2,3을 각각 푸시하면 3이 스택 맨 위에 놓이게됩니다. 1이 먼저 푸시 (push)되기 때문에 2가 1의 맨 위에 놓이게됩니다. 마지막으로 3이 스택의 맨 위에 놓이고 병으로 표시된 스택의 최신 상태는 아래와 같이됩니다.

enter image description here

이제 병으로 표현 된 스택을 3,2,1 값으로 채 웁니다. 스택의 맨 위 요소가 1이되고 스택의 맨 아래 요소가 3이되도록 스택을 뒤집기를 원합니다. 우리가 할 수있는 일은 무엇입니까? 우리는 병을 가져 와서 거꾸로 잡아서 모든 값을 순서대로 뒤집을 수 있습니까?

enter image description here

네, 그렇게 할 수는 있지만 그건 병입니다. 동일한 프로세스를 수행하려면 첫 번째 스택 요소를 역순으로 저장하는 두 번째 스택이 필요합니다. 채워진 스택을 왼쪽에 넣고 새로운 빈 스택을 오른쪽에 넣자. 요소의 순서를 바꾸려면 왼쪽 스택에서 각 요소를 팝하고 오른쪽 스택으로 푸시해야합니다. 우리는 아래 그림에서와 같이 어떻게되는지 알 수 있습니다.

enter image description here

그래서 우리는 스택을 뒤집는 방법을 알고 있습니다.

B - 두 개의 스택을 대기열로 사용

이전 부분에서는 어떻게 스택 요소의 순서를 바꿀 수 있는지 설명했습니다. 이것은 중요한 요소입니다. 왜냐하면 요소를 스택에 푸시 (push)하고 팝 (pop)하면 출력은 정확하게 대기열의 역순으로 출력되기 때문입니다. 예제를 생각해 보자. 정수 배열 {1, 2, 3, 4, 5}을 스택에 넣자. 스택을 비울 때까지 요소를 뽑아서 출력하면 {5, 4, 3, 2, 1}가 될 순서의 역순으로 배열을 얻습니다. 동일한 입력에 대해 큐가 비어있을 때까지 큐를 큐에서 제거하면 출력은 {1, 2, 3, 4, 5}가됩니다. 따라서 요소의 동일한 입력 순서에 대해 대기열의 출력은 스택의 출력과 정확히 반대입니다. 추가 스택을 사용하여 스택을 역전시키는 방법을 알았으므로 두 스택을 사용하여 대기열을 구성 할 수 있습니다.

우리의 대기열 모델은 두 개의 스택으로 구성됩니다. 하나의 스택이 enqueue 연산에 사용되며 (왼쪽의 스택 1은 입력 스택이라고 함), 다른 스택은 dequeue 연산에 사용됩니다 (오른쪽의 스택 2는 출력 스택이라고합니다). 아래 이미지를 확인하십시오.

enter image description here

우리의 의사 코드는 아래와 같습니다.


엔큐 작업

Push every input element to the Input Stack

큐 꺼내기 작업

If ( Output Stack is Empty)
    pop every element in the Input Stack
    and Push them to the Output Stack until Input Stack is Empty

pop from Output Stack

{1, 2, 3} 정수를 각각 대기열에 넣자. 정수는 왼쪽에있는 입력 스택 ( Stack # 1 )에 푸시됩니다.

enter image description here

그런 다음 dequeue 연산을 실행하면 어떻게됩니까? dequeue 연산이 실행될 때마다 큐는 출력 스택이 비어 있는지 확인합니다 (위의 의사 코드 참조). 출력 스택이 비어 있으면 출력 스택에 입력 스택이 추출 될 것이므로 요소 입력 스택의 값이 반전됩니다. 값을 반환하기 전에 대기열의 상태는 다음과 같습니다.

enter image description here

출력 스택 (Stack # 2)에서 요소의 순서를 확인하십시오. 출력 스택에서 요소를 가져 와서 대기열에서 대기열에서 대기 행렬을 제거한 것과 같은 결과를 얻을 수 있다는 것은 명백합니다. 따라서 우리가 두 개의 dequeue 연산을 수행한다면, 먼저 각각 {1, 2}를 얻을 것이다. 그러면 요소 3이 출력 스택의 유일한 요소가되고 입력 스택은 비게됩니다. 요소 4와 5를 대기열에 추가하면 대기열의 상태는 다음과 같습니다.

enter image description here

이제 출력 스택은 비어 있지 않으며 디큐 작업을 실행하면 출력 스택에서 3 개만 튀어 나옵니다. 그러면 주정부는 아래와 같이 표시됩니다.

enter image description here

다시 말하면 두 번 더 dequeue 작업을 실행하면 첫 번째 dequeue 작업에서 queue는 출력 스택이 비 었는지 확인합니다. 그런 다음 입력 스택의 요소를 띄우고 입력 스택이 비어 있지 않으면 출력 스택으로 밀어 넣습니다. 그러면 큐의 상태는 다음과 같습니다.

enter image description here

쉽게 볼 수있는 두 대기열 작업의 출력은 {4, 5}입니다.

C - 두 개의 스택으로 구성된 대기열 구현

다음은 Java로 구현 한 것입니다. Stack의 기존 구현을 사용하지 않을 것이므로 여기서 예가 휠을 다시 만들 것입니다.

C - 1) MyStack 클래스 : 간단한 스택 구현

public class MyStack<T> {

    // inner generic Node class
    private class Node<T> {
        T data;
        Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }

    private Node<T> head;
    private int size;

    public void Push(T e) {
        Node<T> newElem = new Node(e);

        if(head == null) {
            head = newElem;
        } else {
            newElem.next = head;
            head = newElem;     // new elem on the top of the stack
        }

        size++;
    }

    public T pop() {
        if(head == null)
            return null;

        T elem = head.data;
        head = head.next;   // top of the stack is head.next

        size--;

        return elem;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void printStack() {
        System.out.print("Stack: ");

        if(size == 0)
            System.out.print("Empty !");
        else
            for(Node<T> temp = head; temp != null; temp = temp.next)
                System.out.printf("%s ", temp.data);

        System.out.printf("\n");
    }
}

C - 2) MyQueue 클래스 : 두 개의 스택을 사용하는 대기열 구현

public class MyQueue<T> {

    private MyStack<T> inputStack;      // for enqueue
    private MyStack<T> outputStack;     // for dequeue
    private int size;

    public MyQueue() {
        inputStack = new MyStack<>();
        outputStack = new MyStack<>();
    }

    public void enqueue(T e) {
        inputStack.Push(e);
        size++;
    }

    public T dequeue() {
        // fill out all the Input if output stack is empty
        if(outputStack.isEmpty())
            while(!inputStack.isEmpty())
                outputStack.Push(inputStack.pop());

        T temp = null;
        if(!outputStack.isEmpty()) {
            temp = outputStack.pop();
            size--;
        }

        return temp;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

}

C - 3) 데모 코드

public class TestMyQueue {

    public static void main(String[] args) {
        MyQueue<Integer> queue = new MyQueue<>();

        // enqueue integers 1..3
        for(int i = 1; i <= 3; i++)
            queue.enqueue(i);

        // execute 2 dequeue operations 
        for(int i = 0; i < 2; i++)
            System.out.println("Dequeued: " + queue.dequeue());

        // enqueue integers 4..5
        for(int i = 4; i <= 5; i++)
            queue.enqueue(i);

        // dequeue the rest
        while(!queue.isEmpty())
            System.out.println("Dequeued: " + queue.dequeue());
    }

}

C - 4) 샘플 출력

Dequeued: 1
Dequeued: 2
Dequeued: 3
Dequeued: 4
Dequeued: 5
198
Levent Divilioglu

하나의 스택 만 사용하여 대기열을 시뮬레이션 할 수도 있습니다. 두 번째 (임시) 스택은 삽입 메소드에 대한 재귀 호출 호출 스택에 의해 시뮬레이트 될 수 있습니다.

큐에 새 요소를 삽입 할 때도 마찬가지입니다.

  • 순서를 바꾸려면 요소를 한 스택에서 다른 임시 스택으로 전송해야합니다.
  • 그런 다음 삽입 할 새 요소를 임시 스택에 푸시합니다.
  • 그런 다음 요소를 다시 원래 스택으로 전송합니다.
  • 새 요소는 스택의 맨 아래에 있고, 가장 오래된 요소는 맨 위에 있습니다 (먼저 팝됩니다)

스택을 하나만 사용하는 Queue 클래스는 다음과 같습니다.

public class SimulatedQueue<E> {
    private Java.util.Stack<E> stack = new Java.util.Stack<E>();

    public void insert(E elem) {
        if (!stack.empty()) {
            E topElem = stack.pop();
            insert(elem);
            stack.Push(topElem);
        }
        else
            stack.Push(elem);
    }

    public E remove() {
        return stack.pop();
    }
}
80
pythonquick

시간 복잡성은 더 나을 것입니다. 좋은 대기열 구현은 모든 것을 일정한 시간 내에 수행합니다.

편집

왜 내 대답은 여기에 downvoted 확실하지. 우리가 프로그래밍을한다면 시간 복잡성에 신경을 쓰고 큐를 만들기 위해 두 개의 표준 스택을 사용하는 것은 비효율적입니다. 그것은 매우 타당하고 적절한 것입니다. 누군가 다른 사람이 이것을 더 downvote 할 필요성을 느낀다면 나는 그 이유를 알고 싶어합니다.

좀 더 자세한 내용 : 왜 두 개의 스택을 사용하는 것이 단지 대기열보다 나쁜지 : 두 개의 스택을 사용하고 보낼 편지함이 비어있는 동안 누군가가 대기열에서 dequeue를 호출하면 , Dave의 코드에서 볼 수 있듯이받은 편지함의 맨 아래로 가려면 선형 시간이 필요합니다.

단일 링크 된 목록 (각 요소는 다음에 삽입 된 요소를 가리킴)으로 큐를 구현할 수 있으며 푸시 용으로 마지막으로 삽입 된 요소에 대한 추가 포인터를 유지합니다 (또는 순환 목록으로 만듭니다). 이 데이터 구조에 큐 및 큐를 구현하는 것은 일정 시간 내에 매우 쉽게 수행 할 수 있습니다. 그것은 상환 시간이 아니라 최악의 일정 시간입니다. 그리고 코멘트가이 설명을 요구하는 것처럼 보이기 때문에, 최악의 경우의 상수 시간은 상각 된 상수 시간보다 엄격히 좋습니다.

11
Tyler

구현 될 큐를 q로 만들고, q를 구현하는 데 사용되는 스택을 stack1 및 stack2로 보자.

q는 two 방법으로 구현 될 수 있습니다 :

방법 1 (enQueue 연산을 값 비싸게 만드는 것)

이 메소드는 새로 입력 한 요소가 항상 스택 1의 상단에 있는지 확인하여 deQueue 연산이 stack1에서 시작되도록합니다. stack1의 맨 위에 요소를 두려면 stack2가 사용됩니다.

enQueue(q, x)
1) While stack1 is not empty, Push everything from stack1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
deQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it.

방법 2 (deQueue 연산을 값 비싸게 만들어줌으로써)

이 메소드에서 대기열 작업에서 새 요소는 stack1의 맨 위에 입력됩니다. 대기열 제거 작업에서 stack2가 비어 있으면 모든 요소가 stack2로 이동하고 마지막으로 stack2의 맨 위가 반환됩니다.

enQueue(q,  x)
 1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
 1) If both stacks are empty then error.
 2) If stack2 is empty
   While stack1 is not empty, Push everything from stack1 to stack2.
 3) Pop the element from stack2 and return it.

메서드 2는 메서드 1보다 확실히 좋습니다. 메서드 1은 enQueue 작업에서 모든 요소를 ​​두 번 이동하지만 메서드 2 (deQueue 작업에서)는 요소를 한 번 이동하고 stack2가 비어있는 경우에만 요소를 이동합니다.

7
Rahul Gandhi

C #의 솔루션

 public class Queue<T> where T : class
    {
        private Stack<T> input = new Stack<T>();
        private Stack<T> output = new Stack<T>();
        public void Enqueue(T t)
        {
            input.Push(t);
        }

        public T Dequeue()
        {
            if (output.Count == 0)
            {
                while (input.Count != 0)
                {
                    output.Push(input.Pop());
                }
            }
            return output.Pop();
        }
}
3
Santhosh

맨 아래 요소를 얻으려면 첫 번째 스택에서 모든 것을 팝해야합니다. 그런 다음 모든 "대기열에서 제외"작업을 수행 할 때마다 두 번째 스택에 모두 다시 넣습니다.

2
user11055

C # 개발자는 전체 프로그램입니다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace QueueImplimentationUsingStack
{
    class Program
    {
        public class Stack<T>
        {
            public int size;
            public Node<T> head;
            public void Push(T data)
            {
                Node<T> node = new Node<T>();
                node.data = data;
                if (head == null)
                    head = node;
                else
                {
                    node.link = head;
                    head = node;
                }
                size++;
                Display();
            }
            public Node<T> Pop()
            {
                if (head == null)
                    return null;
                else
                {
                    Node<T> temp = head;
                    //temp.link = null;
                    head = head.link;
                    size--;
                    Display();
                    return temp;
                }
            }
            public void Display()
            {
                if (size == 0)
                    Console.WriteLine("Empty");
                else
                {
                    Console.Clear();
                    Node<T> temp = head;
                    while (temp!= null)
                    {
                        Console.WriteLine(temp.data);
                        temp = temp.link;
                    }
                }
            }
        }

        public class Queue<T>
        {
            public int size;
            public Stack<T> inbox;
            public Stack<T> outbox;
            public Queue()
            {
                inbox = new Stack<T>();
                outbox = new Stack<T>();
            }
            public void EnQueue(T data)
            {
                inbox.Push(data);
                size++;
            }
            public Node<T> DeQueue()
            {
                if (outbox.size == 0)
                {
                    while (inbox.size != 0)
                    {
                        outbox.Push(inbox.Pop().data);
                    }
                }
                Node<T> temp = new Node<T>();
                if (outbox.size != 0)
                {
                    temp = outbox.Pop();
                    size--;
                }
                return temp;
            }

        }
        public class Node<T>
        {
            public T data;
            public Node<T> link;
        }

        static void Main(string[] args)
        {
            Queue<int> q = new Queue<int>();
            for (int i = 1; i <= 3; i++)
                q.EnQueue(i);
           // q.Display();
            for (int i = 1; i < 3; i++)
                q.DeQueue();
            //q.Display();
            Console.ReadKey();
        }
    }
}
2
Jaydeep Shil

대기열의 두 스택은 다음과 같이 정의됩니다. 스택 1 과 스택 2.

Enqueue : euqueued 요소는 항상 스택 1

Dequeue : 맨 위 스택 2 큐에 삽입 된 첫 번째 요소이기 때문에 튀어 나올 수 있습니다. 스택 2 비어 있지 않습니다. 언제 스택 2 비어 있으면 우리는 모든 요소를 ​​팝합니다. 스택 1 그들을 안으로 밀어 넣는다. 스택 2 하나씩. 큐의 첫 번째 요소는 아래쪽으로 밀어 넣습니다. 스택 1. 그것은 터지기와 밀기 조작 후에 바로 튀어 나올 수 있습니다. 스택 2.

다음은 동일한 C++ 샘플 코드입니다.

template <typename T> class CQueue
{
public:
    CQueue(void);
    ~CQueue(void);

    void appendTail(const T& node); 
    T deleteHead();                 

private:
    stack<T> stack1;
    stack<T> stack2;
};

template<typename T> void CQueue<T>::appendTail(const T& element) {
    stack1.Push(element);
} 

template<typename T> T CQueue<T>::deleteHead() {
    if(stack2.size()<= 0) {
        while(stack1.size()>0) {
            T& data = stack1.top();
            stack1.pop();
            stack2.Push(data);
        }
    }


    if(stack2.size() == 0)
        throw new exception("queue is empty");


    T head = stack2.top();
    stack2.pop();


    return head;
}

이 솔루션은 내 블로그 에서 빌려 왔습니다. 내 블로그 웹 페이지에서 단계별 작업 시뮬레이션을 통해보다 자세한 분석을 할 수 있습니다.

2
Harry He
// Two stacks s1 Original and s2 as Temp one
    private Stack<Integer> s1 = new Stack<Integer>();
    private Stack<Integer> s2 = new Stack<Integer>();

    /*
     * Here we insert the data into the stack and if data all ready exist on
     * stack than we copy the entire stack s1 to s2 recursively and Push the new
     * element data onto s1 and than again recursively call the s2 to pop on s1.
     * 
     * Note here we can use either way ie We can keep pushing on s1 and than
     * while popping we can remove the first element from s2 by copying
     * recursively the data and removing the first index element.
     */
    public void insert( int data )
    {
        if( s1.size() == 0 )
        {
            s1.Push( data );
        }
        else
        {
            while( !s1.isEmpty() )
            {
                s2.Push( s1.pop() );
            }
            s1.Push( data );
            while( !s2.isEmpty() )
            {
                s1.Push( s2.pop() );
            }
        }
    }

    public void remove()
    {
        if( s1.isEmpty() )
        {
            System.out.println( "Empty" );
        }
        else
        {
            s1.pop();

        }
    }
1
imvp

Swift에서 두 개의 스택을 사용하는 대기열 구현 :

struct Stack<Element> {
    var items = [Element]()

    var count : Int {
        return items.count
    }

    mutating func Push(_ item: Element) {
        items.append(item)
    }

    mutating func pop() -> Element? {
        return items.removeLast()
    }

    func peek() -> Element? {
        return items.last
    }
}

struct Queue<Element> {
    var inStack = Stack<Element>()
    var outStack = Stack<Element>()

    mutating func enqueue(_ item: Element) {
        inStack.Push(item)
    }

    mutating func dequeue() -> Element? {
        fillOutStack() 
        return outStack.pop()
    }

    mutating func peek() -> Element? {
        fillOutStack()
        return outStack.peek()
    }

    private mutating func fillOutStack() {
        if outStack.count == 0 {
            while inStack.count != 0 {
                outStack.Push(inStack.pop()!)
            }
        }
    }
}
1
davejlin

두 개의 스택이있는 대기열을 구현하는 것과 관련하여 많은 게시물을 얻을 수 있습니다. 1. enQueue 프로세스의 비용을 훨씬 많이 들여야합니다. 2. deQueue 프로세스를 훨씬 더 비싸게 만들어야합니다.

https://www.geeksforgeeks.org/queue-using-stacks/

위의 게시물에서 발견 한 중요한 한 가지 방법은 스택 데이터 구조와 재귀 호출 스택을 사용하여 큐를 생성하는 것이 었습니다.

문자 적으로 이것은 여전히 ​​2 개의 스택을 사용하고 있다고 주장 할 수 있지만 이상적으로 이것은 하나의 스택 데이터 구조만을 사용하는 것이 이상적입니다.

아래는 문제에 대한 설명입니다.

  1. 데이터를 enQueuing 및 deQueing하기 위해 단일 스택을 선언하고 데이터를 스택으로 푸시합니다.

  2. deQueueing은 스택의 크기가 1 일 때 스택 요소가 팝되는 기본 조건을 갖습니다. 이렇게하면 deQueue 재귀 중에 스택 오버플로가 발생하지 않습니다.

  3. DeQueueing이 먼저 스택 맨 위에서 데이터를 팝합니다. 이상적으로이 요소는 스택 맨 위에있는 요소가됩니다. 이제 이것이 일단 완료되면, 재귀 적으로 deQueue 함수를 호출 한 다음 위에 팝업 된 요소를 다시 스택으로 푸시합니다.

코드는 다음과 같습니다.

if (s1.isEmpty())
System.out.println("The Queue is empty");
        else if (s1.size() == 1)
            return s1.pop();
        else {
            int x = s1.pop();
            int result = deQueue();
            s1.Push(x);
            return result;

이렇게하면 단일 스택 데이터 구조와 재귀 호출 스택을 사용하여 대기열을 만들 수 있습니다.

1
Radioactive

여기에 자바로 연결된 목록을 사용하여 내 솔루션입니다.

class queue<T>{
static class Node<T>{
    private T data;
    private Node<T> next;
    Node(T data){
        this.data = data;
        next = null;
    }
}
Node firstTop;
Node secondTop;

void Push(T data){
    Node temp = new Node(data);
    temp.next = firstTop;
    firstTop = temp;
}

void pop(){
    if(firstTop == null){
        return;
    }
    Node temp = firstTop;
    while(temp != null){
        Node temp1 = new Node(temp.data);
        temp1.next = secondTop;
        secondTop = temp1;
        temp = temp.next;
    }
    secondTop = secondTop.next;
    firstTop = null;
    while(secondTop != null){
        Node temp3 = new Node(secondTop.data);
        temp3.next = firstTop;
        firstTop = temp3;
        secondTop = secondTop.next;
    }
}

}

Note :이 경우 팝 조작은 시간이 많이 걸립니다. 그래서 두 개의 스택을 사용하여 대기열을 만들 것을 제안하지는 않을 것입니다.

0
Irshad ck

Go는 표준 라이브러리에 풍부한 콜렉션이 없기 때문에 Go에서이 질문에 답할 것입니다.

스택은 실제로 구현하기 쉽기 때문에 이중 스택 대기열을 완성하기 위해 두 개의 스택을 사용하려고합니다. 내 대답에 어떻게 도달했는지 더 잘 이해하기 위해 구현을 두 부분으로 나누었습니다. 첫 부분은 이해하기 쉽지만 불완전합니다.

type IntQueue struct {
    front       []int
    back        []int
}

func (q *IntQueue) PushFront(v int) {
    q.front = append(q.front, v)
}

func (q *IntQueue) Front() int {
    if len(q.front) > 0 {
        return q.front[len(q.front)-1]
    } else {
        return q.back[0]
    }
}

func (q *IntQueue) PopFront() {
    if len(q.front) > 0 {
        q.front = q.front[:len(q.front)-1]
    } else {
        q.back = q.back[1:]
    }
}

func (q *IntQueue) PushBack(v int) {
    q.back = append(q.back, v)
}

func (q *IntQueue) Back() int {
    if len(q.back) > 0 {
        return q.back[len(q.back)-1]
    } else {
        return q.front[0]
    }
}

func (q *IntQueue) PopBack() {
    if len(q.back) > 0 {
        q.back = q.back[:len(q.back)-1]
    } else {
        q.front = q.front[1:]
    }
}

기본적으로 스택의 하단을 서로 조작 할 수있는 두 개의 스택입니다. 또한 STL 명명 규칙을 사용했습니다. 스택의 일반적인 Push, pop, peek 작업은 대기열의 앞이나 뒤로 참조 할 때 앞/뒤 접두사가 있습니다.

위 코드의 문제는 메모리를 매우 효율적으로 사용하지 않는다는 것입니다. 실제로, 그것은 당신이 공간을 다 쓸 때까지 끝없이 자랍니다. 정말 안좋아. 이 문제를 해결하려면 가능할 때마다 스택 공간의 맨 아래 부분을 다시 사용하기 만하면됩니다. Go의 슬라이스가 축소되면 앞쪽으로 자랄 수 없기 때문에 이것을 추적하기위한 오프셋을 도입해야합니다.

type IntQueue struct {
    front       []int
    frontOffset int
    back        []int
    backOffset  int
}

func (q *IntQueue) PushFront(v int) {
    if q.backOffset > 0 {
        i := q.backOffset - 1
        q.back[i] = v
        q.backOffset = i
    } else {
        q.front = append(q.front, v)
    }
}

func (q *IntQueue) Front() int {
    if len(q.front) > 0 {
        return q.front[len(q.front)-1]
    } else {
        return q.back[q.backOffset]
    }
}

func (q *IntQueue) PopFront() {
    if len(q.front) > 0 {
        q.front = q.front[:len(q.front)-1]
    } else {
        if len(q.back) > 0 {
            q.backOffset++
        } else {
            panic("Cannot pop front of empty queue.")
        }
    }
}

func (q *IntQueue) PushBack(v int) {
    if q.frontOffset > 0 {
        i := q.frontOffset - 1
        q.front[i] = v
        q.frontOffset = i
    } else {
        q.back = append(q.back, v)
    }
}

func (q *IntQueue) Back() int {
    if len(q.back) > 0 {
        return q.back[len(q.back)-1]
    } else {
        return q.front[q.frontOffset]
    }
}

func (q *IntQueue) PopBack() {
    if len(q.back) > 0 {
        q.back = q.back[:len(q.back)-1]
    } else {
        if len(q.front) > 0 {
            q.frontOffset++
        } else {
            panic("Cannot pop back of empty queue.")
        }
    }
}

작은 함수가 많지만 6 개의 함수 중 3 개는 다른 함수의 거울입니다.

0
John Leidegren

아래는 ES6 구문을 사용하는 자바 스크립트 언어의 솔루션입니다.

Stack.js

//stack using array
class Stack {
  constructor() {
    this.data = [];
  }

  Push(data) {
    this.data.Push(data);
  }

  pop() {
    return this.data.pop();
  }

  peek() {
    return this.data[this.data.length - 1];
  }

  size(){
    return this.data.length;
  }
}

export { Stack };

QueueUsingTwoStacks.js

import { Stack } from "./Stack";

class QueueUsingTwoStacks {
  constructor() {
    this.stack1 = new Stack();
    this.stack2 = new Stack();
  }

  enqueue(data) {
    this.stack1.Push(data);
  }

  dequeue() {
    //if both stacks are empty, return undefined
    if (this.stack1.size() === 0 && this.stack2.size() === 0)
      return undefined;

    //if stack2 is empty, pop all elements from stack1 to stack2 till stack1 is empty
    if (this.stack2.size() === 0) {
      while (this.stack1.size() !== 0) {
        this.stack2.Push(this.stack1.pop());
      }
    }

    //pop and return the element from stack 2
    return this.stack2.pop();
  }
}

export { QueueUsingTwoStacks };

사용법은 다음과 같습니다.

index.js

import { StackUsingTwoQueues } from './StackUsingTwoQueues';

let que = new QueueUsingTwoStacks();
que.enqueue("A");
que.enqueue("B");
que.enqueue("C");

console.log(que.dequeue());  //output: "A"
0
Jyoti Prasad Pal
public class QueueUsingStacks<T>
{
    private LinkedListStack<T> stack1;
    private LinkedListStack<T> stack2;

    public QueueUsingStacks()
    {
        stack1=new LinkedListStack<T>();
        stack2 = new LinkedListStack<T>();

    }
    public void Copy(LinkedListStack<T> source,LinkedListStack<T> dest )
    {
        while(source.Head!=null)
        {
            dest.Push(source.Head.Data);
            source.Head = source.Head.Next;
        }
    }
    public void Enqueue(T entry)
    {

       stack1.Push(entry);
    }
    public T Dequeue()
    {
        T obj;
        if (stack2 != null)
        {
            Copy(stack1, stack2);
             obj = stack2.Pop();
            Copy(stack2, stack1);
        }
        else
        {
            throw new Exception("Stack is empty");
        }
        return obj;
    }

    public void Display()
    {
        stack1.Display();
    }


}

모든 대기열 작업에 대해 스택 1의 맨 위에 추가합니다. 모든 dequeue에 대해 stack1의 내용을 stack2에 비우고 스택 맨 위에서 요소를 제거합니다. stack1을 stack2에 복사해야하므로 dequeue에 대해 O(n) 복잡합니다. 대기열의 시간 복잡성은 일반 스택과 동일합니다.

0
PradGar

O(1)dequeue()은 pythonquick의 answer 와 동일합니다 :

// time: O(n), space: O(n)
enqueue(x):
    if stack.isEmpty():
        stack.Push(x)
        return
    temp = stack.pop()
    enqueue(x)
    stack.Push(temp)

// time: O(1)
x dequeue():
    return stack.pop()

O(1)enqueue() (이 답변에서는이 게시물에 언급되어 있지 않음)을 사용하면 백 트랙킹을 사용하여 거품을 내고 맨 아래 항목을 반환합니다.

// O(1)
enqueue(x):
    stack.Push(x)

// time: O(n), space: O(n)
x dequeue():
    temp = stack.pop()
    if stack.isEmpty():
        x = temp
    else:
        x = dequeue()
        stack.Push(temp)
    return x

분명히 비효율적이지만 우아하지만 그럼에도 불구하고 좋은 코딩 연습입니다.

0
hIpPy