Data Structures Implementation

This project contains implementations of various data structures in C++, including:

• Array-Based List
• Single Linked List
• Doubly Linked List
• Circular Linked List
• Stack
• Queue

Each data structure has its own set of methods that can be used to interact with the structure. Additionally, there are several problems included that can be solved using these data structures.

Array-Based List

The Array-Based List implementation includes the following methods:

• insert(elementType element): void
• insertAt(elementType element, int index): void
• retrieveAt(int index): elementType
• removeAt(int index): void
• replaceAt(elementType newElement, int index)
• isItemAtEqual(elementType element, int index): bool
• isEmpty(): bool
• isFull(): bool
• listSize(): int
• maxListSize(): int
• clear(): void
• print(): void

Single Linked List

The Single Linked List implementation includes the following methods:

• insertAtHead(elementType element): void
• insertAtTail(elementType element): void
• insertAt(elementType element, int index): void
• removeAtHead(): void
• removeAtTail(): void
• removeAt(int index): void
• retrieveAt(int index): elementType
• replaceAt(elementType newElement, int index)
• isExist(elementType element): bool
• isItemAtEqual(elementType element, int index): bool
• swap(int firstItemIdx, int secondItemIdx): void (swap two nodes without swapping data)
• isEmpty(): bool
• linkedListSize(): int
• clear(): void
• print(): void

Doubly Linked List

The Doubly Linked List implementation includes the following methods:

• insertAtHead(elementType element): void
• insertAtTail(elementType element): void
• insertAt(elementType element, int index): void
• insertAfter(* prev_node, int data): void
• removeAtHead(): void
• removeAtTail(): void
• removeAt(int index): void
• retrieveAt(int index): elementType
• replaceAt(elementType newElement, int index)
• isExist(elementType element): bool
• isItemAtEqual(elementType element, int index): bool
• swap(int firstItemIdx, int secondItemIdx): void (swap two nodes without swapping data)
• reverse(): void (reverse the data in the double linked list)
• isEmpty(): bool
• doubleLinkedListSize(): int
• clear(): void
• forwardTraversal(): void (Print from head to tail)
• backwardTraversal(): void (Print from tail to head)

Circular Linked List

The Circular Linked List implementation includes the following methods:

• insertAtHead(elementType element): void
• insertAtEnd(elementType element): void
• insertAt(elementType element, int index): void
• removeAtHead(): void
• removeAtEnd(): void
• removeAt(int index): void
• retrieveAt(int index): elementType
• replaceAt(elementType newElement, int index)
• isExist(elementType element): bool
• isItemAtEqual(elementType element, int index): bool
• swap(int firstItemIdx, int secondItemIdx): void (swap two nodes without swapping data)
• isEmpty(): bool
• circularLinkedListSize(): int
• clear(): void
• print(): void

Stack

The Stack implementation includes the following methods:

• push(elementType element): void
• pop(): void
• top(): elementType
• isEmpty(): bool
• isFull(): bool
• stackSize(): int

Queue

The Queue implementation includes the following methods:

• enqueue(elementType element): void
• dequeue(): void
• front(): elementType
• isEmpty(): bool
• isFull(): bool
• queueSize(): int

Problems

This project includes several problems that can be solved using the implemented data structures. These problems are:

Linked List Problems

Problem 1: Combine Nodes Between Zeros

Given a linked list containing a sequence of integers separated by 0s, merge all nodes between any two consecutive 0s into a single node whose value is the total of all the merged nodes. There are no two consecutive nodes with value == 0. There should be no 0s in the new list.

Problem 2: Merge K Sorted Linked Lists

Given k linked-lists, each linked-list is sorted in ascending order, merge all the linked-lists into one sorted linked-list.

Stack Problems

Problem 1: Convert the Infix Expression to Postfix Expression

Given a string representing an infix expression, convert it to postfix expression.

Problem 2: Longest Valid Parentheses

Given a string containing the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

Queue Problems

Problem 1: Generate Binary Numbers from 1 to N

Write a function that generates and prints all binary integers from 1 to N.

Problem 2: Implement a Stack

Implement a stack that supports push and pop operations using the enqueue and dequeue operations of the queue. You can use one or more queues.

Problem 3: Sorting a Queue

Given a queue with random integer elements, sort it.