cs210算法与数据结构(二)

Lecture 7 Stacks and Queues1

Stack Interface

堆栈机制称为后进先出（LIFO），因为插入的最后一项是删除的第一项

对于stack，我们有以下几件操作可以进行:
pop ( ) –pop the top item off the stack 将新的元素移至顶部
push ( ) –put another item onto the top 将顶部元素移除
peek ( ) –look at the top item and copy it 复制顶部元素

makeEmpty(): Remove all items from the stack
isEmpty():True if stack is empty, false otherwise
isFull():True if stack is full, false otherwise

使用Java实现一个Stack

public class Stack { 
    private int maxSize;   // size of stack array 
    private long[] stackArray; 
    private int top;   // top of stack 
    
    public Stack(int s) {  
        // constructor 
        
        maxSize = s; // set array size 
        stackArray= new long[maxSize];   // create array 
        
        top = -1;   // no items yet 
        }
    }

    public void push(long j) { 
        // put item on top of stack
        top++;
        stackArray[top] = j; // increment top, insert item
    }

    public long pop() { 
        // take item from top of stack
        return stackArray[top--]; 
        //access item, decrement top
        //注意这里是top--，意味着先赋值再--。换言之，先得到这个long，然后再把顶部回压
    }

    //注意这里的--,a++是先进行了分配再进行++的操作
    //而++a是先进行了++的操作再进行了分配

    public long peek(){
        // peek at top of stack
        return stackArray[top] ; 
    }


    public boolean isEmpty() { 
        // true if stack is empty
        return (top ==-1);
        }
    public boolean isFull() { 
        // true if stack is full
        return (top ==maxSize-1);
        }
    public void makeEmpty() { 
        // empty stack
        top = -1;
    }

Queues

Queues即是按顺序处理
队列使用先进先出系统（FIFO）
插入是在队列的一端，即队列的后面进行的

使用Java实现一个Queues

public class Queue{
    private int maxSize;
    private long[] queArray;
    private int front;
    private int rear;
    private int nItems;


    public Queue(int s) { 
        // constructor
        maxSize= s;
        queArray= new long[maxSize];
        front = 0;
        rear = -1;
        nItems= 0;
    }

    public boolean insert(long j) { 
        // put item at rear of queue
        if(isFull()) 
            return false; //don’t insert if full
            
        if(rear == maxSize-1) // deal with wraparound
        rear = -1;
        
        rear++;
        queArray[rear] = j; // increment rear and insert
        
        nItems++; // one more item
        return true; //successfully inserted
    }

    public Long remove() { 
        // take item from front of queue
        
        if(isEmpty()) 
            return null; //don’t remove if empty
        long temp = queArray[front];// get value and incrfront
        
        front++;
        
        if(front == maxSize) // deal with wraparound
            front = 0;
        
        nItems--; // one less item
        return temp;
    }

    public long peekFront() { 
        // peek at front of queue
        return queArray[front];
    }
    
    public booleanisEmpty() { 
        // true if queue is empty
        return (nItems==0);
    }

    public booleanisFull() { 
        // true if queue is full
        return (nItems==maxSize);
    }
    public int size() { 
        // number of items in queue
        return nItems;
    }


}

处理wraparound的情况可以看PPT或者其他相关理论的图更容易理解：
因为我们在加入和移除(特别是remove)的时候并没有处理头front空出来的问题，因此所谓的头尾不是数组的头尾，而是我们front和rear的位置

双端队列 Deque (double-ended queue)

它意味着我们可以在任一一端插入和删除物品，它不再有“前后”的概念呢，而是以左右的概念代替

而Deque是可以代表前面两种数据结构的：

Stack实质上就是只要对于一端操作的Deque:
insertRight()
removeRight()

Queue则是对于左右各有且仅有一种操作的Deque:
insertRight()
removeLeft()

deque实际上是一种比堆栈或队列更通用的数据结构，但没有经常被使用

优先级队列 Priority Queue

优先级队列是这样一种队列，其中的项目不只是在后面加入
而是根据其优先级将其放入队列中

public void insert(long item) { 
    // insert item
    if(nItems== 0){ // if no items,
        queArray[0] = item; // insert at 0

    }else{ // if some items,
        int j = nItems; // start at end
        while(j > 0 && queArray[j-1] > item){ 
            // while new item larger
            
            queArray[j] = queArray[j-1]; // shift upward
            j--; // decrement j
        }
        
        queArray[j] = item; // insert it
    }
    nItems++; // increase items}

Lecture 8 Linked Lists

链表 Linked List

链表是由一系列链接组成的抽象数据结构

链表的每一个节点node(也叫做链接link)包括以下两个数据：
1.数据data
2.下一个节点的连接

对比数组

1.当数组装满时，扩展它们并不容易；另一方面，数组浪费空间，因为它们并不总是满的
2.在数组中插入和删除都是很困难的

链表避免了所有这些问题，因为它们可以通过改变它们指向的项目来调整它们的顺序——不会浪费内存，并且可以轻松添加额外的链接

结构

所有链接都包含对列表中下一个链接的引用
链表类只需要存储对第一个链接的引用，因为后续的引用也需要通过一步步推导得出
Link类存储一些数据和对下一个链接的引用

实现

class LinkedList {
    private Link first;

    public LinkedList( ){
        first= null;
        }

    public booleanisEmpty( ){
        return (first== null);
        }

    ...
}

链表仅包含对第一个链接的引用
第一个链接的引用最初设置为null

public class Link {
    public int data;
    public Link next;
    public Link(int datain) {
         // constructor
         data = datain; // initialize data // 'next' is automatically set to null
    }
}

操作

首先自然是插入链表头的操作：找元素，改连接即可

public void insertHead(int number) {
    Link newLink = new Link(number);
    newLink.next= first;
    first = newLink;
}

删除链表头：断开与第一个节点的连接，然后设置新的连接

public Link deleteHead() {
    Link temp = first;
    first = first.next;
    return temp;
}

遍历链表：
使用链表时，我们必须从链的头部开始，按照需求一步一步寻找我们的目标

不可能进行二分查找——链表的一大缺点

public void display {
    Link current = first; // start with first link
    while(current != null) {
        current.displayLink(); //print out the link
        current = current.next; //keep going until you come to the end
    }
}

从链表中间删除某一个元素：
主要是找到该元素的前一个元素与后一个元素
然后将要删除的元素的前后元素相连接，自然这个元素就被删除了

public Link delete(int key) { // delete link with given ke
    Link current = first; // search for link
    Link previous = first; //put these equal to first Link
    while(current.data!= key) {
        if(current.next== null) { 
            return null; 
        } // didn't find it
        else {
            previous = current; // go to next link
            current = current.next;
        }
    } // found it
    
    if(current == first){ // if first link,
        first = first.next; // change first
    }else{ // otherwise,
    previous.next = current.next; // bypass it
    }
    return current;
}

双端链表 Double-Ended Linked Lists

双端列表类似于普通链表，但具有一个附加功能:它引用了最后一个链接以及第一个链接

这允许在末尾和开头插入或删除新链接
便于实现队列（项目在一端到达，在另一端离开）

public class Link {
    public int data;
    public Link next;
    public Link previous;
}

现在每次我们插入或删除一个链接，我们必须处理四个链接而不是两个

换言之，现在我们每次要进行“更新”操作的时候，都需要处理两个节点的两个连接点

现在我们可以在列表中向后或向前移动

各种操作与单向一样，不过都改为修改两个节点。我们这里以插入作示例:

public void insertOrdered(long data) { //inserts data in order
    Link current = first; // start at beginning
    while(current !=null && data > current.data) { 
        current = current.next; 
        } // move to next link 
        
    Link newLink = new Link(data); // make new link
    
    if(current == first) { // if insertion at head
        insertHead(data);
    } else if(current == last){ //if insertion at tail
        insertTail(data);
    } else { // somewhere in middle
        newLink.previous = current.previous; // step 1
        current.previous.next= newLink; // step 2
        newLink.next= current; // step 3
        current.previous= newLink; // step 4
    }
}

迭代器 Iterators

我们需要一种方法，可以从一个链接到另一个链接执行一个操作

迭代器总是指向列表中的某个链接
它们与列表相关联，但不是列表的一部分

或者说，迭代器更像是在链表外部的一个通道，它虽然不属于链表结构，但是链表结构可以通过它来完成一些特殊的操作

我们使用Iterator Class来实现这个功能：
包含对数据结构中的项的引用的对象（用于遍历这些结构）通常称为迭代器
使用对象的主要优点是，我们可以创建任意多的引用

class ListIterator() {
    private Link current;
    ...
}

理所当然，我们需要利用链表类来获得一个迭代器，这样我们可以更方便地在使用链表的时候使用迭代器，因此我们加入了getIterator()方法

public void getIterator(){
    LinkedList theList = new LinkedList();
    ListIterator iter1 = theList.getIterator();
    Link aLink = iter1.getCurrent(); //access link at iterator
    iter1.nextLink();// move iterator to next Link
}

完整的迭代器：

class ListIterator{
    private Link current; // current link
    private Link previous; // previous link
    //前一个节点和现在的节点

    private LinkList ourList; // our linked list
    //存储对应的链表，这样可以方便我们访问它
    
    public ListIterator(LinkList list) { 
        // constructor
        ourList = list;
        reset();
    }
        
    public void reset() { 
        // start at 'first'
        current = ourList.getFirst();
        previous = null;
        //将连接点设置为链表首位
    }
    
    public void nextLink() {
        previous = current; //set previous to this
        current = current.next; //set this to next
    }

迭代器方法

其他方法可以使迭代器成为一个灵活而强大的类
•reset（）–将迭代器设置为列表的开始
•nextLink（）–将迭代器移动到下一个链接节点
•getCurrent（）–返回迭代当前所在的链接节点
•atEnd（）–检查迭代器是否在末尾：如果它在列表末尾，则返回true
•insertAfter（）–在迭代器之后插入新链接
•insertBefore（）–在迭代器之前插入新链接
•deleteCurrent（）–删除迭代器上的链接

使用链表的栈 Stacks using Linked Lists

如果我们想要用链表实现一个栈，那么我们应该使用单端单链表，然后对它的头部进行插入和删除即可

class Link {
    public char data; // data item
    public Link next; // next link in list

    public Link(char data) { 
        // constructor
        this.data= data; // initialize data
        }
    }

然后进行list的相关编写：

public class LinkedList{
    private Link first ; 
    
    public LinkedList(){
        first = null ;
    }

    public boolean isEmpty(){
        return (first == null) ; 
    }

    //--------------------------------
    public void insertHead(char date){
        Link newLink = new Link(data);
        newLink.next = first ; 
        //使 newLink ->> old first 
        first = newLink ;
        //当前irst ->> newLink
    }

    public Link removeHead(){
        //删掉首位元素
        Link temp = first ; 
        first = first.next ; 
        //首位移至下一位，则是删除该位
        return temp  ; 
        //return 我们删除的
    }
}

然后把这些统统封装到堆栈中

public class Stack{
    private LinkedList list ; 
    public Stack(){
        list = new LinkedList()s;
    }

    public void push(char data){
        list.insertHead(data);
    }

    public char pop(){
        return list.removeHead().data;
    }
}