Stack With Singly Linked List

Stack with Singly Linked List: A stack is a data structure that follows the Last-In-First-Out (LIFO) principle, meaning the last element inserted is the first one to be removed. In a singly linked list implementation of a stack, each node in the list contains a value and a reference to the next node. The top of the stack is represented by the head node.

Example: Consider the following singly linked list representation of a stack:

Stack:  5 -> 3 -> 8 -> 2 -> None

In this example, the top of the stack is the node containing the value 5. The node with value 3 is below it, followed by the node with value 8, and so on.

Implementation Steps:

  1. Define a class Node that represents a node in the singly linked list. Each node should contain a value and a next reference.
  2. Define a class Stack that represents the stack. It should have an instance variable top to keep track of the top of the stack.
  3. Implement the push method in the Stack class to add a new element to the top of the stack. This involves creating a new node with the given value and updating the top reference.
  4. Implement the pop method in the Stack class to remove and return the element from the top of the stack. This involves updating the top reference to the next node and returning the value of the original top node.
  5. Implement the peek method in the Stack class to return the value of the element at the top of the stack without removing it. This involves returning the value of the top node.
  6. Implement the is_empty method in the Stack class to check if the stack is empty. This involves checking if the top reference is None.

Now let's solve the "Valid Parentheses" problem using the stack implemented with a singly linked list:


class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class Stack:
    def __init__(self):
        self.top = None

    def push(self, value):
        new_node = Node(value)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if self.is_empty():
            return None
        popped_value = self.top.value
        self.top = self.top.next
        return popped_value

    def peek(self):
        return self.top.value if self.top else None

    def is_empty(self):
        return self.top is None


def is_valid(s):
    stack = Stack()

    for char in s:
        if char in '({[':
            stack.push(char)
        elif char in ')}]':
            if stack.is_empty() or not is_matching(stack.peek(), char):
                return False
            stack.pop()

    return stack.is_empty()


def is_matching(opening, closing):
    return (opening == '(' and closing == ')') or \
           (opening == '{' and closing == '}') or \
           (opening == '[' and closing == ']')


# Test the solution
s1 = "()[]{}"
print("Is valid:", is_valid(s1))  # Output: True

s2 = "([)]"
print("Is valid:", is_valid(s2))  # Output: False

s3 = "{[]}"
print("Is valid:", is_valid(s3))  # Output: True

Explanation:

  1. We define the Node class to represent a node in the singly linked list. Each node has a value and a reference to the next node.
  2. The Stack class is defined with a top reference to keep track of the top of the stack. It has methods to push, pop, peek, and check if the stack is empty.
  3. The is_valid function takes a string s as input and checks if the parentheses are valid. It uses the stack to push opening parentheses and pop when encountering closing parentheses.
  4. We iterate through each character in the input string. If the character is an opening parentheses, we push it onto the stack. If it is a closing parentheses, we check if it matches the opening parentheses at the top of the stack. If not, we return False.
  5. After iterating through all characters, we check if the stack is empty. If it is, all parentheses are properly matched, and we return True. Otherwise, we return False.

Time and Space Complexity: 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 exactly once. The space complexity is also O(n) as we may store opening parentheses on the stack, which can have a maximum size of n/2 for a valid string.

Let's solve another question using the stack implemented with a singly linked list. The problem we'll solve is "Daily Temperatures."

Problem: Daily Temperatures Given a list of daily temperatures, return a list where, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, consider it as 0.

Example:


Input: temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Explanation: For the first day (73), the next day (74) has a higher temperature, so the 
result is 1. For the second day (74), the next day (75) has a higher temperature, so the 
result is 1. For the third day (75), the next higher temperature is on the 7th day (76), 
so the result is 4. And so on.

Solution: We'll use the stack implemented with a singly linked list to solve this problem.


class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class Stack:
    def __init__(self):
        self.top = None

    def push(self, value):
        new_node = Node(value)
        new_node.next = self.top
        self.top = new_node

    def pop(self):
        if self.is_empty():
            return None
        popped_value = self.top.value
        self.top = self.top.next
        return popped_value

    def peek(self):
        return self.top.value if self.top else None

    def is_empty(self):
        return self.top is None


def daily_temperatures(temperatures):
    stack = Stack()
    result = [0] * len(temperatures)

    for i, temp in enumerate(temperatures):
        while not stack.is_empty() and temp > temperatures[stack.peek()]:
            prev_index = stack.pop()
            result[prev_index] = i - prev_index

        stack.push(i)

    return result


# Test the solution
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
result = daily_temperatures(temperatures)
print("Result:", result)  # Output: [1, 1, 4, 2, 1, 1, 0, 0]

Explanation:

  1. We define the Node class to represent a node in the singly linked list. Each node has a value and a reference to the next node.
  2. The Stack class is defined with a top reference to keep track of the top of the stack. It has methods to push, pop, peek, and check if the stack is empty.
  3. The daily_temperatures function takes a list of temperatures as input and returns a list representing the number of days we need to wait until a warmer temperature for each day.
  4. We iterate through each temperature in the input list. For each temperature, we compare it with the temperatures on the stack's top. If the current temperature is higher, we update the result for the previous indices and pop them from the stack. We then push the current index onto the stack.
  5. After iterating through all the temperatures, we return the resulting list.

The time complexity of this solution is O(n), where n is the number of temperatures. The space complexity is O(n) as well, since we use the stack to store the indices.

Next Post Previous Post