FOR FREE MATERIALS
Write a code to implement a stack using queue.
Back to ProgrammingDescription
Overview:
Stack: A Stack is a Last In First Out data structure. Here we will implement a Stack using a single Queue, which is a First In First Out data structure. Queue data structure has standard operations like enqueue() [Inserting the element in the queue] and dequeue() [Remove the element from the queue]. Using these two operations we will implement the operations of a stack, which arePush()and Pop() .
Algorithm
Algorithm:
Input:
1. Elements of the stack
Output:
1. 1. Result of push and pop operations.
Algo:
Step 1: Start
Step 2: Define user defined datatype queue with integer pointer *arr, integer rear, front, count, max
Step 3: Defining queueCount function
int queueCount(queue *q)
return q.count
Step 4: Defining queueCreate function
queue* queueCreate(int n)
Set queue *q null
Set q GetNode(queue)
Check if(q = null)
Display “Unable to create stack”
Return null
End if
Set q.max n
Set q.arr GetNode(int * n)
Set q.rear n – 1
Set q.front n – 1
Return q
Step 5: Defining enqueue function
void enqueue(queue *q, int v)
Check if(q.count = q.max)
Display “Stack is full”
Return
End if
Set q.rear (q.rear + 1) mod q.max
Set q.arr[q.rear] v
Set q.count q.count + 1
Step 6: Defining dequeue function
int dequeue(queue *q)
Set int val null
Check if(q.count = 0)
Display “Stack is Empty”
Return 0
End if
Set q.front (q.front + 1) mod q.max
Set val q.arr[q.front]
Set q.count q.count – 1
Return val
Step 7: Defining queueIsEmpty function
int queueIsEmpty(queue *q)
Return (q.count = 0)
Step 8: Defining queueDisplay function
void queueDisplay(queue *q)
Set int i (q.front + 1) mod q.max
Set int n Call queueCount(q)
While (n) do
Display (q.arr[i])
Check if(i = q.max – 1)
Set i 0
Else
Set i i + 1
End if
Set n n – 1
End While
Step 9: Defining stackPush function
void stackPush(queue *q, int v)
Call enqueue(q, v)
Step 10: Defining stackPop function
int stackPop(queue *q)
Set int i null
Set int n Call queueCount(q)
Set int val null
for i = 0 to i < (n – 1) repeat
Set val Call dequeue(q)
Call enqueue(q, val)
Set val Call dequeue(q)
Return val
Step 11: Defining main function
Set queue *q null
Display “Enter the maximum size of the stack”
Read n
Set q Call queueCreate(n)
While(1) do
Display “Choose any of the options:”
Display “\n1. Push \n2. Pop \n3. Display \n4. Exit”
Display “\nOption: “
Read option
Switch(option)
Case 1:
Display “Enter the value to Push”
Read x
Call stackPush(q, x)
Display “The current values in the stack: “
Call queueDisplay(q)
Break
Case 2:
Set x Call stackPop(q)
Display “The current values in the stack: “
Call queueDisplay(q)
Check if(x = 0)
Display “Stack is Empty”
Else
Display “Popped value” x
End if
Break
Case 3:
Display “The current values in the stack: “
Call queueDisplay(q)
Break
Case 4:
Display “Exiting”
Return 0
default:
Display “Exiting”
Return 0
End Switch
End While
Return 0
Step 12: Stop
Code
Applications:
a. Stack is used in Infix to Postfix or Infix to Prefix Conversion.
b. Its used for Postfix or Prefix Evaluation.
c. it is also used for Backtracking Procedure.
Advantage:
1. A single queue is used here to implement the stack, so no extra space is needed here.
2. Dynamic memory allocation is used here.
Disadvantage:
2. The time complexity for the pop opeartion is comparetively high,O(n) .
Time complexity:
For the push() opeartion, we just need to do the enqueue()operation once, thus the time complexity for push operation is O(1).
But, for the pop() opeartion, we need to do the dequeue() opeartion n times and the enqueue() opeartion (n-1) times , thus the time complexity for pop operation is O(n).
Space Complexity:
No extra space is required in this code, so space complexity O(1) .
