پیاده سازی پشته با استفاده از صف — به زبان ساده

در این مطلب، چگونگی پیاده سازی پشته با استفاده از صف بیان شده است. یک ساختار داده صف موجود است که از عملیات استانداردی مانند ()enqueue و ()dequeue پشتیبانی می‌کند. نیاز به پیاده‌سازی ساختار داده «پشته» (Stack) با استفاده از صف و عملیات آن است. باید توجه داشت که امکان پیاده سازی پشته با استفاده از صف، وجود دارد. برای این کار، نیاز به دو صف است.

راهکار اول: پر هزینه کردن عملیات

این روش، اطمینان حاصل می‌کند که عناصری که جدید به پشته وارد شده‌اند، همیشه در ابتدای q1 قرار دارند، بنابراین، از عملیات pop فقط در صف q1 استفاده می‌شود. صف q2 برای قرار دادن هر عنصر جدید در جلوی q1 مورد استفاده قرار می‌گیرد.

فیلم آموزش مبانی برنامه نویسی – الگوریتم و فلوچارت با رویکرد حل مساله در فرادرس

کلیک کنید

1. مراحل عملیات (push(s,x در ادامه بیان شده‌اند.
   • x را در صف q2 قرار بده.
   • همه چیز را یک به یک از q1 خالی کن و در q2 قرار بده.
   • نام q1 و q2 را جا به جا کن.
2. عملیات (pop(s در ادامه بیان شده است.
   • یک عنصر را از q۱ خارج کن و آن را بازگردان.

در ادامه، پیاده‌سازی رویکرد بالا، در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «جاوا» (Java)، «پایتون» (Python) و «سی‌شارپ» (#C) انجام شده است.

پیاده سازی پشته با استفاده از صف در ++C

فیلم آموزش ساختمان داده ها و پیاده سازی در سی پلاس پلاس C++‎ در فرادرس

کلیک کنید

/* Program to implement a stack using  
two queue */
#include<bits/stdc++.h> 
  
using namespace std; 
  
class Stack 
{  
    // Two inbuilt queues 
    queue<int> q1, q2; 
      
    // To maintain current number of 
    // elements 
    int curr_size; 
  
    public: 
    Stack() 
    { 
        curr_size = 0; 
    } 
  
    void push(int x) 
    { 
        curr_size++; 
  
        // Push x first in empty q2 
        q2.push(x); 
  
        // Push all the remaining  
        // elements in q1 to q2.  
        while (!q1.empty()) 
        { 
            q2.push(q1.front()); 
            q1.pop(); 
        } 
  
        // swap the names of two queues 
        queue<int> q = q1; 
        q1 = q2; 
        q2 = q; 
    } 
  
    void pop(){ 
  
        // if no elements are there in q1  
        if (q1.empty()) 
            return ; 
        q1.pop(); 
        curr_size--; 
    } 
  
    int top() 
    { 
        if (q1.empty()) 
            return -1; 
        return q1.front(); 
    } 
  
    int size() 
    { 
        return curr_size; 
    } 
}; 
  
// Driver code 
int main() 
{ 
    Stack s; 
    s.push(1); 
    s.push(2); 
    s.push(3); 
  
    cout << "current size: " << s.size()  
         << endl; 
    cout << s.top() << endl; 
    s.pop(); 
    cout << s.top() << endl; 
    s.pop(); 
    cout << s.top() << endl; 
  
    cout << "current size: " << s.size()  
         << endl; 
    return 0; 
} 
// This code is contributed by Chhavi

پیاده سازی پشته با استفاده از صف در جاوا

فیلم آموزش برنامه نویسی جاوا Java در فرادرس

کلیک کنید

/* Java Program to implement a stack using  
two queue */
import java.util.*; 
  
class GfG { 
  
static class Stack  
{  
    // Two inbuilt queues  
    static Queue<Integer> q1 = new LinkedList<Integer>(); 
    static Queue<Integer> q2 = new LinkedList<Integer>();  
      
    // To maintain current number of  
    // elements  
    static int curr_size;  
  
    Stack()  
    {  
        curr_size = 0;  
    }  
  
    static void push(int x)  
    {  
        curr_size++;  
  
        // Push x first in empty q2  
        q2.add(x);  
  
        // Push all the remaining  
        // elements in q1 to q2.  
        while (!q1.isEmpty())  
        {  
            q2.add(q1.peek());  
            q1.remove();  
        }  
  
        // swap the names of two queues  
        Queue<Integer> q = q1;  
        q1 = q2;  
        q2 = q;  
    }  
  
    static void pop(){  
  
        // if no elements are there in q1  
        if (q1.isEmpty())  
            return ;  
        q1.remove();  
        curr_size--;  
    }  
  
    static int top()  
    {  
        if (q1.isEmpty())  
            return -1;  
        return q1.peek();  
    }  
  
    static int size()  
    {  
        return curr_size;  
    }  
};  
  
// driver code  
public static void main(String[] args)  
{  
    Stack s = new Stack();  
    s.push(1);  
    s.push(2);  
    s.push(3);  
  
    System.out.println("current size: " + s.size());  
    System.out.println(s.top());  
    s.pop();  
    System.out.println(s.top());  
    s.pop();  
    System.out.println(s.top());  
  
    System.out.println("current size: " + s.size());  
} 
}  
// This code is contributed by Prerna  

پیاده سازی پشته با استفاده از صف در پایتون ۳

فیلم آموزش الگوریتم های مرتب سازی در زبان برنامه نویسی پایتون با مثال (رایگان) در فرادرس

کلیک کنید

# Program to implement a stack using  
# two queue  
from queue import Queue 
  
class Stack: 
      
    def __init__(self): 
          
        # Two inbuilt queues  
        self.q1 = Queue() 
        self.q2 = Queue()  
              
        # To maintain current number  
        # of elements 
        self.curr_size = 0
  
    def push(self, x): 
        self.curr_size += 1
  
        # Push x first in empty q2  
        self.q2.put(x)  
  
        # Push all the remaining  
        # elements in q1 to q2.  
        while (not self.q1.empty()): 
            self.q2.put(self.q1.queue[0])  
            self.q1.get() 
  
        # swap the names of two queues  
        self.q = self.q1  
        self.q1 = self.q2  
        self.q2 = self.q 
  
    def pop(self): 
  
        # if no elements are there in q1  
        if (self.q1.empty()):  
            return
        self.q1.get()  
        self.curr_size -= 1
  
    def top(self): 
        if (self.q1.empty()): 
            return -1
        return self.q1.queue[0] 
  
    def size(self): 
        return self.curr_size 
  
# Driver Code  
if __name__ == '__main__': 
    s = Stack() 
    s.push(1)  
    s.push(2)  
    s.push(3)  
  
    print("current size: ", s.size()) 
    print(s.top())  
    s.pop()  
    print(s.top())  
    s.pop()  
    print(s.top())  
  
    print("current size: ", s.size()) 
  
# This code is contributed by PranchalK

پیاده سازی پشته با استفاده از صف در #C

فیلم آموزش کاربردی برنامه نویسی سی شارپ #C – مقدماتی در فرادرس

کلیک کنید

/* C# Program to implement a stack using  
two queue */
using System; 
using System.Collections; 
  
class GfG  
{ 
  
public class Stack  
{  
    // Two inbuilt queues  
    public Queue q1 = new Queue(); 
    public Queue q2 = new Queue();  
      
    // To maintain current number of  
    // elements  
    public int curr_size;  
  
    public Stack()  
    {  
        curr_size = 0;  
    }  
  
    public void push(int x)  
    {  
        curr_size++;  
  
        // Push x first in empty q2  
        q2.Enqueue(x);  
  
        // Push all the remaining  
        // elements in q1 to q2.  
        while (q1.Count > 0)  
        {  
            q2.Enqueue(q1.Peek());  
            q1.Dequeue();  
        }  
  
        // swap the names of two queues  
        Queue q = q1;  
        q1 = q2;  
        q2 = q;  
    }  
  
    public void pop() 
    {  
  
        // if no elements are there in q1  
        if (q1.Count == 0)  
            return ;  
        q1.Dequeue();  
        curr_size--;  
    }  
  
    public int top()  
    {  
        if (q1.Count == 0)  
            return -1;  
        return (int)q1.Peek();  
    }  
  
    public int size()  
    {  
        return curr_size;  
    }  
};  
  
// Driver code  
public static void Main(String []args)  
{  
    Stack s = new Stack();  
    s.push(1);  
    s.push(2);  
    s.push(3);  
    Console.WriteLine("current size: " + s.size());  
    Console.WriteLine(s.top());  
    s.pop();  
    Console.WriteLine(s.top());  
    s.pop();  
    Console.WriteLine(s.top());  
    Console.WriteLine("current size: " + s.size());  
} 
}  
  
// This code is contributed by Arnab Kundu

خروجی قطعه کدهای بالا به صورت زیر است.

current size: 3
3
2
1
current size: 1

روش دوم: پر هزینه کردن عملیات POP

در عمل Push، عنصر جدید همیشه در صف q1 قرار می‌گیرد. در عملیات ()pop، اگر q2 خالی باشد، همه عناصر به جز آخرین عنصر، به q2 انتقال پیدا می‌کنند. در نهایت، آخرین عنصر از صف q1 خارج و بازگردانده می‌شود.

فیلم آموزش ساختمان داده ها در فرادرس

کلیک کنید

1. عملیات (push(s, x
   • x را در صف q1 قرار بده (فرض می‌شود که سایز q1 نامحدود است).
2. عملیات (pop(s
   • یک به یک عناصر موجود در صف q1، به جز آخرین عنصر را خالی کن و در q2 قرار بده.
   • آخرین عنصر از q1 را خارج کن؛ عنصر خارج شده، نتیجه است. آن را ذخیره کن.
   • عنصر ذخیره شده در گام قبلی را بازگردان.

پیاده سازی پشته با استفاده از صف در ++C

/* Program to implement a stack  
using two queue */
#include<bits/stdc++.h> 
using namespace std; 
  
class Stack 
{ 
    queue<int> q1, q2; 
    int curr_size; 
  
    public: 
    Stack() 
    { 
        curr_size = 0; 
    } 
  
    void pop() 
    { 
        if (q1.empty()) 
            return; 
  
        // Leave one element in q1 and  
        // push others in q2. 
        while (q1.size() != 1) 
        { 
            q2.push(q1.front()); 
            q1.pop(); 
        } 
  
        // Pop the only left element  
        // from q1 
        q1.pop(); 
        curr_size--; 
  
        // swap the names of two queues 
        queue<int> q = q1; 
        q1 = q2; 
        q2 = q; 
    } 
  
    void push(int x) 
    { 
        q1.push(x); 
        curr_size++; 
    } 
  
    int top() 
    { 
        if (q1.empty()) 
            return -1; 
  
        while( q1.size() != 1 ) 
        { 
           q2.push(q1.front()); 
           q1.pop(); 
        }  
          
        // last pushed element 
        int temp = q1.front(); 
          
        // to empty the auxiliary queue after 
        // last operation 
        q1.pop(); 
       
        // push last element to q2 
        q2.push(temp); 
  
        // swap the two queues names 
        queue<int> q = q1; 
        q1 = q2; 
        q2 = q; 
        return temp; 
    } 
  
    int size() 
    { 
        return curr_size; 
    } 
}; 
  
// Driver code 
int main() 
{ 
    Stack s; 
    s.push(1); 
    s.push(2); 
    s.push(3); 
    s.push(4); 
  
    cout << "current size: " << s.size()  
         << endl; 
    cout << s.top() << endl; 
    s.pop(); 
    cout << s.top() << endl; 
    s.pop(); 
    cout << s.top() << endl; 
    cout << "current size: " << s.size()  
         << endl; 
    return 0; 
} 
// This code is contributed by Chhavi

پیاده سازی پشته با استفاده از صف در جاوا

فیلم آموزش ساختمان داده ها در فرادرس

کلیک کنید

/* Java Program to implement a stack  
using two queue */
import java.util.*; 
  
class Stack 
{ 
    Queue<Integer> q1 = new LinkedList<>(), q2 = new LinkedList<>(); 
    int curr_size; 
  
    public Stack() 
    { 
        curr_size = 0; 
    } 
  
    void remove() 
    { 
        if (q1.isEmpty()) 
            return; 
  
        // Leave one element in q1 and  
        // push others in q2. 
        while (q1.size() != 1) 
        { 
            q2.add(q1.peek()); 
            q1.remove(); 
        } 
  
        // Pop the only left element  
        // from q1 
        q1.remove(); 
        curr_size--; 
  
        // swap the names of two queues 
        Queue<Integer> q = q1; 
        q1 = q2; 
        q2 = q; 
    } 
  
    void add(int x) 
    { 
        q1.add(x); 
        curr_size++; 
    } 
  
    int top() 
    { 
        if (q1.isEmpty()) 
            return -1; 
  
        while( q1.size() != 1 ) 
        { 
            q2.add(q1.peek()); 
            q1.remove(); 
        }  
          
        // last pushed element 
        int temp = q1.peek(); 
          
        // to empty the auxiliary queue after 
        // last operation 
        q1.remove(); 
      
        // push last element to q2 
        q2.add(temp); 
  
        // swap the two queues names 
        Queue<Integer> q = q1; 
        q1 = q2; 
        q2 = q; 
        return temp; 
    } 
  
    int size() 
    { 
        return curr_size; 
    } 
  
// Driver code 
public static void main(String[] args)  
{ 
    Stack s = new Stack(); 
    s.add(1); 
    s.add(2); 
    s.add(3); 
    s.add(4); 
  
    System.out.println("current size: " + s.size()); 
    System.out.println(s.top() ); 
    s.remove(); 
    System.out.println(s.top() ); 
    s.remove(); 
    System.out.println(s.top() ); 
    System.out.println("current size: " +s.size()); 
} 
} 
  
// This code is contributed by Princi Singh

پیاده سازی پشته با استفاده از صف در #C

فیلم آموزش کاربردی برنامه نویسی سی شارپ C#‎ در فرادرس

کلیک کنید

using System; 
using System.Collections; 
class GfG 
{ 
    public class Stack 
    { 
        public Queue q1 = new Queue(); 
        public Queue q2 = new Queue(); 
        //Just enqueue the new element to q1 
        public void Push(int x) => q1.Enqueue(x); 
  
        //move all elements from q1 to q2 except the rear of q1.  
        //Store the rear of q1 
        //swap q1 and q2 
        //return the stored result 
        public int Pop() 
        { 
            if (q1.Count == 0) 
                return -1; 
            while (q1.Count > 1) 
            { 
                q2.Enqueue(q1.Dequeue()); 
            } 
            int res = (int)q1.Dequeue(); 
            Queue temp = q1; 
            q1 = q2; 
            q2 = temp; 
            return res; 
        } 
  
        public int Size() => q1.Count; 
  
        public int Top() 
        { 
            if (q1.Count == 0) 
                return -1; 
            while (q1.Count > 1) 
            { 
                q2.Enqueue(q1.Dequeue()); 
            } 
            int res = (int)q1.Dequeue(); 
            q2.Enqueue(res); 
            Queue temp = q1; 
            q1 = q2; 
            q2 = temp; 
            return res; 
        } 
    }; 
    public static void Main(String[] args) 
    { 
        Stack s = new Stack(); 
    s.Push(1); 
    Console.WriteLine("Size of Stack: " + s.Size() + "\tTop : " + s.Top()); 
    s.Push(7); 
    Console.WriteLine("Size of Stack: " + s.Size() + "\tTop : " + s.Top()); 
    s.Push(9); 
    Console.WriteLine("Size of Stack: " + s.Size() + "\tTop : " + s.Top()); 
  
    s.Pop(); 
    Console.WriteLine("Size of Stack: " + s.Size() + "\tTop : " + s.Top()); 
    s.Pop(); 
    Console.WriteLine("Size of Stack: " + s.Size() + "\tTop : " + s.Top()); 
  
    s.Push(5); 
    Console.WriteLine("Size of Stack: " + s.Size() + "\tTop : " + s.Top()); 
    } 
} 
//Submitted by Sakti Prasad 
  
//Size of Stack: 1    Top : 1 
//Size of Stack: 2    Top : 7 
//Size of Stack: 3    Top : 9 
//Size of Stack: 2    Top : 7 
//Size of Stack: 1    Top : 1 
//Size of Stack: 2    Top : 5

خروجی قطعه کدهای بالا، به صورت زیر است.

current size: 4
4
3
2
current size: 2

فیلم مجموعه آموزش ساختمان داده و طراحی الگوریتم در فرادرس

کلیک کنید

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده

^^