powerpoint notes

Overview of Stacks and Queues in Various Programming Languages

• Stacks and queues are essential data structures used for organizing and manipulating data efficiently.

• Different programming languages provide various container types to implement these structures, and their efficiencies differ based on the operations performed.

Container Choices Across Languages

C++

• vector

  • Good for Stack? Yes

  • Good for Queue? No

  • Why:

  • Back operations are O(1), but front operations are O(n) due to linear time complexity when shifting elements.

  • Notes: Cache-friendly implementation.

• deque

  • Good for Stack? Yes

  • Good for Queue? Yes

  • Why:

  • Both enqueue (adding) and dequeue (removing) operations are O(1) at both ends.

  • Notes: Preferred choice for queues due to its efficiency in both operations.

• list

  • Good for Stack? Works

  • Good for Queue? Works

  • Why:

  • Insertions and deletions are O(1), though traversal is O(n) due to no inherent indexing.

Java

• ArrayList

  • Good for Stack? Yes

  • Good for Queue? No

  • Why:

  • Front removal is O(n) as it requires shifting elements to maintain order.

• LinkedList

  • Good for Stack? Yes

  • Good for Queue? Yes

  • Why:

  • Both ends have O(1) complexity; however, operations in the middle are O(n).

Python

• list

  • Good for Stack? Yes

  • Good for Queue? No

  • Why:

  • Pop from front (pop(0)) is O(n) due to element shifting, but append and pop from end are O(1).

• deque (from collections module)

  • Good for Stack? Yes

  • Good for Queue? Yes

  • Why:

  • Both enqueue and dequeue operations at each end are O(1), making it an efficient choice for both stacks and queues.

Circular Queue

• Defines a circular queue as treating the underlying array as a circular structure, where the ends are connected.

• Utilizes two indices:

  • front: Position from which to remove an element.

  • rear: Position at which to add an element.

• Advantages:

  • Prevents shifting of elements with every enqueue or dequeue operation.

  • When the queue is full, an internal array resize is necessary (resize logic is abstracted here).

  • Ensures that all enqueue and dequeue operations maintain an amortized time complexity of O(1) due to array resizing.

Circular Queue Pseudo-Code

Initialize

• Create an array of size k.

• Set front to 0, rear to 0, and size to 0.

Enqueue(x)

• If size == array.length, call resizeArray().

• Insert x at position rear in the array:

  • array[rear] = x

• Update rear index:

  • rear = (rear + 1) mod array.length

• Increment size:

  • size = size + 1

Dequeue()

• If size == 0, return or throw an exception.

• Retrieve value at front position:

  • value = array[front]

• Update front index:

  • front = (front + 1) mod array.length

• Decrement size:

  • size = size – 1

• Return the retrieved value.

Peek()

• If size == 0, return or throw an exception.

• Return the value at front position.

isEmpty()

• Return boolean indicating if size equals 0.

length()

• Return current size of the queue.

Circular Queue Representation

• Visualize a circular queue with various elements to demonstrate positions of front and rear.

  • Front:

  • Element at index representing front position (e.g., 3).

  • Rear:

  • Element at index representing rear position (e.g., 7).

Amortization

• Concept of amortization explains that most operations are inexpensive over a series of executes, but occasionally one is expensive (such as resizing operations).

• It derives an averaged cost for all operations performed over time.

• For data structures like dynamic arrays or hash tables, the amortized time complexity can be often considered O(1).