{"id":9228,"date":"2022-08-25T08:52:48","date_gmt":"2022-08-25T08:52:48","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9228"},"modified":"2022-12-14T11:38:40","modified_gmt":"2022-12-14T11:38:40","slug":"implement-a-stack-using-single-queue","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/implement-a-stack-using-single-queue\/","title":{"rendered":"Implement a Stack Using Single Queue"},"content":{"rendered":"

\"\"<\/p>\n

Problem statement:<\/h3>\n

We have to build a stack with a single queue.<\/p>\n

What is a Stack?<\/h3>\n

Stack is a linear data structure<\/a> in which a user can insert and delete an element from the same end which is known as a top.
\nStack data structure follows LIFO property i.e. (Last in First out).
\nIn LIFO, the element which was inserted last will be the element which was removed first.
\nIn stack, the process of insertion is called push operation and the process of deletion of the element from the stack is known as pop.
\nAnd, we can easily keep track of the last element using a pointer called top.<\/p>\n

\"\"<\/p>\n

What is a Queue?<\/h3>\n

A Queue is a linear data structure in which a user can insert and delete an element on the different end.
\nThe process of insertion in the queue is known as enqueue<\/strong> and the element will be added on the rear end of the queue. The process of deletion in the queue is known as dequeue<\/strong> and the element will be deleted from the front end.<\/p>\n

How to implement the Stack using a Single Queue?<\/h3>\n

The Stack can be easily implemented by making the insertion operation costly. For the push operation i.e. the insertion operation, we will store the count of the elements (n) present in the stack. Then, the new element is inserted at the rear end. After that, we will iterate n times and on each iteration we will remove the first element from the stack and insert it at the rear end of the stack. This will make the insertion (push) operation costly, but will make the deletion (pop) efficient with O(1) time complexity as we are using a queue in which deletion of elements is done from the front end. And on the front end, the newly added element is there. So, on deletion the element which is added atlast will be deleted.<\/p>\n

Below are the complete steps:<\/p>\n

\/\/ Let new_element<\/strong> be the element to be pushed and st<\/strong> be the stack
\npush(st, new_element)<\/strong><\/p>\n

    \n
  1. Let the size of the queue be s.<\/li>\n
  2. Enqueue new_element to queue.<\/li>\n
  3. One by one dequeue s items from the queue and enqueue them. <\/li>\n<\/ol>\n

    \/\/ Removes an element from the queue
    \npop(st)<\/strong>
    \nDequeue an element from the queue.<\/p>\n\t\t\t\t\t\t