# Stacks

### Introduction

#### Stacks

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It means that the element which is inserted last is the first one to be removed. The two primary operations on a stack are push (inserting an element onto the stack) and pop (removing the top element from the stack).

Now, let's solve a question called "Valid Parentheses" using the stack concept.

Problem: Given a string containing only parentheses - '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Here's the solution code in Python with proper comments explaining each step:

```
class Stack:
def __init__(self):
self.stack = []
def push(self, x):
# Push the element onto the stack
self.stack.append(x)
def pop(self):
# Pop the top element from the stack if it's not empty
if not self.is_empty():
return self.stack.pop()
def peek(self):
# Return the top element from the stack without removing it
if not self.is_empty():
return self.stack[-1]
def is_empty(self):
# Check if the stack is empty
return len(self.stack) == 0
def is_valid_parentheses(s):
stack = Stack()
opening = ['(', '{', '[']
closing = [')', '}', ']']
for char in s:
if char in opening:
# Push opening parentheses onto the stack
stack.push(char)
elif char in closing:
# Check if the closing parentheses matches the top element of the stack
if stack.is_empty() or opening.index(stack.pop()) != closing.index(char):
return False
# The stack should be empty if all parentheses are matched correctly
return stack.is_empty()
```

In this code, we create a `Stack`

class with three main operations: `push`

, `pop`

, and `peek`

.

The `push`

operation appends the given element to the top of the stack.

The `pop`

operation removes and returns the top element from the stack if it's not empty.

The `peek`

operation returns the top element from the stack without removing it.

The `is_empty`

operation checks if the stack is empty by checking the length of the stack.

In the `is_valid_parentheses`

function, we create an instance of the `Stack`

class and initialize two lists, `opening`

and `closing`

, which contain the opening and closing parentheses respectively.

We iterate through each character in the input string `s`

. If the character is an opening parenthesis, we push it onto the stack. If the character is a closing parenthesis, we check if it matches the top element of the stack. If not, or if the stack is empty, we return `False`

as the parentheses are not valid.

After iterating through all the characters, we check if the stack is empty. If it's empty, it means all the parentheses are matched correctly, and we return `True`

. Otherwise, we return `False`

.

### Time and Space Complexity

The time complexity of the `push`

, `pop`

, `peek`

, and `is_empty`

operations in the stack implementation is O(1) since they involve simple operations on the stack list.

For the `is_valid_parentheses`

function, the time complexity is O(n), where n is the length of the input string `s`

. We iterate through each character in `s`

, and the operations performed in each iteration take constant time.

The space complexity of the implementation is O(n) in the worst case, where n is the length of the input string `s`

. This is because the stack can hold all the opening parentheses in the worst case scenario, where `s`

consists only of opening parentheses.

Let's solve a question that involves using the stack concept. The problem we'll solve is "Remove All Adjacent Duplicates in String".

Problem: Remove All Adjacent Duplicates in String

Given a string S, remove all adjacent duplicates from the string repeatedly until no adjacent duplicates are left. Return the final string after all such duplicate removals.

Example: Input: S = "abbaca" Output: "ca" Explanation: Step 1: Remove "bb" from "abbaca" to get "aaca". Step 2: Remove "aa" from "aaca" to get "ca".

Here's the Python code to solve the problem:

```
def removeDuplicates(S):
stack = []
for char in S:
if stack and stack[-1] == char:
stack.pop()
else:
stack.append(char)
return "".join(stack)
# Test the removeDuplicates function
S = "abbaca"
print("Input:", S)
print("Output:", removeDuplicates(S))
```

In this solution, we use a stack to keep track of the characters. We iterate through each character in the input string. If the stack is not empty and the current character is the same as the top of the stack, we remove the top character from the stack (as it forms an adjacent duplicate pair). Otherwise, we push the current character onto the stack. After iterating through all characters, we join the remaining characters in the stack to form the final string.

The time complexity of this solution is O(n), where n is the length of the input string. We iterate through each character in the string once. The space complexity is also O(n) in the worst case, as the stack may hold all the characters in the string if there are no adjacent duplicates.

Let's solve another LeetCode question that involves using the stack concept. The problem we'll solve is "Valid Parentheses" (LeetCode #20).

Problem: Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if:

- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.

Example 1: Input: s = "()" Output: True

Example 2: Input: s = "()[]{}" Output: True

Example 3: Input: s = "(]" Output: False

Here's the Python code to solve the problem:

```
def isValid(s):
stack = []
opening_brackets = "({["
closing_brackets = ")}]"
for char in s:
if char in opening_brackets:
stack.append(char)
elif char in closing_brackets:
if not stack:
return False
opening_bracket = stack.pop()
if opening_brackets.index(opening_bracket) != closing_brackets.index(char):
return False
return len(stack) == 0
# Test the isValid function
s = "()[]{}"
print("Input:", s)
print("Output:", isValid(s))
```

In this solution, we use a stack to keep track of the opening brackets encountered. We iterate through each character in the input string. If the character is an opening bracket, we push it onto the stack. If the character is a closing bracket, we check if the stack is empty (indicating a mismatch) or if the opening bracket at the top of the stack does not correspond to the closing bracket. If any of these conditions are met, the string is not valid, and we return False. At the end, we check if the stack is empty to ensure all opening brackets have been closed.

The time complexity of this solution is O(n), where n is the length of the input string. We iterate through each character in the string once. The space complexity is also O(n) in the worst case, as the stack may hold all the opening brackets if there are no closing brackets or if the string is entirely composed of opening brackets.