[CS61B_Spring 2015] DISCUSSION 6

RT~本次是要用两个stack 实现一个queue

Stack 方面我写了一个mystack类，有POP PUSH 和 IS_EMPTY三个方法，功能和作业里一开头ADT里的STACK 一模一样


public class Squeue {
        mystack main;
        mystack Buffer;
        boolean adding;
        public Squeue(){
                main = new mystack();
                Buffer = new mystack();
                adding = true;
        }
        public void enqueue(int item){
                if (!adding){
                        swap(Buffer,main);
                        adding = true;
                }
                main.push(item);
        }
        private void swap(mystack a,mystack b){
                while (!a.is_empty()){
                        b.push(a.pop());
                }
        }
        public int dequeue(){
                if (adding){
                        swap(main,Buffer);
                        adding =false;
                }
                int r = Buffer.pop();
                return r;
        }
        public static void main(String[] args){
       //Simple Tests
                Squeue s = new Squeue();
                s.enqueue(1);
                s.enqueue(2);
                s.enqueue(3);
                s.enqueue(4);
                s.enqueue(5);
                System.out.println(s.dequeue());
                System.out.println(s.dequeue());
        }

       
       

}

真的好的      。

1:null

2:
  2-1:stack
  2-2:map
  2-3:set
3:
  3-1:use two maps to store k-v and v-k pairs respectively.
      for the method numLessThan(K), just use int count to recore the result, and get the value by iterating through the map.
  3-2:use two priority queues, qu1 and qu2, and a count variable to record the number of items in the current ADT. when we need getMedian():
   if(n%2!=0), we dequeue count/2 items to qu2, and count/2+1 is what we want. we then dequeue the remaining count/2 items to qu2, and then move items in qu2 back to qu1; The procedure is similar for n%2==0;


4:
public class SQueue{
  Stack s1;
  Stack s2;

  public SQueue(){
     s1=new Stack();
     s2=new Stack();
  }
  public void enqueue(int item){
       while(!s2.isEmpty()){
           s1.push(s2.pop());      
       }
       s1.push(item);
       while(!s1.isEmpty()){
           s2.push(s1.pop());  
       }
  }
  public int dequeue(){
     return s2.pop();
  }
  public static void main(String args[]){
      SQueue test= new SQueue();

      test.enqueue(1);
      test.enqueue(2);
      test.enqueue(3);
      test.enqueue(4);
      test.enqueue(5);
      System.out.println(test.dequeue());
      System.out.println(test.dequeue());
      System.out.println(test.dequeue());
      System.out.println(test.dequeue());
      System.out.println(test.dequeue());
  }
}

//离最新进度越来越近了。。。。

1 Assorted ADTs
No questions.

2 Solving Problems with ADTs
Stack
Set
Map

3 More Complicated ADTs
Write this ADT based on Map. Create two maps: K->V and V->K. For numLessThan, invoke keys(), sort the keys and find the number of keys less than K.
Use a List. Sort before getMedian(). Using two priority queues, one for less than median, and the other for larger than median.

4 ADTing in Circles

1. import java.util.Stack;
   
2. 
   
3. public class SQueue {
   
4.         private Stack<Integer> s1;
   
5. 
   
6.         public SQueue() {
   
7.                 s1 = new Stack<Integer>();
   
8.         }
   
9. 
   
10.         public void enqueue(int item) {
    
11.                 Stack<Integer> s2 = new Stack<Integer>();
    
12.                 while (!s1.isEmpty()) {
    
13.                         s2.push(s1.pop());
    
14.                 }
    
15.                 s1.push(item);
    
16.                 while (!s2.isEmpty()) {
    
17.                         s1.push(s2.pop());
    
18.                 }
    
19.         }
    
20. 
    
21.         public int dequeue() {
    
22.                 return s1.pop();
    
23.         }
    
24. }

复制代码