Stack and Queue Lecture Notes

Introduction

• Continuation of the "Sters A to Z DSA Course"
• Focus on Stack and Queue
• Link to previous content in the description

What is a Stack?

• A stack is a data structure that holds a certain type of data.
• Can store various data types:
  • Integer
  • Pair
  • Double
  • Long
  • Character
  • String
  • Custom types
• Follows Last In First Out (LIFO) mechanism.

Stack Operations

1. Push: Adds a value to the stack.
2. Pop: Removes the last element pushed onto the stack.
3. Top: Retrieves the topmost element without removing it.
4. Size: Returns the number of elements in the stack.

Example Operations

• Push(2)
• Push(3)
• Push(4)
• Push(1)
• Pop() returns 1
• Top() returns 4
• Size() returns 3

What is a Queue?

• A Queue is a data structure that follows First In First Out (FIFO) mechanism.

Queue Operations

1. Push: Adds a value to the queue.
2. Pop: Removes the first element from the queue.
3. Top: Retrieves the front element without removing it.
4. Size: Returns the number of elements in the queue.

Example Operations

• Push(2)
• Push(1)
• Push(3)
• Push(4)
• Pop() removes 2
• Top() returns 1
• Size() returns 3

Implementing Stack and Queue using Arrays

• Stack requires a fixed size array. E.g., int stack[10].
• Operations need checks for size exceeding capacity.
• Implementation is straightforward with functions for push, pop, top, and size.

Time Complexity for Stack using Arrays

• All operations: O(1)
• Space Complexity: fixed size, may waste space if not all elements are used.

Implementing Stack and Queue using Linked Lists

• Linked lists allow dynamic sizing.
• Stack uses a single pointer (top).
• Queue uses two pointers (start and end).

Time Complexity for Stack using Linked Lists

• All operations: O(1)
• Space Complexity: dynamic, depends on number of elements.

Implementing Stack using Queue and Queue using Stack

Stack using Queue

• Requires reverse ordering of elements during push to maintain LIFO behavior.
• Operations may require multiple steps to rearrange the queue.

Queue using Stack

• Uses two stacks to maintain FIFO behavior.
• Transfers elements between stacks to provide top and pop actions accordingly.

Conclusion

• Understanding stacks and queues is essential for problem-solving in data structures.
• Implementations can vary based on the types used (arrays vs linked lists).
• Performance can be optimized depending on the use case.

---

• Ensure to practice implementations and understand the underlying mechanisms for interviews.