Data Structures

Hash tables, also known as hash maps or dictionaries in some programming languages, are data structures that store key-value pairs. They use a technique called hashing to efficiently retrieve and store data based on keys.

Here’s a basic overview of how hash tables work:

1. Hash Function: A hash function is used to convert keys into array indices. It takes a key as input and computes a hash code, which is typically an integer. This hash code is then mapped to an index in the hash table’s underlying array.

2. Heap Data Structure 2024-06-07

   The heap data structure is a binary tree-based data structure that satisfies the heap property. It is commonly implemented as an array, where the parent-child relationships are determined by the indices of the array elements. There are two main types of heaps: max heaps and min heaps.

   Max Heap: In a max heap, every parent node has a value greater than or equal to the values of its children. The maximum value is stored at the root of the heap.

3. Queue Data Structure 2022-06-27

   A Queue is a linear data struture that is open at both ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). In can be thought of as a queue of poeple waiting to get tickets, the first person in line will be the first one called to purchase their ticket.

   

   Basic Operations

   • enqueue() − add (store) an item to the queue.

   • Stack Data Structure 2022-06-27

     The stack data structure is a fundamental abstract data type commonly used in computer science and software engineering. It follows the Last-In, First-Out (LIFO) principle, meaning that the last element added to the stack is the first one to be removed. Think of it like a stack of plates: you can only add or remove plates from the top of the stack.

     

     Basic Operations

     • Push: Adding an element to the top of the stack.
     • Pop: Removing the top element from the stack.
     • Peek (or Top): Viewing the top element of the stack without removing it.
     • isEmpty: Checking if the stack is empty.
     • Size: Returning the number of elements currently in the stack.

     Implementations

     • Stacks can be implemented using various data structures, including arrays and linked lists.
     • Arrays are commonly used for implementing stacks due to their simplicity and constant-time access to elements.
     • Linked lists can also be used, providing dynamic memory allocation and flexibility.

     A stack implemented using an array

     class Stack:
     	def __init__(self, data):
     		self.stack = []
     		if data:
     			self.stack.append(data)
     
     	def add(self, data):
     		self.stack.append(data)
     
     	def pop(self):
     		return self.stack.pop()
     
     	def peek(self):
     		if self.isEmpty():
     			raise ValueError("The stack is empty")
     		return self.stack[-1]
     
     	def isEmpty(self):
     		return len(self.stack) == 0
     

     type DataType interface{}
     
     type Stack []DataType
     
     func (s *Stack) Size() int {
     	return len(*s)
     }
     
     func (s *Stack) IsEmpty() bool {
     	return len(*s) == 0
     }
     
     func (s *Stack) Push(d DataType) {
     	*s = append(*s, d)
     }
     
     func (s *Stack) Pop() DataType {
     	if s.IsEmpty() {
     		return ""
     	} else {
     		index := len(*s) - 1   
     		element := (*s)[index] 
     		*s = (*s)[:index]      
     		return element
     	}
     }
     
     func (s *Stack) Peek() DataType {
     	if s.IsEmpty() {
     		return ""
     	}
     	return (*s)[len(*s)-1]
     }
     

     class Stack {
         constructor() {
           this.stack = [];
         }
         
         push(data) {
             this.stack.push(data);
         }
         
         pop() {
             return this.stack.pop();
         }
         
         peek() {
             return this.stack[this.stack.length-1];
         }
         
         isEmpty() {
             return this.stack.length === 0;
         }
     }
     

     class Stack {
     private:
     	vector<string> stack;
     public:
     	void push(string data) {
     		stack.push_back(data);
     	}
     
     	string pop() {
     		string temp = stack.back();
     		stack.pop_back();
     		return temp;
     	}
     
     	string peek() {
     		return stack.back();
     	}
     
     	bool empty() {
     		return stack.empty();
     	}
     };
     

     class Stack {
         private ArrayList<Integer> stack;
     
         Stack (int size) {
             stack = new ArrayList<Integer>(size);
         }
     
         public void push(int data) {
             stack.add(data);
         }
     
         public int pop() {
             int temp = stack.get(stack.size()-1);
             stack.remove(stack.size()-1);
             return temp;
         }
     
         public int peek() {
             return stack.get(stack.size()-1);
         }
     
         public boolean isEmpty() {
             return stack.isEmpty();
         }
     }
     

     A stack implemented using a Linked List.

   • Linked List Data Structure 2019-03-26

     A linked list is a linear collection of data elements, their order is not given by their physical placement in memory. Instead they are constructed in such a way that each element points to the next. It is a data structure that consists of a collection of nodes which together represents a sequence.

     

     Linked lists can be singly or doubly linked.