本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
算法(第4版)
知识点
- Queue概念
- Queue逆序
- Java 迭代器
- eclipse停止输入快捷键
题目
1.3.6 下面这段代码对队列q进行了什么操作？
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());
答案
逆序
public class Queue<Item> implements Iterable<Item> {
private int N;
private class Node {
Item item;
Node next;
}
private Node first;
private Node last;
public Queue() {
}
public boolean isEmpty() {
if (first == null)
return true;
return false;
}
public int size() {
return N;
}
public void enqueue(Item item) {
Node oldLast = last;
last = new Node();
last.item = item;
last.next = null;
if (this.isEmpty()) {
first = last;
} else {
oldLast.next = last;
}
N++;
}
public Item dequeue() {
Item item = first.item;
first = first.next;
if (this.isEmpty()) {
last = null;
}
N--;
return item;
}
public Iterator<Item> iterator() {
// TODO Auto-generated method stub
return new QueueIterator();
}
private class QueueIterator implements Iterator<Item> {
public boolean hasNext() {
// TODO Auto-generated method stub
return false;
}
public Item next() {
// TODO Auto-generated method stub
return null;
}
public void remove() {
// TODO Auto-generated method stub
}
}
public static void main(String[] args) {
Queue<String> stringQueue = new Queue<String>();
stringQueue.enqueue("我");
stringQueue.enqueue("的");
stringQueue.enqueue("名字");
stringQueue.enqueue("叫顶级程序员不穿女装");
stringQueue.enqueue("微博:https://m.weibo.cn/p/1005056186766482");
// System.out.println(stringQueue.dequeue());
// System.out.println(stringQueue.dequeue());
// System.out.println(stringQueue.dequeue());
// System.out.println(stringQueue.dequeue());
// System.out.println(stringQueue.dequeue());
// System.out.println(stringQueue.dequeue());
Stack<String> stack = new Stack<String>();
while (!stringQueue.isEmpty())
stack.push(stringQueue.dequeue());
while (!stack.isEmpty())
stringQueue.enqueue(stack.pop());
System.out.println(stringQueue.dequeue());
System.out.println(stringQueue.dequeue());
System.out.println(stringQueue.dequeue());
System.out.println(stringQueue.dequeue());
System.out.println(stringQueue.dequeue());
}
}
代码索引
题目
1.3.7 为Stack添加一个方法peek()，返回栈中最近添加的元素（而不是弹出）。
1.3.7 Add a method peek() to Stack that returns the most recently inserted item on the stack (without popping it).
分析
本人所有简书的算法文章详细分析已经移入小专栏：算法四习题详解，欢迎大家订阅
答案
将
public Item top()
{
return first.item;
}
改为
public Item peek()
{
return first.item;
}
代码索引
题目
1.3.8 给定以下输入，给出DoublingStackOfStrings的数组的内容和大小。
it was - the best - of times - - - it was - the - -
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 - -
答案
public class DoublingStackOfStrings<Item> implements Iterable<Item>{
private int N;
private Item[] items = (Item[])(new Object[1]);
public void push(Item item)
{
if (items.length == N) resize(N * 2);
items[N++] = item;
}
public Item pop()
{
Item item = items[--N];
items[N] = null;
if (N > 0 && N == items.length / 4) resize(N * 2);
return item;
}
private void resize(int max)
{
Item[] items2 = (Item[])(new Object[max]);
for (int i = 0; i < N; i++) {
items2[i] = items[i];
}
items = items2;
}
public int arraySize()
{
return items.length;
}
public Iterator<Item> iterator() {
// TODO Auto-generated method stub
return new ArrayIterator();
}
private class ArrayIterator implements Iterator<Item>{
private int i = N;
public boolean hasNext(){
return i > 0;
}
public Item next(){
return items[--i];
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
DoublingStackOfStrings<String> stack = new DoublingStackOfStrings<String>();
String[] inputs = StdIn.readAllStrings();
for (int i = 0; i < inputs.length; i++)
{
if (inputs[i].equals("-"))
{
stack.pop();
}
else
{
stack.push(inputs[i]);
}
}
for (String s : stack)
{
System.out.print(s + " ");
}
System.out.println();
System.out.println("ArraySize: " + stack.arraySize());
System.out.println();
}
}
代码索引
视频讲解
点此观看分析视频：顶级程序员教你学算法(29)-Queue概念(1.3.6-1.3.8)
广告
我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。
