一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 407|回复: 4
收起左侧

[CS61B_Spring 2015] DISCUSSION 6

[复制链接] |试试Instant~ |关注本帖
karte_polo 发表于 2015-7-4 23:39:41 | 显示全部楼层 |阅读模式

[其他]CS61B DATA STRUCTURES #6 - 2015-06-01@UC BERKLEY

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
RT~本次是要用两个stack 实现一个queue
 楼主| karte_polo 发表于 2015-7-4 23:42:00 | 显示全部楼层
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());
        }

       
       

}
回复 支持 反对

使用道具 举报

梦在最晴天 发表于 2015-7-5 18:04:23 | 显示全部楼层
真的好的      。
回复 支持 反对

使用道具 举报

Casualet 发表于 2015-8-9 22:04:41 | 显示全部楼层
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());
  }
}

//离最新进度越来越近了。。。。
回复 支持 反对

使用道具 举报

HNAKXR 发表于 2016-2-12 12:55:50 | 显示全部楼层
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. public class SQueue {
  3.         private Stack<Integer> s1;

  4.         public SQueue() {
  5.                 s1 = new Stack<Integer>();
  6.         }

  7.         public void enqueue(int item) {
  8.                 Stack<Integer> s2 = new Stack<Integer>();
  9.                 while (!s1.isEmpty()) {
  10.                         s2.push(s1.pop());
  11.                 }
  12.                 s1.push(item);
  13.                 while (!s2.isEmpty()) {
  14.                         s1.push(s2.pop());
  15.                 }
  16.         }

  17.         public int dequeue() {
  18.                 return s1.pop();
  19.         }
  20. }
复制代码

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 16:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表