Algorithms, Part 1 Course from Princeton — Stack, Queue, and Week 2 Assignment Deques and Randomized Queues

Introduction

Algorithms, Part 1 is a solid course for IT or software engineers to learn algorithms which are provided by Princeton. Of course, we still have to take time to clarify the concepts after completing the class.

Stack and queue are fundamental data structure for storing data in the practice. In this article, we will focus on APIs and different ways for implementations.

About this Series

This series aims to wrap up contents of Algorithms, Part 1.

• week 1: Union-find and Week 1 assignment Percolation
• week 2: this article
• week 3: Sorting and Week 3 assignment Collinear Points
• week 4: Binary Tree, Binary Heaps, and Week 4 Assignment 8 puzzle
• week 5: Hash table and Week 5 Assignment KD-Tree

Agenda

It includes the following topics in this article.

• Separate interface and implementation
• Introduction to Stack
• Stack implementation in Linked-list
• Stack implementation in Array (Resizing array)
• Introduction to Queue
• Queue implementation in Linked-list
• Queue implementation in Array (Resizing array)
• Priority queue implementation in Array
• Week 2 Programming Assignment: Deques and Randomized Queues

1. Separate interface and implementation

What we want to do is to completely separate the details of the implementation from the client

e.g., stack, queue, bag, priority queue, symbol table, union-find, etc.

Roles

• client : program using operations defined in an interface
• implementation : actual code implementing operations
• interface : the description of data type, basic operations

Benefits

1. Client has many implementation from which to choose but the client code should only perform the basic operations
2. Many clients can re-use the sameimplementation

2. Introduction to Stack

Last in First out (LIFO): remove and return the item most recently added

APIs

APIs we have to implement for the stack.

Resizing array implementation vs linked list implementation

Stack can be implemented with either resizing array or linked list. client can use interchangeably.

Related LeetCode questions

• 150. Evaluate Reverse Polish Notation (medium)
• 155. Min Stack (medium)
• 46. Permutations (medium)
• 77. Combinations (medium)
• 1381. Design a Stack With Increment Operation (medium)
• 1441. Build an Array With Stack Operations (medium)
• 232. Implement Queue using Stacks (easy)
• 225. Implement Stack using Queues (easy)

3. Stack implementation in Linked-list

Description

• Maintain pointer to first node in a linked list
• Insert and remove the front

Propositions

Every operations takes constant time in the worst case

Implementation in Java (from the official video)

4. Stack implementation in Array (Resizing array)

Description

• Use array s[] to store N items on stack
• push : add new item at s[N]
• pop : remove new item at s[N — 1]

Considerations

• underflow: throw exception if pop from an empty stack
• overflow: use resizing array for array implementation

Resizing array

• If the array is full, create a new array of twice the size, and copy items
• consequence: inserting first N items takes time proportional to N (not N ^ 2)
• If the array is full, having size of array s[]

Too expensive in worst case for resizing array

• consider push-pop-push-pop…sequence when array is full
• each operation takes time proportional to N

Proposition

Implementation in Java (from the official video)

Related LeetCode questions

• 1381. Design a Stack With Increment Operation (medium)

5. Introduction to Queue

First in first out (FIFO): remove and return the item least recently added

APIs

APIs we have to implement for the queue.

6. Queue implementation in linked-list

Description

• Maintain pointer to first and last nodes in a linked list
• Insert the front
• Remove from the end

Implementation in Java (from the official video)

7. Queue implementation in Array (Resizing array)

Description

• Use array q[] to store items in queue
• enqueue : add new item at q[tail]
• dequeue : remove item from q[head]
• Update head and tail modulo the capacity

Implementation in Java (completed by myself, from the official video)

8. Priority queue implementation in array

Description

• Queue: remove the item most recently added
• Stack: remove the item least recently added
• Randomized queue: remove a random item
• Priority queue: remove the largest (or smallest) item

APIs

Implementation in Java (from the official video)

• Unordered array implementation

Challenge

• Implement all operations efficiently

9. Completed code in JavaScript

• completed by myself, not from the official video

Week 2 Programming Assignment: Deques and Randomized Queues

There are two requirements.

1. deque: double-ended queue that supports adding and removing items from either the front or the back of the data structute
2. randomized queue: the item removed is chosen uniformly at random among items in the data structure
3. client program: read a sequence of string and print exactly k of item, uniformly at random

Requirements in detail

Solutions

• Deque.java

• RandomizedQueue.java

• Permutation.java

Grades

Summary

Thanks for your patient. I am Sean. I work as a software engineer.

This article is my note. Please feel free to give me advice if any mistakes. I am looking forward to your feedback.

• Subscribe me

• The Facebook page for articles

• The latest side project: Daily Learning