다음 기능을 구현하십시오. 스택 표준 작업을 사용하는 데이터 구조 변발,
- push (x) –> 요소 x를 스택으로 푸시
- pop () –> 스택 맨 위에있는 요소를 제거합니다.
- top () –> 스택 맨 위에있는 요소를 반환합니다.
- empty () –> 스택이 비어 있는지 여부를 반환합니다.
차례
예
입력:
stack.push (1);
stack.push (2);
stack.top (); // 2를 반환합니다.
stack.pop (); // 2를 반환합니다.
stack.empty (); // false 반환
출력:
2
2
그릇된
큐를 사용하여 스택을 구현하는 알고리즘
2 개의 큐 (예 : q1 및 q2)를 사용하여 스택을 구현할 수 있습니다.
푸시 (x)
q1의 끝에서 x를 누르고 최상위 변수에서 스택의 맨 위에 유지합니다.
의사 코드
void push(int x) {
q1.add(x);
top = x;
}
시간 복잡성 = O (1)
상단()
스택의 맨 위는 항상 맨 위 변수에 유지되므로 맨 위를 반환하면됩니다.
의사 코드
int top() {
return top;
}
시간 복잡성 = O (1)
빈()
큐 q1이 비어 있으면 스택이 비어 있습니다.
의사 코드
boolean empty() {
return q1.isEmpty();
}
시간 복잡성 = O (1)
팝()
큐 q1의 뒤쪽에는 스택의 맨 위가 포함되어 있으므로 q1의 크기를 n으로 둡니다.
- 큐 q1의 (n – 1) 요소를 큐 q2로 이동합니다.
- 또한 전송중인 현재 변수로 스택의 맨 위를 유지하십시오.
- 이제 q1에는 스택의 맨 위에있는 요소가 하나만 포함됩니다.
- 이 요소를 제거하고 일부 변수 (예 : ele)에 저장하십시오.
- 모든 요소를 큐 q2에서 큐 q1로 이동합니다.
- ele를 반환합니다.
시간 복잡성 = O (N)
여기서 n은 큐의 요소 수입니다.
예를 들어,
q1 = 3-> 5-> 7-> 1-> 2
q2 = 널
요소를 튀어 나오십시오.
- q1에서 q1로 이전 (n – 2)
q1 = 2 및 q2 = 3-> 5-> 7-> 1 - q1에서 요소를 제거하고 저장하십시오.
q1 = null 및 q2 = 3-> 5-> 7-> 1 및 ele = 2 - 모든 요소를 q2에서 q1로 이동합니다.
q1 = 3-> 5-> 7-> 1 및 q2 = null - ele를 반환합니다.
자세한 내용은 아래 이미지를 참조하십시오.
의사 코드
int pop() {
int n = q1.size();
for (int i = 0; i < n - 1; i++) {
int curr = q1.remove();
q2.add(curr);
top = curr;
}
int ele = q1.remove();
n = q2.size();
for (int i = 0; i < n; i++) {
q1.add(q2.remove());
}
return ele;
}
시간 복잡성 = O (N)
큐를 사용하여 스택을 구현하기위한 JAVA 코드
import java.util.Queue;
import java.util.LinkedList;
public class StackUsingQueues {
// Two queues to implement stack
private static Queue<Integer> q1 = new LinkedList<>();
private static Queue<Integer> q2 = new LinkedList<>();
// Stores the top element of stack
private static int top;
private static void push(int x) {
// Add element at rear of q1
q1.add(x);
// update top as current element
top = x;
}
private static int top() {
// Top stores the top of stack
return top;
}
private static int pop() {
int n = q1.size();
// Shift (n - 1) elements from q1 to q2 and update top as curr
// element transferred
for (int i = 0; i < n - 1; i++) {
int curr = q1.remove();
q2.add(curr);
top = curr;
}
// q1 contains only 1 element which is top of stack
// store the element in ele and remove it from q1
int ele = q1.remove();
n = q2.size();
// Again transfer back the elements from q2 to q1
for (int i = 0; i < n; i++) {
q1.add(q2.remove());
}
// return ele, this is the top of stack
return ele;
}
private static boolean empty() {
// If q1 is empty then stack is empty
return q1.isEmpty();
}
public static void main(String[] args) {
// Example
push(1);
push(2);
System.out.println(top());
System.out.println(pop());
System.out.println(empty());
}
}
큐를 사용하여 스택을 구현하기위한 C ++ 코드
#include <bits/stdc++.h>
using namespace std;
// Two queues to implement stack
queue<int> q1;
queue<int> q2;
// Stores the top element of stack
int Top;
void push(int x) {
// Add element at rear of q1
q1.push(x);
// update top as current element
Top = x;
}
int top() {
// Top stores the top of stack
return Top;
}
bool empty() {
// If q1 is empty then stack is empty
return q1.empty();
}
int pop() {
int n = q1.size();
// Shift (n - 1) elements from q1 to q2 and update top as curr
// element transferred
for (int i = 0; i < n - 1; i++) {
int curr = q1.front();
q1.pop();
q2.push(curr);
Top = curr;
}
// q1 contains only 1 element which is top of stack
// store the element in ele and remove it from q1
int ele = q1.front();
q1.pop();
n = q2.size();
// Again transfer back the elements from q2 to q1
for (int i = 0; i < n; i++) {
q1.push(q2.front());
q2.pop();
}
// return ele, this is the top of stack
return ele;
}
int main() {
// Example
push(1);
push(2);
cout<<top()<<endl;
cout<<pop()<<endl;
if (empty()) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
return 0;
}
2 2 false
