FOR FREE YEAR SOLVED
Double Stack
Back to ProgrammingDescription
Overview:
Stack: Stack is a linear data structure used to store a collection of data. Data is inserted using push()operation and deleted using pop() operation. Stack is a LIFO (Last in First out) data structure where data is removed from thetopof the stack only.
Double Stack: Double stack or stack growing towards each other can be implemented using an array where one stack starts from the leftmost position of the array and the second stack starts from the rightmost position of the array. Two tops of the stacks are separately maintained as illustrated in Figure below.
Prerequisites:
- Array
- Stack
Procedure:
Consider an array of size 6. Stack1 starts from leftmost of position of the array with top initialized to top1 = -1 and Stack1 starts from rightmost of position of the array with top initialized to top1 = size = 6. The procedure is illustrated in figure below.
Algorithm
Algorithm:
Input:
1. Elements of the stack
Output:
1. Result of push and pop operations.
Algo:
Step 1: Start
Step 2: Set int size 6
Step 3: Set top1 -1
Step 4: Set top2 size
Step 5: Defining push function
void push(int stack[], int item, int id)
Check if(top1 < top2 – 1)
Check if(id = 1)
Set top1 top1 + 1
Set stack[top1] item
Else
Set top2 top2 – 1
Set stack[top2] item
End if
Else
Display “Stack overflow”
End if
Step 6: Defining pop function
intpop(int stack[], int id)
Check if (id = 1)
Check if (top1 >= 0)
Set int item stack[top1]
Set top1top1 – 1
Display “Popped item:”, item
Else
Display “Stack underflow”
End if
Else if (id = 2)
Check if (top2 < size)
Set int item stack[top2]
Set top2 top2 + 1
Display “Popped item:”, item
Else
Display “Stack underflow”
End if
End if
Step 7: Defining display function
void display(int stack[])
Display “Stack 1:”
for i = top1 to i>= 0 repeat
Display stack[i], “à”
Set ii – 1
Display “Stack 2:”
for i = top2 to i< size repeat
Display stack[i], “à”
Set ii + 1
Step 8: Defining main function
Set int flag 1
Set int stack[size] null
While(flag) do
Display “1: Push to Stack 1 \n”
Display “2: Push to Stack 2 \n”
Display “3: Pop from Stack 1 \n”
Display “4: Pop from Stack 2 \n”
Display “5: Display stacks \n”
Display “6: Exit \n”
Read choice
Switch(choice)
Case 1:
Display “Enter item”
Read item
Call push(stack, item, 1)
Break
Case 2:
Display “Enter item”
Read item
Call push(stack, item, 2)
Break
Case 3:
Call pop(stack, 1)
Break
Case 4:
Call pop(stack, 2)
Break
Case 5:
Call display(stack)
Break
Case 6:
Set flag 0
break
default:
Display “Wrong Choice
End Switch
End While
Return 0
Step 9: Stop
