Question

Using a single queue (linkedQueue), re-implement the concept of Stack ADT, what is the complexity of the method push, pop, top, isEmpty, and size. You should not use any extra data structure.

Related codes:

public interface Stack<E> {

int size( );

boolean isEmpty( );

void push(E e);

E top( );

E pop( );

}

public class LinkedStack<E> implements Stack<E> {

private SinglyLinkedList<E> list = new SinglyLinkedList<>( );

   public LinkedStack( ) { }

   public int size( ) { return list.size( ); }

   public boolean isEmpty( ) { return list.isEmpty( ); }

   public void push(E element) { list.addFirst(element);}

   public E top( ) { return list.first( ); }

   public E pop( ) { return list.removeFirst( ); }

   }

---------------------------------------

public interface Queue<E> {

int size( );

boolean isEmpty( );

void enqueue(E e);

E first( );

E dequeue( );

}

public class LinkedQueue<E> implements Queue<E> {

private SinglyLinkedList<E> list = new SinglyLinkedList<>( ); // an empty list

public LinkedQueue( ) { } // new queue relies on the initially empty list

public int size( ) { return list.size( ); }

public boolean isEmpty( ) { return list.isEmpty( ); }

public void enqueue(E element) { list.addLast(element); }

public E first( ) { return list.first( ); }

public E dequeue( ) { return list.removeFirst( ); }

}

Answer 1

Based on the format given, I shall give my own code similar to it.

There are two ways to implement a stack using queue, in one approach, the time complexity of push function increases while in the other, pop's time complexity rises.

1.

In this approach, if we have to push an element, we push it to q2 and then pop all the elements of q1 and push into q2 and then swap names of q1 and q2 which takes order of O(n). top, isempty and size are all of order O(1)

For pop(), we simply pop the element from q1 and return it in order of O(1)

import java.util.*; 

class Main { 

        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()); 
        } 
} 

2.

For push(), we simply push the element into q1 in order of O(1)

In this approach, if we have to pop an element, we dequeue everything from q1 and push it to q2 and the last item dequeued from q1 is our desired element so we return it. then we swap the names of q1 and q2 and all this takes order of O(n) while top, isempty and size are all of order O(1)

import java.util.*; 

class Main { 
        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()); 
        } 
}