STACK03 - Editorial

editorial
, ,
1

Problem Link - Implement Stack using Arrays

Problem Statement:

Here’s a simple exercise that involves implementing a stack.
In this exercise, you’ll implement a basic stack to reverse a string using the stack’s LIFO property.

Task
Update the functions push() and pop() within the class stack to output the reverses string.

Approach:

The key idea behind this code is to use a stack to reverse the characters of a given string. A stack works by adding elements to the top, and when elements are removed, they are popped from the top. This property is perfect for reversing a string because by pushing the characters onto the stack and then popping them off, we reverse the order.

Here’s how the code works:

  1. Pushing Characters:
  • We first push each character of the input string onto the stack, one by one.
  • The pushToStack function places each character at the top of the stack. Since stacks follow LIFO, the last character pushed will be the first to come out when we pop.
  1. Popping Characters:
  • After all characters are on the stack, we begin popping them off one by one. Each character popped from the stack is added to a new string (reversedString).
  • This process continues until the stack is empty. Since the stack pops characters in reverse order, the reversedString will hold the input string in reverse.

Time Complexity:

The time complexity is O(n) because we push and pop each character of the string once.

Space Complexity:

The space complexity is O(n) due to the stack and reversed string, both requiring space proportional to the input length.