首页 > 试题广场 >

用Object-C定义并实现一个基于数组的循环队列类,当队列

[问答题]
用Object-C定义并实现一个基于数组的循环队列类,当队列放满需支持动态的扩展队列长度。
这个题目说的好简略啊,偷个懒,用NSMutableArray实现一下~

#import <Foundation/Foundation.h>

@interface LoopQueue : NSObject

-( instancetype )initWithItem:( NSObject *)item andCapcity:( NSUInteger )capacity;

-( instancetype )init;

-( void )enqueue:( NSObject *)item;

-( NSObject *)dequeue;

@end


#import "LoopQueue.h"

#define DEFAULT_SIZE 10

@interface LoopQueue ()

@property ( nonatomic ) int first;

@property ( nonatomic ) int last;

@property ( nonatomic ) NSUInteger capacity;

@property ( nonatomic ) NSMutableArray *elementData;

@end


@implementation LoopQueue

-( instancetype )initWithItem:( NSObject *)item andCapcity:( NSUInteger )cap

{

    self . first = - 1 ;

    self . last = - 1 ;

    self . capacity = cap;

    self . elementData = [ NSMutableArray arrayWithCapacity :cap];

    if (item == nil ) {

        return self ;

    }

    [ self . elementData addObject :item];

    return self ;

}

-( instancetype )init

{

    self = [[ LoopQueue alloc ] initWithItem : nil andCapcity : DEFAULT_SIZE ];

    return self ;

}

-( BOOL )isFull

{

    return ( _first == 0 && _last == _capacity - 1 ) || _first == _last + 1 ;

}

-( BOOL )isEmpty

{

    return self . first == - 1 ;

}

-( void )enqueue:( NSObject *)item

{

    if (![ self isFull ]) {

        if ( _last == _capacity - 1 || _last == - 1 ) {

            self . elementData [ 0 ] = item;

            _last = 0 ;

            if ( _first == - 1 ){

                _first = 0 ;

            }

        } else {

            self . elementData [++ _last ] = item;

        }

    } else {

        self . capacity ++;

        self . last ++;

        [ self . elementData addObject :item];

        

    }

}

-( NSObject *)dequeue

{

    if (![ self isEmpty ]) {

        NSObject *tmp = self . elementData [ _first ];

        if ( _first == _last ){

            _last = _first = - 1 ;

        } else if ( _first == _capacity - 1 ){

            _first = 0 ;

        } else {

            _first ++;

        }

        return tmp;

    } else {

        NSLog ( @"Fail :Queue is Empty" );

        return nil ;

    }

}

发表于 2015-09-01 10:29:57 回复(3)
根本不会,只会Android
发表于 2018-04-04 22:23:41 回复(0)
定义一个结构体,以及int变量front,rear用于跟踪数据填充情况。
1.当队列rear+1对数组长度取余等于front时,说明数组已填充满,那么需要扩展,即重新new 数组,长度为原来2倍,然后将原来数据copy新数组中,同时回收旧的数组
2.当rear==front时为空
注:使用rear+1前提是front指定的空间不存放值,这样就可知front==rear时时队列为空,而避免混淆队列是空还是满。
发表于 2015-10-05 10:53:26 回复(2)

#import <Foundation/Foundation.h>

@interface LoopQueue : NSObject

- ( instancetype )initWithItem:(NSObject *)item andCapcity:(NSUInteger )capacity;

- ( instancetype )init;

- ( void )enqueue:(NSObject *)item;
- (NSObject *)dequeue;
@end

#import "LoopQueue.h"

#define Default_size 10

@interface LoopQueue ()

@property ( nonatomic ) int first;

@property ( nonatomic ) int last;

@property ( nonatomic , assign ) NSUInteger capacity;

@property ( nonatomic , copy ) NSMutableArray *elementData;

@end

@implementation LoopQueue

- ( instancetype )initWithItem:( NSObject *)item andCapcity:( NSUInteger )capacity{

    self . first = -1;

    self . last = -1;

    self . capacity = capacity;

    self . elementData = [ NSMutableArray arrayWithCapacity :capacity];

    

    if (item == nil ) {

        return self ;

    }

    [ self . elementData addObject :item];

    return self ;

}

- ( instancetype )init{

    self = [[ LoopQueue alloc ] initWithItem : nil andCapcity : Default_size ];

    return   self ;

}

- ( BOOL )isFull{

    return ( _first == 0 && _last == _capacity -1)|| _first == _last + 1;

}

- ( BOOL )isEmpty{

    return   self . first == -1;

}

- ( void )enqueue:( NSObject *)item{

    if (![ self isFull ]) {

        if ( _last == _capacity -1 || _last == -1) {

            self . elementData [0]=item;

            _last = 0;

            if ( _first == -1) {

                _first = 0;

            }

        } else {

            self . elementData [++ _last ] = item;

        }

    } else {

        self . capacity ++;

        self . last ++;

        [ self . elementData addObject :item];

    }

}

- ( NSObject *)dequeue{

    if (![ self isEmpty ]) {

        NSObject *temp = self . elementData [ _first ];

        if ( _first == _last ) {

            _last = _first = -1;

            

        } else if ( _first == _capacity -1){

            _first = 0;

            

        } else {

            _first ++;

        }

        return temp;

    } else {

        NSLog ( @" 空队列 " );

        return nil ;

    }

}

@end


发表于 2016-09-10 12:30:29 回复(0)

发表于 2016-08-07 19:06:22 回复(0)