แนวคิด
สมมติว่าต้องการ implement stack ด้วย queue ต้องกำหนดเมธอดสำหรับ stack:
- push(x) - Push x เข้า stack
- pop() - ลบและคืนค่าองค์ประกอบบนสุดของ stack
- top() - คืนค่าองค์ประกอบบนสุดของ stack
- empty() - คืนค่าว่า stack ว่างหรือไม่
เช่น ถ้าเรียก push(10), push(20), แล้ว pop(), pop() ผลลัพธ์คือ 20, 10
วิธีแก้:
- กำหนด deque q
- ฟังก์ชัน push() รับ x: แทรก x ที่หน้าสุดของ q
- ฟังก์ชัน pop(): k := องค์ประกอบแรกของ q, ลบองค์ประกอบหน้าสุดออกจาก q, คืนค่า k
- ฟังก์ชัน top(): คืนค่าองค์ประกอบแรกของ q
- ฟังก์ชัน empty(): ถ้า q ว่าง: คืนค่า true, มิฉะนั้น: คืนค่า false
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class MyStack {
private:
deque<int> q;
public:
void push(int x){ q.push_front(x); }
int pop(){ int k = q.front(); q.pop_front(); return k; }
int top(){ return q.front(); }
bool empty(){ if (q.empty()) return true; else return false; }
};
main() {
MyStack ob;
ob.push(10);
ob.push(20);
cout << (ob.pop()) << endl;
cout << (ob.pop()) << endl;
}
อินพุต
push(10),push(20),pop(),pop()
เอาต์พุต
20 10
