[CC150] Chapter 3 Stacks and Queues
3.1 Describe how you could use a single array to implement three stacks.
If we assume that all three stacks have the same size, we could easily do this by recording the indice for the top elements. Here I ignore the dynamic implementation in the book since it is way too complicate.
3.2 How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop, and min should all operate in O(1) time.
Use an additional stack to store the current and historic minimum elements. Note that here we used a pair to handle duplicates. Instead of push all duplicated minimum elements to the stack, the following code is more efficient for saving space. Note that we did not assert the pop operation. For the original stack class in C++, pop a empty stack does not throw an error.
3.3 Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks and should create a new stack once the previous one exceeds capacity. SetOfStack.push() and SetOfStack.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).
FOLLOW UP
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.
Here we use a vector of stacks. Note that my solution does not guarantee that all stacks except the last one will be full after some popAt() operations. If we want that, the time and space complexity will significantly increase by moving the latest stacks (or we can use linked list since it is easier to move).
3.4 In the classic problem of the Towers of Hanoi, you have 3 towers and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (i.e., each disk sits on top of an even larger one). You have the following constraints:
(1) Only one disk can be moved at a time;
(2) A disk is slid off the top of one tower onto the next tower;
(3) A disk can only be placed on top of a large disk.
Write a program to move the disks from the first tower to the last using stacks.
Clearly we could use recursion. Suppose we have three towers, t1, t2 and t3. We would like to move N disks at t1 to t3. This can be done by:
a) Move N-1 disks from t1 to t2, using t3 as buffer.
b) Move the largest disk from t1 to t3.
c) Move N-1 disks from t2 to t3, using t1 as buffer.
3.5 Implement a MyQueue class which implements a queue using two stacks.
Essentially, anytime we want to get the front of the queue, we reverse the stack. However, I am not sure how to implement back() under this approach.
The amortized cost is O(1) for any operations.
3.6 Write a program to sort a stack in ascending order (with biggest items on top). You may use additional stacks to hold items, but you may not copy the elements into any other data structures (such as an array). The stack supports the following operations: push, pop, peek, and isEmpty.
The only way is to use inserting sort and an additional buffer stack.
3.7 An animal shelter holds only dogs and cats, and operates on a strictly "first in, first out" basis. People must adopt either the "oldest" (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specific animal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog, dequeueCat. You may use the built-in LinkedList data structure.
The easiest way is to use two queues, one for dogs and another for cats. We use another variable (such as time stamp) to record the arrival time. When we do dequeueAny, we compare the arrival times for the front nodes of two queues, and return the older one.
If we assume that all three stacks have the same size, we could easily do this by recording the indice for the top elements. Here I ignore the dynamic implementation in the book since it is way too complicate.
3.2 How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop, and min should all operate in O(1) time.
Use an additional stack to store the current and historic minimum elements. Note that here we used a pair to handle duplicates. Instead of push all duplicated minimum elements to the stack, the following code is more efficient for saving space. Note that we did not assert the pop operation. For the original stack class in C++, pop a empty stack does not throw an error.
3.3 Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks and should create a new stack once the previous one exceeds capacity. SetOfStack.push() and SetOfStack.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).
FOLLOW UP
Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.
Here we use a vector of stacks. Note that my solution does not guarantee that all stacks except the last one will be full after some popAt() operations. If we want that, the time and space complexity will significantly increase by moving the latest stacks (or we can use linked list since it is easier to move).
3.4 In the classic problem of the Towers of Hanoi, you have 3 towers and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (i.e., each disk sits on top of an even larger one). You have the following constraints:
(1) Only one disk can be moved at a time;
(2) A disk is slid off the top of one tower onto the next tower;
(3) A disk can only be placed on top of a large disk.
Write a program to move the disks from the first tower to the last using stacks.
Clearly we could use recursion. Suppose we have three towers, t1, t2 and t3. We would like to move N disks at t1 to t3. This can be done by:
a) Move N-1 disks from t1 to t2, using t3 as buffer.
b) Move the largest disk from t1 to t3.
c) Move N-1 disks from t2 to t3, using t1 as buffer.
3.5 Implement a MyQueue class which implements a queue using two stacks.
Essentially, anytime we want to get the front of the queue, we reverse the stack. However, I am not sure how to implement back() under this approach.
The amortized cost is O(1) for any operations.
3.6 Write a program to sort a stack in ascending order (with biggest items on top). You may use additional stacks to hold items, but you may not copy the elements into any other data structures (such as an array). The stack supports the following operations: push, pop, peek, and isEmpty.
The only way is to use inserting sort and an additional buffer stack.
3.7 An animal shelter holds only dogs and cats, and operates on a strictly "first in, first out" basis. People must adopt either the "oldest" (based on arrival time) of all animals at the shelter, or they can select whether they would prefer a dog or a cat (and will receive the oldest animal of that type). They cannot select which specific animal they would like. Create the data structures to maintain this system and implement operations such as enqueue, dequeueAny, dequeueDog, dequeueCat. You may use the built-in LinkedList data structure.
The easiest way is to use two queues, one for dogs and another for cats. We use another variable (such as time stamp) to record the arrival time. When we do dequeueAny, we compare the arrival times for the front nodes of two queues, and return the older one.
Comments
Post a Comment