대기열에서 스택 문제, 스택 데이터 구조의 표준 기능을 사용하여 큐의 다음 기능을 구현해야합니다.
- 대기열에 넣기 : 대기열 끝에 요소 추가
- 대기열에서 빼기 : 대기열 시작에서 요소 제거
차례
예
입력:
대기열에 넣기 (5)
대기열에 넣기 (11)
대기열에 넣기 (39)
Dequeue () // 5 반환
대기열에 넣기 (12)
Dequeue () // 11 반환
Dequeue () // 39 반환
출력:
5
11
39
암호알고리즘
대기열은 두 개의 스택을 사용하여 구현할 수 있습니다. 첫 번째는 대기열에 넣는 작업을 비용이 많이 들게하고 두 번째는 대기열에서 빼기 작업을 비용이 많이 들게하는 방법으로 스택을 사용하여 대기열을 구현할 수 있습니다.
스택을 사용하는 대기열에 대한 방법 1 (대기열에 추가 작업)
두 개의 스택 st1 및 st2를 만듭니다. 시각화 변발 st1에서 st1의 맨 위가 대기열의 맨 앞에 있고 st1에서 아래쪽으로 이동하는 것은 대기열에서 앞으로 이동하는 것과 유사합니다.
대기열에 넣기 (x)
x를 대기열 뒤쪽으로 푸시하는 것은 x를 스택 st1의 맨 아래로 푸시하는 것과 같습니다.
- st1에서 모든 요소를 제거하고 st2로 푸시하십시오.
- x를 st2로 푸시합니다.
- st2에서 모든 요소를 제거하고 st1로 다시 푸시하십시오.
시간 복잡성 = O (n) A
대기열에서 빼기 ()
대기열의 전면에서 요소를 제거하는 것은 스택 st1의 상단을 제거하는 것과 유사합니다. 따라서 st1이 비어 있지 않으면 st1의 상단을 팝하고 반환합니다.
시간 복잡성 = O (1)
방법 1의 전체 공간 복잡성 = O (N)
스택을 사용하는 대기열 용 JAVA 코드
import java.util.Stack;
public class QueueUsingStacks {
// Costly Enqueue Operation
private static Stack<Integer> st1;
private static Stack<Integer> st2;
private static void enqueue(int x) {
// remove all the elements from st1 and push them to st2
while (!st1.isEmpty()) {
st2.push(st1.pop());
}
// push x to st2
st2.push(x);
// remove all the elements from st2 and push them back to st1
while (!st2.isEmpty()) {
st1.push(st2.pop());
}
}
private static int dequeue() {
if (st1.isEmpty()) {
return -1;
}
// if st1 is not empty return and remove the top of st1
return st1.pop();
}
public static void main(String[] args) {
st1 = new Stack<>();
st2 = new Stack<>();
// Example
enqueue(5);
enqueue(11);
enqueue(39);
System.out.println(dequeue());
enqueue(12);
System.out.println(dequeue());
System.out.println(dequeue());
}
}
5 11 39
C ++ 코드
#include<bits/stdc++.h>
using namespace std;
// Costly Enqueue Operation
stack<int> st1;
stack<int> st2;
void enqueue(int x) {
// remove all the elements from st1 and push them to st2
while (!st1.empty()) {
int curr = st1.top();
st1.pop();
st2.push(curr);
}
// push x to st2
st2.push(x);
// remove all the elements from st2 and push them back to st1
while (!st2.empty()) {
int curr = st2.top();
st2.pop();
st1.push(curr);
}
}
int dequeue() {
if (st1.empty()) {
return -1;
}
// if st1 is not empty return and remove the top of st1
int top = st1.top();
st1.pop();
return top;
}
int main() {
// Example
enqueue(5);
enqueue(11);
enqueue(39);
cout<<dequeue()<<endl;
enqueue(12);
cout<<dequeue()<<endl;
cout<<dequeue()<<endl;
return 0;
}
5 11 39
스택을 사용하는 대기열에 대한 방법 2 (대기열 제거 작업)
두 개의 스택 st1 및 st2를 만듭니다. st1의 대기열 시각화, st1의 상단은 대기열의 뒤쪽을 나타내며, st1에서 위쪽으로 이동하는 것은 대기열에서 앞으로 이동하는 것과 유사합니다.
대기열에 넣기 (x)
x를 대기열 뒤쪽으로 푸시하는 것은 x를 stack_st1의 맨 위로 푸시하는 것과 유사합니다. 따라서 x를 st1의 맨 위로 밀어 넣으십시오.
시간 복잡성 = O (1)
대기열에서 빼기 ()
대기열의 전면에서 요소를 제거하는 것은 stack_st1의 맨 아래에서 요소를 제거하는 것과 유사합니다. 따라서 st1이 비어 있지 않으면
- st1에서 모든 요소를 제거하고 st2로 푸시하십시오.
- st2의 상단을 팝하고 가변 상단에 저장합니다.
- st2에서 모든 요소를 제거하고 st1로 다시 푸시하십시오.
- 돌아 가기
시간 복잡성 = O (N)
방법 2의 전체 공간 복잡성 = O (N)
JAVA 코드
import java.util.Stack;
public class QueueUsingStacks {
// Costly Dequeue Operation
private static Stack<Integer> st1;
private static Stack<Integer> st2;
private static void enqueue(int x) {
// push x to top of st1
st1.push(x);
}
private static int dequeue() {
if (st1.isEmpty()) {
return -1;
}
// if st1 is not empty
// remove all the elements from st1 and push them to st2
while (!st1.isEmpty()) {
st2.push(st1.pop());
}
// pop the top of st2 and store it in a variable top
int top = st2.pop();
// remove all the elements from st2 and push them back to st1
while (!st2.isEmpty()) {
st1.push(st2.pop());
}
// return top
return top;
}
public static void main(String[] args) {
st1 = new Stack<>();
st2 = new Stack<>();
// Example
enqueue(5);
enqueue(11);
enqueue(39);
System.out.println(dequeue());
enqueue(12);
System.out.println(dequeue());
System.out.println(dequeue());
}
}
5 11 39
C ++ 코드
#include<bits/stdc++.h>
using namespace std;
// Costly Dequeue Operation
stack<int> st1;
stack<int> st2;
void enqueue(int x) {
// push x to top of st1
st1.push(x);
}
int dequeue() {
if (st1.empty()) {
return -1;
}
// if st1 is not empty
// remove all the elements from st1 and push them to st2
while (!st1.empty()) {
int curr = st1.top();
st1.pop();
st2.push(curr);
}
// pop the top of st2 and store it in a variable top
int top = st2.top();
st2.pop();
// remove all the elements from st2 and push them back to st1
while (!st2.empty()) {
int curr = st2.top();
st2.pop();
st1.push(curr);
}
// return top
return top;
}
int main() {
// Example
enqueue(5);
enqueue(11);
enqueue(39);
cout<<dequeue()<<endl;
enqueue(12);
cout<<dequeue()<<endl;
cout<<dequeue()<<endl;
return 0;
}
5 11 39
