1.3 Bags, Queues, and Stacks
1.3.1¶
Add a method isFull() to FixedCapacityStackOfStrings.
public boolean isFull() {
return N == a.length;
}
1.3.2¶
Give the output printed by java Stack for the input
it was - the best - of times - - - it was - the - -
Answer is:
to be not that or be (2 left on stack)
1.3.3¶
Suppose that a client performs an intermixed sequence of (stack) push and pop operations. The push operations put the integers 0 through 9 in order onto the stack; the pop operations print out the return values. Which of the following sequence(s) could not occur?
a. 4 3 2 1 0 9 8 7 6 5 b. 4 6 8 7 5 3 2 9 0 1 c. 2 5 6 7 4 8 9 3 1 0 d. 4 3 2 1 0 5 6 7 8 9 e. 1 2 3 4 5 6 9 8 7 0 f. 0 4 6 5 3 8 1 7 2 9 g. 1 4 7 9 8 6 5 3 0 2 h. 2 1 4 3 6 5 8 7 9 0
TODO
1.3.4¶
Write a stack client Parentheses that reads in a text stream from standard input and uses a stack to determine whether its parentheses are properly balanced. For example, your program should print true for [()]{}{()()} and false for [(]).
static boolean areBalanced(String expr) {
Stack < Character > stack = new Stack < Character > ();
// Traversing the Expression
for (int i = 0; i < expr.length(); i++) {
char x = expr.charAt(i);
if (x == '(' || x == '[' || x == '{') {
// Push the element in the stack
stack.push(x);
continue;
}
if (stack.isEmpty())
return false;
switch (x) {
case ')':
stack.pop();
if (x != '(')
return false;
break;
case '}':
stack.pop();
if (x != '{')
return false;
break;
case ']':
stack.pop();
if (x != '[')
return false;
break;
}
}
return (stack.isEmpty());
}
1.3.6¶
What does the following code fragment do to the queue q?
Stack<String> stack = new Stack<String>();
while (!q.isEmpty())
stack.push(q.dequeue());
while (!stack.isEmpty())
q.enqueue(stack.pop());
It reverses the order of the strings pushed originally. Check it out with this simple example:
public static void main(String[] args) {
Stack < String > stack = new Stack < String > ();
Deque < String > q = new ArrayDeque < String > ();
q.offer("Hello");
q.offer("World");
q.offer("This");
q.offer("Is");
q.offer("It");
while (!q.isEmpty())
stack.push(q.poll()); // reverses order of strings
while (!stack.isEmpty())
q.offer(stack.pop()); // put back in reverse order
while (!q.isEmpty())
System.out.println(q.poll());
}
1.3.7¶
Add a method peek() to Stack that returns the most recently inserted item on the stack (without popping it).
public Item peek() {
if (N > 0) {
return a[0];
}
return null;
}
1.3.8¶
Give the contents and size of the array for DoublingStackOfStrings with the input
it was - the best - of times - - - it was - the - -
TODO
1.3.9¶
Write a program that takes from standard input an expression without left parentheses and prints the equivalent infix expression with the parentheses inserted. For example, given the input:
1 + 2 ) * 3 - 4 ) * 5 - 6 ) )your program should print
( ( ( ( 1 + 2 ) * 3 - 4 )) * ( 5 - 6 ) )
The idea is simple. Iterate over all the symbols and put them into a stack. When we reach a )
we pop all items into another stack and insert a left parenthesis '(' and then we push the items back again.
When we reach the end we will have the complete expression from the stack in reverse. So we need to print them in reverse.
static String parseExpr(String expr) {
Stack in = new Stack < Character > ();
Stack out = new Stack < Character > ();
for (char c: expr.toCharArray()) {
if (c == ' ') {
continue;
}
if (c == ')') {
while (! in .empty()) {
out.add( in .pop());
} in .push('(');
while (!out.empty()) { in .add(out.pop());
}
} in .push(c);
}
return in.toString();
}
1.3.10¶
Write a filter InfixToPostfix that converts an arithmetic expression from infix to postfix.
Taken from here
static int precedence(char ch) {
switch (ch) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
static String infixToPostfix(String input) {
Stack output = new Stack < Character > ();
Stack symbols = new Stack < Character > ();
for (char c: input.toCharArray()) {
if (Character.isLetterOrDigit(c)) {
output.push(c);
} else if (c == ' ' || c == '(') {
symbols.push(c);
} else if (c == ')') {
while (!symbols.isEmpty() && (char) symbols.peek() != '(')
output.push(symbols.pop());
if (!symbols.isEmpty() && (char) symbols.peek() != '(')
return "Invalid Expression"; // invalid expression
else
symbols.pop();
} else {
while (!symbols.isEmpty() && precedence(c) <= precedence((char) symbols.peek())) {
if ((char) symbols.peek() == '(')
return "Invalid Expression";
output.push(symbols.pop());
}
symbols.push(c);
}
}
while (!symbols.empty()) {
output.push(symbols.pop());
}
return output.toString();
}
1.3.11¶
Write a program EvaluatePostfix that takes a postfix expression from standard input, evaluates it, and prints the value. (Piping the output of your program from the previous exercise to this program gives equivalent behavior to Evaluate.
static int evaluatePostfix(String input) {
Stack s = new Stack < Integer > ();
String[] parts = input.split("\\s+");
for (String part: parts) {
if (part.equals(" ")) {
continue;
}
if (part.equals("+")) {
int first = (int) s.pop();
int second = (int) s.pop();
s.push(first + second);
} else if (part.equals("*")) {
int first = (int) s.pop();
int second = (int) s.pop();
s.push(first * second);
} else {
s.push(Integer.parseInt(part));
}
}
return (int) s.pop();
}
1.3.12¶
Write an iterable Stack client that has a static method copy() that takes a stack of strings as argument and returns a copy of the stack. Note : This ability is a prime example of the value of having an iterator, because it allows development of such functionality without changing the basic API.
Taken from here.
public static FixedCapacityStackOfStrings copy(FixedCapacityStackOfStrings s) {
FixedCapacityStackOfStrings copy = new FixedCapacityStackOfStrings(s.size());
int count = 0;
while (count != s.size() - 1) {
// grab the top element
String top = s.pop();
// Shift all the other elements into the destination stack
while (count != s.size()) {
copy.push(s.pop());
}
// push the top element into the source stack
s.push(top);
// Shift the previously shifted elements into the source stack again
while (!copy.isEmpty()) {
s.push(copy.pop());
}
count += 1;
}
// The items in the source stack are in reverse order here. Push them into the destination to get the original stack
while (!s.isEmpty()) {
copy.push(s.pop());
}
return copy;
}
1.3.13¶
Suppose that a client performs an intermixed sequence of (queue) enqueue and dequeue operations. The enqueue operations put the integers 0 through 9 in order onto the queue; the dequeue operations print out the return value. Which of the following sequence(s) could not occur?
a. 0 1 2 3 4 5 6 7 8 9
b. 4 6 8 7 5 3 2 9 0 1
c. 2 5 6 7 4 8 9 3 1 0
d. 4 3 2 1 0 5 6 7 8 9
TODO
1.3.14¶
Develop a class ResizingArrayQueueOfStrings that implements the queue abstraction with a fixed-size array, and then extend your implementation to use array resizing to remove the size restriction.
static class ResizingArrayQueueOfStrings < String > implements Iterable < String > {
private String[] a;
private int N = 0;
ResizingArrayQueueOfStrings() {
a = (String[]) new Object[1];
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
private void resize(int max) { // Move stack to a new array of size max.
String[] temp = (String[]) new Object[max];
for (int i = 0; i < N; i++)
temp[i] = a[i];
a = temp;
}
public void enqueue(String item) { // Add item to the end of the queue.
if (N == a.length) resize(2 * a.length);
a[N++] = item;
}
public String pop() { // Remove item from the front of queue.
String item = a[0];
for (int i = 1; i < N; i++) {
a[i - 1] = a[i];
}
if (N > 0 && N == a.length / 4) resize(a.length / 2);
return item;
}
@Override
public Iterator < String > iterator() {
return new ResizingArrayQueueOfStringsIterator();
}
private class ResizingArrayQueueOfStringsIterator implements Iterator < String > { // Support FIFO iteration.
private int i = 0;
public boolean hasNext() {
return i < N;
}
public String next() {
return a[i++];
}
public void remove() {}
}
}
1.3.15¶
Write a Queue client that takes a command-line argument k and prints the kth from the last string found on standard input (assuming that standard input has k or more strings).
TODO
1.3.16¶
Using readInts() on page 126 as a model, write a static method readDates() for Date that reads dates from standard input in the format specified in the table on page 119 and returns an array containing them.
TODO
1.3.17¶
Do Exercise 1.3.16 for Transaction.
TODO
1.3.19¶
Give a code fragment that removes the last node in a linked list whose first node is first.
TODO
1.3.20¶
Write a method delete() that takes an int argument k and deletes the kth element in a linked list, if it exists.
TODO
1.3.21¶
Write a method find() that takes a linked list and a string key as arguments and returns true if some node in the list has key as its item field, false otherwise.
TODO
1.3.24¶
Write a method removeAfter() that takes a linked-list Node as argument and removes the node following the given one (and does nothing if the argument or the next field in the argument node is null).
TODO
1.3.25¶
Write a method insertAfter() that takes two linked-list Node arguments and inserts the second after the first on its list (and does nothing if either argument is null).
TODO
1.3.26¶
Write a method remove() that takes a linked list and a string key as arguments and removes all of the nodes in the list that have key as its item field.
TODO
1.3.27¶
Write a method max() that takes a reference to the first node in a linked list as argument and returns the value of the maximum key in the list. Assume that all keys are positive integers, and return 0 if the list is empty.
TODO
1.3.28¶
Develop a recursive solution to the previous question.
TODO
1.3.29¶
Write a Queue implementation that uses a circular linked list, which is the same as a linked list except that no links are null and the value of last.next is first whenever the list is not empty. Keep only one Node instance variable (last).
TODO
1.3.31¶
Implement a nested class DoubleNode for building doubly-linked lists, where each node contains a reference to the item preceding it and the item following it in the list (null if there is no such item). Then implement static methods for the following tasks: insert at the beginning, insert at the end, remove from the beginning, remove from the end, insert before a given node, insert after a given node, and remove a given node.
TODO
1.3.32¶
Steque. A stack-ended queue or steque is a data type that supports push, pop, and enqueue. Articulate an API for this ADT. Develop a linked-list-based implementation.
TODO
1.3.33¶
Deque. A double-ended queue or deque (pronounced “deck”) is like a stack or a queue but supports adding and removing items at both ends. A deque stores a collection of items and supports the following API:
public class Deque<Item> implements Iterable<Item> Deque() create an empty deque boolean isEmpty() is the deque empty? int size() number of items in the deque void pushLeft(Item item) add an item to the left end void pushRight(Item item) add an item to the right end Item popLeft() remove an item from the left end Item popRight() remove an item from the right end API for a generic double-ended queueWrite a class Deque that uses a doubly-linked list to implement this API and a class ResizingArrayDeque that uses a resizing array.
TODO
1.3.34¶
Random bag. A random bag stores a collection of items and supports the following API:
public class RandomBag<Item> implements Iterable<Item>
RandomBag() create an empty random bag
boolean isEmpty() is the bag empty?
int size() number of items in the bag
void add(Item item) add an item
Write a class RandomBag that implements this API. Note that this API is the same as for Bag, except for the adjective random, which indicates that the iteration should provide the items in random order (all N ! permutations equally likely, for each iterator). Hint : Put the items in an array and randomize their order in the iterator’s constructor.
TODO
1.3.35¶
Random queue. A random queue stores a collection of items and supports the following API:
public class RandomQueue<Item>
RandomQueue() create an empty random queue
boolean isEmpty() is the queue empty?
void enqueue(Item item) add an item
Item dequeue() remove and return a random item
(sample without replacement)
Item sample() return a random item, but do not remove
(sample with replacement)
Write a class RandomQueue that implements this API. Hint : Use an array representation (with resizing). To remove an item, swap one at a random position (indexed 0 through N-1) with the one at the last position (index N-1). Then delete and return the last object, as in ResizingArrayStack. Write a client that deals bridge hands (13 cards each) using RandomQueue
.
TODO
1.3.36¶
Random iterator. Write an iterator for RandomQueue
- from the previous exercise that returns the items in random order.
TODO
1.3.37¶
Josephus problem. In the Josephus problem from antiquity, N people are in dire straits and agree to the following strategy to reduce the population. They arrange themselves in a circle (at positions numbered from 0 to N–1) and proceed around the circle, eliminating every Mth person until only one person is left. Legend has it that Josephus figured out where to sit to avoid being eliminated. Write a Queue client Josephus that takes N and M from the command line and prints out the order in which people are eliminated (and thus would show Josephus where to sit in the circle). % java Josephus 7 2 1 3 5 0 4 2 6
TODO
1.3.38¶
Delete kth element. Implement a class that supports the following API:
First, develop an implementation that uses an array implementation, and then develop one that uses a linked-list implementation. Note : the algorithms and data structures that we introduce in Chapter 3 make it possible to develop an implementation that can guarantee that both insert() and delete() take time prortional to the logarithm of the number of items in the queue—see Exercise 3.5.27.public class GeneralizedQueue<Item> GeneralizedQueue() create an empty queue boolean isEmpty() is the queue empty? void insert(Item x) add an item Item delete(int k) delete and return the kth least recently inserted item
TODO
1.3.39¶
Ring buffer. A ring buffer, or circular queue, is a FIFO data structure of a fixed size N. It is useful for transferring data between asynchronous processes or for storing log files. When the buffer is empty, the consumer waits until data is deposited; when the buffer is full, the producer waits to deposit data. Develop an API for a RingBuffer and an implementation that uses an array representation (with circular wrap-around).
TODO
1.3.40¶
Move-to-front. Read in a sequence of characters from standard input and maintain the characters in a linked list with no duplicates. When you read in a previously unseen character, insert it at the front of the list. When you read in a duplicate character, delete it from the list and reinsert it at the beginning. Name your program MoveToFront: it implements the well-known move-to-front strategy, which is useful for caching, data compression, and many other applications where items that have been recently accessed are more likely to be reaccessed.
TODO
1.3.41¶
Copy a queue. Create a new constructor so that
Queue<Item> r = new Queue<Item>(q);
makes r a reference to a new and independent copy of the queue q. You should be able to push and pop from either q or r without influencing the other. Hint : Delete all of the elements from q and add these elements to both q and r.
TODO
1.3.42¶
Copy a stack. Create a new constructor for the linked-list implementation of Stack so that
Stack<Item> t = new Stack<Item>(s);
makes t a reference to a new and independent copy of the stack s.
TODO
1.3.43¶
Listing files. A folder is a list of files and folders. Write a program that takes the name of a folder as a command-line argument and prints out all of the files contained in that folder, with the contents of each folder recursively listed (indented) under that folder’s name. Hint : Use a queue, and see java.io.File.
TODO
1.3.44¶
Text editor buffer. Develop a data type for a buffer in a text editor that implements the following API:
Hint : Use two stacks.public class Buffer Buffer() create an empty buffer void insert(char c) insert c at the cursor position char delete() delete and return the character at the cursor void left(int k) move the cursor k positions to the left void right(int k) move the cursor k positions to the right int size() number of characters in the buffer
TODO
1.3.46¶
Forbidden triple for stack generability. Prove that a permutation can be generated by a stack (as in the previous question) if and only if it has no forbidden triple (a, b, c) such that a < b < c with c first, a second, and b third (possibly with other intervening integers between c and a and between a and b). Partial solution: Suppose that there is a forbidden triple (a, b, c). Item c is popped before a and b, but a and b are pushed before c. Thus, when c is pushed, both a and b are on the stack. Therefore, a cannot be popped before b.
TODO
1.3.47¶
Catenable queues, stacks, or steques. Add an extra operation catenation that (destructively) concatenates two queues, stacks, or steques (see Exercise 1.3.32). Hint : Use a circular linked list, maintaining a pointer to the last item.
TODO
1.3.48¶
Two stacks with a deque. Implement two stacks with a single deque so that each operation takes a constant number of deque operations (see Exercise 1.3.33).
TODO
1.3.49¶
Queue with three stacks. Implement a queue with three stacks so that each queue operation takes a constant (worst-case) number of stack operations. Warning : high degree of difficulty
TODO