[普通教程] Coursera普林斯顿大学公开课Algorithm I总结（一）：栈和队列

[复制链接]

轻舟过

该用户从未签到

258 主题	314 好友	3万积分

第二章

积分: 35715

发表于 2012-10-7 22:11:10 | 显示全部楼层 |阅读模式

╱人◕‿‿◕人╲定下契约

您需要登录才可以下载或查看，没有账号？╱人◕‿‿◕人╲订下契约（注册新用户）

本帖最后由轻舟过于 2012-10-7 22:13 编辑

8月中旬的时候我注册了Coursera上斯坦福大学的Algorithm I的课程，然后一直积极地学习这门课，直到课程结束。虽然注册的时候只是抱着复习一下本科学过的知识的心态，但是在学习的过程中还是学到了不少新的知识。比如本科阶段学习的算法课使用的语言是C语言，是面向过程的，而本课程使用的语言则是Java，于是了解了一些面向对象语言实现数据结构的方法。
栈和队列
栈和队列应该是最简单的数据结构了，栈是LIFO的数据结构，而队列是FIFO的数据结构。这两种数据结构都有两种实现方式，一种是使用链表的实现，而另外一种则是使用数组的实现。
用链表实现的栈每次插入、删除、查看栈顶元素处理的都是头部的元素，而队列插入是插在链表的尾部，查看以及删除元素处理的都是头部元素，基本上维护好指针就OK了。
栈和队列的链表实现不需要事先给定栈和队列的大小，插入元素只需要分配一个节点的空间并将其链到链表上就可以了，删除也是类似，处理好指针，gc会自动回收节点的空间。而数组实现不一样，数组是需要指定长度的，这样数组实现的构造函数与链表实现的构造函数的api就不一样了。解决的方法就是采用一种策略在合适的时候重新分配空间并将原始数组的元素复制到新数组，从而实现数组自动增长和缩短。
当然我们不能在每次插入或删除时调整数组的长度，一个可行的策略是：

在数组满的时候将分配一个两倍于原先数组长度的空间，并复制元素。
在数组1/4满的时候分配一个原先数组1/2长度的空间，并复制元素。

这样N次插入，N次删除所需的时间是O(N)，也就是说均摊下来每次操作的时间是O(1)。
泛型
当然栈和队列需要泛型编程实现，以支持各种类，需要注意的是Java并不支持创建泛型的数组，也就是这样的代码是会报错的：
[mw_shl_code=java,true]s = new Item[capacity];[/mw_shl_code]正确的写法应该是这样：
[mw_shl_code=java,true]s = (Item[]) new Object[capacity];[/mw_shl_code]
迭代器
栈和队列可以实现迭代器接口Iterable，以方便地遍历元素
[mw_shl_code=java,true]public interface Iterable<Item>
{
Iterator<Item> iterator();
}[/mw_shl_code]Iterator也是一个接口：
[mw_shl_code=java,true]public interface Iterator<Item>
{
boolean hasNext();
Item next();
void remove();
}[/mw_shl_code]接口的实现如下：
[mw_shl_code=java,true]public Iterator<Item> iterator() { return new ListIterator(); }
private class ListIterator implements Iterator<Item>
{
private Node current = first;
public boolean hasNext() { return current != null; }
public void remove() { /* not supported */ }
public Item next()
{
 Item item = current.item;
 current = current.next;
 return item;
}
}[/mw_shl_code]实现了接口之后可以用如下的代码来遍历容器:
[mw_shl_code=java,true]for (String s : stack)
StdOut.println(s);[/mw_shl_code]
代码
附Queue.java和Stack.java的实现，代码来自课程的algs4.jar。
[mw_shl_code=java,true]/*************************************************************************
* Compilation: javac Queue.java
* Execution: java Queue < input.txt
* Data files: http://algs4.cs.princeton.edu/13stacks/tobe.txt
*
* A generic queue, implemented using a linked list.
*
* % java Queue < tobe.txt
* to be or not to be (2 left on queue)
*
*************************************************************************/

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
* The <tt>Queue</tt> class represents a first-in-first-out (FIFO)
* queue of generic items.
* It supports the usual enqueue and dequeue
* operations, along with methods for peeking at the top item,
* testing if the queue is empty, and iterating through
* the items in FIFO order.
* 
* All queue operations except iteration are constant time.
* 
* For additional documentation, see <a href="http://algs4.cs.princeton.edu/13stacks">Section 1.3</a> of
* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
*/
public class Queue<Item> implements Iterable<Item> {
private int N; // number of elements on queue
private Node first; // beginning of queue
private Node last; // end of queue

// helper linked list class
private class Node {
 private Item item;
 private Node next;
}

/**
 * Create an empty queue.
 */
public Queue() {
 first = null;
 last = null;
 N = 0;
 assert check();
}

/**
 * Is the queue empty?
 */
public boolean isEmpty() {
 return first == null;
}

/**
 * Return the number of items in the queue.
 */
public int size() {
 return N;
}

/**
 * Return the item least recently added to the queue.
 * @throws java.util.NoSuchElementException if queue is empty.
 */
public Item peek() {
 if (isEmpty()) throw new NoSuchElementException("Queue underflow");
 return first.item;
}

/**
 * Add the item to the queue.
 */
public void enqueue(Item item) {
 Node oldlast = last;
 last = new Node();
 last.item = item;
 last.next = null;
 if (isEmpty()) first = last;
 else oldlast.next = last;
 N++;
 assert check();
}

/**
 * Remove and return the item on the queue least recently added.
 * @throws java.util.NoSuchElementException if queue is empty.
 */
public Item dequeue() {
 if (isEmpty()) throw new NoSuchElementException("Queue underflow");
 Item item = first.item;
 first = first.next;
 N--;
 if (isEmpty()) last = null; // to avoid loitering
 assert check();
 return item;
}

/**
 * Return string representation.
 */
public String toString() {
 StringBuilder s = new StringBuilder();
 for (Item item : this)
 s.append(item + " ");
 return s.toString();
}

// check internal invariants
private boolean check() {
 if (N == 0) {
 if (first != null) return false;
 if (last != null) return false;
 }
 else if (N == 1) {
 if (first == null || last == null) return false;
 if (first != last) return false;
 if (first.next != null) return false;
 }
 else {
 if (first == last) return false;
 if (first.next == null) return false;
 if (last.next != null) return false;

 // check internal consistency of instance variable N
 int numberOfNodes = 0;
 for (Node x = first; x != null; x = x.next) {
 numberOfNodes++;
 }
 if (numberOfNodes != N) return false;

 // check internal consistency of instance variable last
 Node lastNode = first;
 while (lastNode.next != null) {
 lastNode = lastNode.next;
 }
 if (last != lastNode) return false;
 }

 return true;
}

/**
 * Return an iterator that iterates over the items on the queue in FIFO order.
 */
public Iterator<Item> iterator() {
 return new ListIterator();
}

// an iterator, doesn't implement remove() since it's optional
private class ListIterator implements Iterator<Item> {
 private Node current = first;

 public boolean hasNext() { return current != null; }
 public void remove() { throw new UnsupportedOperationException(); }

 public Item next() {
 if (!hasNext()) throw new NoSuchElementException();
 Item item = current.item;
 current = current.next;
 return item;
 }
}

/**
 * A test client.
 */
public static void main(String[] args) {
 Queue<String> q = new Queue<String>();
 while (!StdIn.isEmpty()) {
 String item = StdIn.readString();
 if (!item.equals("-")) q.enqueue(item);
 else if (!q.isEmpty()) StdOut.print(q.dequeue() + " ");
 }
 StdOut.println("(" + q.size() + " left on queue)");
}
}
[/mw_shl_code][mw_shl_code=java,true]/*************************************************************************
* Compilation: javac Stack.java
* Execution: java Stack < input.txt
*
* A generic stack, implemented using a linked list. Each stack
* element is of type Item.
*
* % more tobe.txt
* to be or not to - be - - that - - - is
*
* % java Stack < tobe.txt
* to be not that or be (2 left on stack)
*
*************************************************************************/

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
* The <tt>Stack</tt> class represents a last-in-first-out (LIFO) stack of generic items.
* It supports the usual push and pop operations, along with methods
* for peeking at the top item, testing if the stack is empty, and iterating through
* the items in LIFO order.
* 
* All stack operations except iteration are constant time.
* 
* For additional documentation, see <a href="/algs4/13stacks">Section 1.3</a> of
* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
*/
public class Stack<Item> implements Iterable<Item> {
private int N; // size of the stack
private Node first; // top of stack

// helper linked list class
private class Node {
 private Item item;
 private Node next;
}

/**
 * Create an empty stack.
 */
public Stack() {
 first = null;
 N = 0;
 assert check();
}

/**
 * Is the stack empty?
 */
public boolean isEmpty() {
 return first == null;
}

/**
 * Return the number of items in the stack.
 */
public int size() {
 return N;
}

/**
 * Add the item to the stack.
 */
public void push(Item item) {
 Node oldfirst = first;
 first = new Node();
 first.item = item;
 first.next = oldfirst;
 N++;
 assert check();
}

/**
 * Delete and return the item most recently added to the stack.
 * @throws java.util.NoSuchElementException if stack is empty.
 */
public Item pop() {
 if (isEmpty()) throw new NoSuchElementException("Stack underflow");
 Item item = first.item; // save item to return
 first = first.next; // delete first node
 N--;
 assert check();
 return item; // return the saved item
}

/**
 * Return the item most recently added to the stack.
 * @throws java.util.NoSuchElementException if stack is empty.
 */
public Item peek() {
 if (isEmpty()) throw new NoSuchElementException("Stack underflow");
 return first.item;
}

/**
 * Return string representation.
 */
public String toString() {
 StringBuilder s = new StringBuilder();
 for (Item item : this)
 s.append(item + " ");
 return s.toString();
}

// check internal invariants
private boolean check() {
 if (N == 0) {
 if (first != null) return false;
 }
 else if (N == 1) {
 if (first == null) return false;
 if (first.next != null) return false;
 }
 else {
 if (first.next == null) return false;
 }

 // check internal consistency of instance variable N
 int numberOfNodes = 0;
 for (Node x = first; x != null; x = x.next) {
 numberOfNodes++;
 }
 if (numberOfNodes != N) return false;

 return true;
}

/**
 * Return an iterator to the stack that iterates through the items in LIFO order.
 */
public Iterator<Item> iterator() { return new ListIterator(); }

// an iterator, doesn't implement remove() since it's optional
private class ListIterator implements Iterator<Item> {
 private Node current = first;
 public boolean hasNext() { return current != null; }
 public void remove() { throw new UnsupportedOperationException(); }

 public Item next() {
 if (!hasNext()) throw new NoSuchElementException();
 Item item = current.item;
 current = current.next;
 return item;
 }
}

/**
 * A test client.
 */
public static void main(String[] args) {
 Stack<String> s = new Stack<String>();
 while (!StdIn.isEmpty()) {
 String item = StdIn.readString();
 if (!item.equals("-")) s.push(item);
 else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
 }
 StdOut.println("(" + s.size() + " left on stack)");
}
}[/mw_shl_code]

评分

参与人数 2	宅魂 +1	宅币 +23	贡献 +2	收起理由
风音洛洛		+ 20	+ 2	o(￣▽￣)ブ发糖
没糖给你了	+ 1	+ 3		o(￣▽￣)ブ发糖

查看全部评分

博客什么的求人气 http://bimania.org

合作站点账号登陆

[普通教程] Coursera普林斯顿大学公开课Algorithm I总结（一）：栈和队列

╱人◕‿‿◕人╲定下契约

评分

浏览过的版块