ใช้สแต็กโดยใช้คิวเดียว


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน โฟร์ไคต์ Google อินโฟซิส MAQ ไมโครซอฟท์
คิว กอง

คำชี้แจงปัญหา

ปัญหา“ ติดตั้งสแต็กโดยใช้คิวเดี่ยว” ขอให้เราใช้โครงสร้างข้อมูลสแต็ก (LIFO) โดยใช้โครงสร้างข้อมูลคิว (FIFO)

ในที่นี้ LIFO หมายถึง Last In First Out ในขณะที่ FIFO หมายถึง First In First Out

ใช้สแต็กโดยใช้คิวเดียว

ตัวอย่าง

push(10)
push(20)
top()
pop()
push(30)
pop()
top()
Top : 20
Pop : 20
Pop : 30
Top : 10
push(1)
push(2)
top()
pop()
Top : 2
Pop : 2

คำอธิบาย

สมมติว่าเรามีคิวและตอนนี้เราเริ่มเพิ่มองค์ประกอบเข้าไป ดังนั้นสำหรับการเพิ่มหรือแทรกองค์ประกอบเข้าไป เราจะเรียกไฟล์ ฟังก์ชั่นผลักดัน

push (1) —————> สถานะปัจจุบันของคิว -> 1

push (2) —————> สถานะปัจจุบันของคิว -> 2,1

ในการดำเนินการนี้เราจะลบองค์ประกอบทั้งหมดที่อยู่ในคิวก่อนหน้านี้ จากนั้นเราแทรกองค์ประกอบใหม่ของเราในคิวว่าง หลังจากนั้นเราก็ดันองค์ประกอบที่ถูกลบอีกครั้งในลำดับเดียวกัน

เมื่อมองไปที่ด้านบน / ด้านหน้าของคิวจึงทำให้เราเป็น 2 ผลลัพธ์

q.top () = 2

ลองลบองค์ประกอบด้านบน ดังนั้นเราจึงลบ 2 ออกจากคิว

ดังนั้นหลังจากการลบสถานะปัจจุบันของคิว = 1

อัลกอริทึมเพื่อใช้งานสแต็กโดยใช้คิวเดียว

  1. เริ่มต้นคลาสสแต็กด้วยไฟล์ คิว โครงสร้างข้อมูลของ จำนวนเต็ม พิมพ์เป็นสมาชิกส่วนตัว เรายังกำหนด ดันป๊อปด้านบน และ ไม่มีข้อมูล เนื่องจากเป็นหน้าที่ของสมาชิกสาธารณะ
  2. สร้างฟังก์ชันว่าง () ส่งคืนจริงถ้าคิวว่างไม่งั้นจะส่งคืนเท็จ
  3. push () ยอมรับค่าจำนวนเต็ม สร้างตัวแปรจำนวนเต็มและจัดเก็บขนาดของคิวในตัวแปรและพุช / แทรกตัวแปรจำนวนเต็มในคิว
  4. สำรวจจาก 0 ไปยังขนาดก่อนหน้าของคิว ใส่ด้านหน้าปัจจุบันของคิวเข้ากับตัวเองและลบออก
  5. สร้างฟังก์ชัน pop () ซึ่งตรวจสอบว่าไม่มีองค์ประกอบในคิวหรือไม่จากนั้นพิมพ์“ ไม่มีองค์ประกอบ” และส่งกลับ -1 อื่นป๊อป / ลบองค์ประกอบด้านบน / ด้านหน้า
  6. เราสร้างฟังก์ชัน top () ซึ่งจะคืนค่า -1 หากไม่มีองค์ประกอบในคิวอื่นส่งกลับด้านหน้าของคิว

รหัส

โปรแกรม C ++ เพื่อติดตั้งสแต็กโดยใช้คิวเดียว

#include<bits/stdc++.h> 
using namespace std; 
  
class Stack{ 
    queue<int>q;
    
public: 
    void push(int val); 
    int pop(); 
    int top(); 
    bool empty(); 
}; 
  
void Stack::push(int val){ 
    int s = q.size(); 
  
    q.push(val); 
  
    for(int i=0; i<s; i++){ 
        q.push(q.front()); 
        q.pop(); 
    } 
} 
  
int Stack::pop(){ 
    if(q.empty()){ 
        cout<<"No elements\n";
        return -1;
    }    
    else{
        int x = q.front();
        q.pop();
        return x;
    }  
} 
  
int  Stack::top(){ 
    return (q.empty())? -1 : q.front(); 
} 
  
bool Stack::empty(){ 
    return (q.empty()); 
} 
  
int main(){ 
    Stack s;
    
    s.push(10); 
    s.push(20); 
    cout<<"Top : "<<s.top()<<endl; 
    cout<<"Pop : "<<s.pop()<<endl; 
    s.push(30); 
    cout<<"Pop : "<<s.pop()<<endl;
    cout<<"Top : "<<s.top()<<endl; 

    return 0; 
}
Top : 20
Pop : 20
Pop : 30
Top : 10

โปรแกรม Java เพื่อใช้งานสแต็กโดยใช้คิวเดียว

import java.util.LinkedList; 
import java.util.Queue; 
  
class stack{ 
    Queue<Integer> q = new LinkedList<Integer>(); 
      
    void push(int val){ 
        int size = q.size(); 
          
        q.add(val); 
          
        for(int i=0; i<size; i++){ 
            int x = q.remove(); 
            q.add(x); 
        } 
    } 
      
    int pop(){ 
        if (q.isEmpty()){ 
            System.out.println("No elements"); 
            return -1; 
        } 
        int x = q.remove(); 
        return x; 
    } 
      
    int top(){ 
        if (q.isEmpty()) 
            return -1; 
        return q.peek(); 
    } 
      
    boolean isEmpty(){ 
        return q.isEmpty(); 
    } 
  
    public static void main(String[] args){ 
        stack s = new stack(); 
        
        s.push(10); 
        s.push(20); 
        System.out.println("Top : " + s.top()); 
        System.out.println("Pop : " + s.pop()); 
        s.push(30); 
        System.out.println("Pop : " + s.pop()); 
        System.out.println("Top : " + s.top());
        
    } 
}
Top : 20
Pop : 20
Pop : 30
Top : 10

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

กำลังใช้ฟังก์ชัน push () O (n) เวลาในขณะที่ฟังก์ชัน pop () และ top () ต้องการเวลาคงที่เท่านั้นเช่น O (1). เนื่องจากในการผลักดันองค์ประกอบเราจะลบและเพิ่มจำนวนองค์ประกอบที่มีอยู่แล้ว สิ่งนี้ทำให้การดำเนินการทำงานในเวลาพหุนาม

ความซับซ้อนของอวกาศ

O (n) เนื่องจากเราใช้พื้นที่ในการจัดเก็บองค์ประกอบจำนวน n