Stack With Doubly Linked List

Stack with Doubly Linked List:

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle.
A doubly linked list is a linked data structure where each node contains a reference to the previous and next node in the list.
Implementing a stack using a doubly linked list allows for efficient insertion and deletion at both ends of the list.

Implementation Steps:

Create a Node class: Define a class to represent each node in the doubly linked list. Each node should have data and references to the previous and next nodes.
Create a Stack class: Define a class to represent the stack. The stack should have references to the head and tail nodes of the doubly linked list.
Implement stack operations: Define methods in the Stack class to perform stack operations such as push (inserting an element), pop (removing the top element), and peek (getting the top element without removing it).
Handle edge cases: Check for empty stack conditions and handle them accordingly.

Here's an example of implementing a stack with a doubly linked list in Python:


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


class Stack:
    def __init__(self):
        self.head = None
        self.tail = None

    def push(self, data):
        # Create a new node
        new_node = Node(data)

        if not self.head:
            # If stack is empty, set new node as head and tail
            self.head = new_node
            self.tail = new_node
        else:
            # Add new node at the top of the stack
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node

    def pop(self):
        if not self.head:
            # Stack is empty
            return None

        # Remove the top node from the stack
        popped_node = self.tail

        if self.head == self.tail:
            # Stack has only one node
            self.head = None
            self.tail = None
        else:
            # Update the tail to the previous node
            self.tail = self.tail.prev
            self.tail.next = None

        return popped_node.data

    def peek(self):
        if not self.head:
            # Stack is empty
            return None

        # Return the data of the top node
        return self.tail.data


# Test the Stack class
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)

print("Peek:", stack.peek())  # Output: 3
print("Pop:", stack.pop())    # Output: 3
print("Pop:", stack.pop())    # Output: 2
print("Peek:", stack.peek())  # Output: 1

In this implementation, the Node class represents each node in the doubly linked list. The Stack class maintains the references to the head and tail nodes. The push method inserts a new node at the top of the stack, the pop method removes the top node from the stack, and the peek method returns the data of the top node without removing it.

Time and Space Complexity:

The time complexity for push, pop, and peek operations is O(1) since we only perform constant-time operations such as updating references.
The space complexity is O(n), where n is the number of elements in the stack. Each element requires a node in the doubly linked list.

Let's solve a question from that can be tackled using the concept of a stack implemented with a doubly linked list. The question we'll solve is "Valid Parentheses."

Problem Description: Given a string 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: Input: s = "({[]})" Output: True

Input: s = "({[})]" Output: False

To solve this problem, we can use a stack to keep track of the opening brackets we encounter. Whenever we encounter a closing bracket, we can check if it matches the top of the stack. If it does, we pop the opening bracket from the stack and continue. If it doesn't match or the stack is empty, we return False. After processing all the characters in the string, if the stack is empty, we return True; otherwise, we return False.

Here's the Python code to solve the "Valid Parentheses" problem using a stack implemented with a doubly linked list:


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


class Stack:
    def __init__(self):
        self.head = None
        self.tail = None

    def push(self, char):
        new_node = Node(char)

        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node

    def pop(self):
        if not self.head:
            return None

        popped_node = self.tail

        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            self.tail = self.tail.prev
            self.tail.next = None

        return popped_node.char

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


def is_valid(s):
    stack = Stack()

    for char in s:
        if char in '({[':
            stack.push(char)
        else:
            if stack.is_empty():
                return False
            top_char = stack.pop()
            if (top_char == '(' and char != ')') or \
                    (top_char == '{' and char != '}') or \
                    (top_char == '[' and char != ']'):
                return False

    return stack.is_empty()


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

s2 = "({[})]"
print("Is Valid:", is_valid(s2))  # Output: False

In this example, we use the Node and Stack classes to implement a stack using a doubly linked list. The is_valid function takes a string s as input and iterates over each character. If the character is an opening bracket, it is pushed onto the stack. If it is a closing bracket, we check if it matches the top of the stack and pop the top if they match. Finally, we check if the stack is empty to determine if the string is valid.

The time complexity of this solution is O(n) since we iterate through each character in the input string once. The space complexity is O(n) as well, where n is the length of the input string.

Let's solve another question from using the stack concept implemented with a doubly linked list. The problem we'll solve is "Decode String."

Problem Description: Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

Example: Input: s = "3[a]2[bc]" Output: "aaabcbc"

Input: s = "3[a2[c]]" Output: "accaccacc"

To solve this problem, we can use a stack to keep track of the encoded strings and the corresponding counts. We iterate through each character in the input string and perform the following steps:

If the character is a digit, we extract the complete number and push it onto the stack.
If the character is an opening bracket, we push an empty string onto the stack to store the encoded string.
If the character is a closing bracket, we pop the encoded string and the count from the stack and repeat the encoded string the given number of times.
If the character is a letter, we append it to the current encoded string on the top of the stack.

Here's the Python code to solve the "Decode String" problem using a stack implemented with a doubly linked list:


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


class Stack:
    def __init__(self):
        self.head = None
        self.tail = None

    def push(self, value):
        new_node = Node(value)

        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node

    def pop(self):
        if not self.head:
            return None

        popped_node = self.tail

        if self.head == self.tail:
            self.head = None
            self.tail = None
        else:
            self.tail = self.tail.prev
            self.tail.next = None

        return popped_node.value

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

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


def decode_string(s):
    stack = Stack()

    for char in s:
        if char.isdigit():
            stack.push(int(char))
        elif char == '[':
            stack.push('')
        elif char == ']':
            encoded_string = ''
            while stack.peek() != '':
                encoded_string = stack.pop() + encoded_string
            stack.pop()  # Discard the empty string marker
            count = stack.pop()
            stack.push(encoded_string * count)
        else:
            stack.push(char)

    return ''.join(stack.pop() for _ in range(len(stack)))


# Test the solution
s1 = "3[a]2[bc]"
print("Decoded String:", decode_string(s1))  # Output: "aaabcbc"

s2 = "3[a2[c]]"
print("Decoded String:", decode_string(s2))  # Output: "accaccacc"

In this example, we use the Node and Stack classes to implement a stack using a doubly linked list. The decode_string function takes an encoded string s as input and iterates through each character. Depending on the character type (digit, opening bracket, closing bracket, or letter), we perform the necessary operations on the stack. Finally, we join the individual decoded strings from the stack to get the final result.

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 encoded strings and counts on the stack.

Stack With Doubly Linked List

DIFFICULTY

COMPANY

Data Structures