CREATE OWN LIBRARY
String Palindrome using 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 the topof the stack only.
String palindrome using Stack: To check string palindrome using stack, we push every character till the middle character of the string onto the stack. Then, we iterate from the middle character ( or after the middle character if the length of the string is odd ) till the last character. In every iteration we pop a character from the stack and compare it with the character in the string in the current iteration.
Procedure:
Let us consider the string “MADAM”. The procedure for checking if it is palindrome is illustrated in the diagram below.
Prerequisites:
- Array
- Stack
Algorithm
Algorithm:
Input:
1. A string
Output:
1. Displays if enteredstring is palindrome or not
Algo:
Step 1: Start
Step 2: Set int top <= -1
Step 3: Defining push function
void push(char stack[], char ch)
Set top <= top + 1
Set stack[top] <= ch
Step 4: Defining pop function
char pop(char stack[])
Set temp <= stack[top]
Set top <= top – 1
Return temp
Step 5: Defining input function
void input(char str[])
Display “Enter Input String”
Read str
Display “Input String: \n”
Display str
Step 6: Defining checkPalindrome function
int checkPalindrome(char str[], char stack[])
Set int i <= 0
Set char ch <= null
Set int mid <= length(str) / 2
Set int flag <= 1
While (i < mid) do
Call push(stack, str[i])
Set i <= i + 1
End while
Check if ((length(str) mod 2) ≠ 0)
Set i <= i + 1
End if
While (str[i]) do
Set ch <= Call pop(stack)
Check if (ch ≠ str[i])
Set flag ß0
Break
End if
Set i <= i + 1
End while
Check if (flag = 1)
Display “Palindrome string”
Else
Display “Non palindrome string”
End if
Step 7: Defining main function
Set char str[20] <= null
Set char *stack <= null
Call input(str)
Set stack <= GetNode(length(str) * char)
Call chackPalindrome(str, stack)
Step 8: Stop
Code
Characteristics:
- A linked list implementation of the stack can be used for dynamic stack.
- The algorithm uses extra space for the stack, hence, the space complexity is O(n) where n is size of the stack.
- The algorithm has linear time complexity O(n) where n is the length of the string.
Advantage:
- The algorithm has linear time complexity O(n) where n is the length of the string.
- Efficient memory utilization since the stacks grow towards each other. Hence, the size of each stack is not fixed and can have maximum size = size of the array
Disadvantage:
- The algorithm uses extra space for the stack, hence, the space complexity is O(n) where n is size of the stack.
- Since, the algorithm uses array implementation of the stack, memory utilization is not efficient
Complexity:
Time Complexity:
Push()operations and Pop() operations take constant time O(1). The checkPalindrome() function iterates over every character and calls the push()and pop() operations. Hence, the total time complexity isO(n) + O(1) + O(1) = O(n) where n is the length of the string.
Space Complexity:
The algorithm uses extra space for the stack, hence, the space complexity isO(n) where n is size of the stack.
