Homework 3: Stacks and Queues

Question 1:

Its common to implement a specific data structure using others. This time, youre asked to implement a

queue using only 2 stacks. The implemented queue must support the main functions of a normal queue:

enqueue(e), first, and dequeue.

Question 2:

Prior to our discussion in lab 3, exercise 2. Show your implementation of boolean isBalanced(String

exp)where expr is a string of the grouping elements: {}, [], (). The method checks whether the pairs are

balanced in the given expression.

Question 3:

A palindrome is a string that is identical to itself when reversed. For example, "madam", "dad", and "abba" are

palindromes. Use a stack and queue to implement the boolean isPalindrome(String text)

method. It returns true if the text is palindrome, false otherwise.

Note: the empty string is a palindrome, as is every string of length one.

Question 4:

Remove All Adjacent Duplicates In String, you are given a string, you should return a string without any

duplicate adjacent letters, for example:

Input: s = "abbaca"

Output: "ca"

Explanation:

In "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move.

The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".

*Try to use stack to solve this problem.Lab1 | Introduction

Question 5:

You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class:

-

RecentCounter(): Initializes the counter with zero recent requests.

-

int ping(int t): Adds a new request at time t, where t represents some time in milliseconds, and returns

the number of requests that has happened in the past 3000 milliseconds (including the new request).

Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].

It is guaranteed that every call to ping method uses a strictly larger value of t than the previous call.

class RecentCounter {

public RecentCounter() {

}

public int ping(int t) {

}

}

Question 6:

A file system keeps a log each time some user performs a change folder operation.

The operations are described below:

"../" : Move to the parent folder of the current folder. (If you are already in the main folder, remain in the same

folder).

"./" : Remain in the same folder.

"x/" : Move to the child folder named x (This folder is guaranteed to always exist).

You are given a list of strings logs where logs[i] is the operation performed by the user at the i-th step.

The file system starts in the main folder, then the operations in logs are performed.

Return the minimum number of operations needed to go back to the main folder after the change folder operations.

Input: logs = ["d1/","d2/","../","d21/","./"]

Output: 2

Explanation: Use this change folder operation "../" 2 times and go back to the

main folder.