Форум программистов, компьютерный форум CyberForum.ru

Реализация очереди массивом - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 41, средняя оценка - 4.80
Sobaka21
Заблокирован
25.01.2012, 19:58     Реализация очереди массивом #1
Как реализовать очередь с помощью массива????
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
25.01.2012, 20:03     Реализация очереди массивом #2
Очень давно писал, где-то год назад, но код сохранился
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
 
using namespace std;
 
#define SIZE 100
#define PRINT(A) cout << endl << #A << endl; 
 
class queue {
    int q[SIZE];
    int sloc, rloc;
public:
    void init ();
    void qput (int val);
    int qget ();
};
 
void queue::init()
{
    rloc = sloc = 0;
}
 
void queue::qput(int val)
{
    if ( sloc == SIZE ) {
        PRINT ( QUEUE filled with );
        return ;
    }
    q[++sloc] = val;
}
 
int queue::qget() 
{
    if ( rloc == sloc ) {
        PRINT ( QUEUE 0 );
        return 0;
    }
    return q[++rloc] ;
}
 
 
int main(int argc, char* argv[])
{
    queue q1;
    int value;
    int i;
    const int COUNT = 3;
 
    q1.init ();
 
    for ( i = 0 ; i < COUNT ; ++i)
    {
        cout << " Enter val = ";
        cin >> value ;
        q1.qput(value);
    }
 
    cout << " QUEUE : " ;
 
    for ( i = 0 ; i < COUNT ; ++i )
        cout << q1.qget() << "   ";
 
    cout << endl;
 
 
    system ("pause");
    return 0;
}
silent_1991
26.01.2012, 00:04
  #3

Не по теме:

Да уж, только очередь на массиве и реализовывать...

NoMasters
26.01.2012, 00:19
  #4

Не по теме:

silent_1991, не скажи, мне тут недавно показывали весьма годную версию. Правда, постоянной максимальной длинны.

silent_1991
26.01.2012, 00:58
  #5

Не по теме:

NoMasters, а в двух словах можно написать, как там решалась проблема с эффективностью? Всё таки мне без постоянного сдвига элементов не представляется возможным написать очередь на массиве (правда, мозг особо напрягать тоже не хочется, не вижу смысла в таких извращениях )

NoMasters
26.01.2012, 01:12
  #6

Не по теме:

Ничего не надо сдвигать. Есть по индексу для записи и чтения, которые бегают по кругу, весьма эффективно.

easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
26.01.2012, 03:41     Реализация очереди массивом #7
Цитата Сообщение от NoMasters Посмотреть сообщение
Ничего не надо сдвигать. Есть по индексу для записи и чтения, которые бегают по кругу, весьма эффективно.
Очень хотелось бы реализацию посмотреть. Мне вот тоже не представляется очередь на массиве без сдвигов. Кольцевой буфер, кстати, тоже лучше на списке делать по-моему...
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
26.01.2012, 04:52     Реализация очереди массивом #8
easybudda, полагаю, что-то в этом роде:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
class FixedSizeQueueIsEmptyException : public std::exception
{
public:
    virtual ~FixedSizeQueueIsEmptyException() throw()
    {
    }
    
    virtual const char *what() const throw()
    {
        return "queue is empty";
    }
};
 
class FixedSizeQueueIsFullException : public std::exception
{
public:
    virtual ~FixedSizeQueueIsFullException() throw()
    {
    }
    
    virtual const char *what() const throw()
    {
        return "queue is full";
    }
};
 
template<typename T, size_t N>
class FixedSizeQueue
{
public:
    typedef T value_type;
    typedef size_t size_type;
    
public:
    FixedSizeQueue():
    m_top(0),
    m_bottom(0),
    m_size(0)
    {
    }
    
    size_type size() const
    {
        return m_size;
    }
    
    bool empty() const
    {
        return size() == 0;
    }
    
    bool full() const
    {
        return size() == N;
    }
    
    void push(const T& value)
    {
        if (full())
            throw FixedSizeQueueIsFullException();
        
        m_queue[m_bottom] = value;
        
        m_bottom = s_next_bottom();
        ++m_size;
    }
    
    void pop()
    {
        if (empty())
            throw FixedSizeQueueIsEmptyException();
        
        m_top = s_next_top();
        --m_size;
    }
    
    T top() const
    {
        if (empty())
            throw FixedSizeQueueIsEmptyException();
        
        return m_queue[m_top];
    }
    
private:
    size_type s_next_loop_count(size_type counter, size_type size) const
    {
        return ++counter == size ? 0 : counter;
    }
    
    size_type s_next_top() const
    {
        return s_next_loop_count(m_top, N);
    }
    
    size_type s_next_bottom() const
    {
        return s_next_loop_count(m_bottom, N);
    }
    
private:
    value_type m_queue[N];
    size_type m_top;
    size_type m_bottom;
    size_type m_size;
};
Добавлено через 2 минуты
easybudda, хотелось бы обратить внимание (на всякий случай) на то, что речь шла о реализации очереди
Цитата Сообщение от NoMasters Посмотреть сообщение
постоянной максимальной длинны
Sobaka21
Заблокирован
26.01.2012, 17:08  [ТС]     Реализация очереди массивом #9
Цитата Сообщение от go Посмотреть сообщение
Очень давно писал, где-то год назад, но код сохранился
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
 
using namespace std;
 
#define SIZE 100
#define PRINT(A) cout << endl << #A << endl; 
 
class queue {
    int q[SIZE];
    int sloc, rloc;
public:
    void init ();
    void qput (int val);
    int qget ();
};
 
void queue::init()
{
    rloc = sloc = 0;
}
 
void queue::qput(int val)
{
    if ( sloc == SIZE ) {
        PRINT ( QUEUE filled with );
        return ;
    }
    q[++sloc] = val;
}
 
int queue::qget() 
{
    if ( rloc == sloc ) {
        PRINT ( QUEUE 0 );
        return 0;
    }
    return q[++rloc] ;
}
 
 
int main(int argc, char* argv[])
{
    queue q1;
    int value;
    int i;
    const int COUNT = 3;
 
    q1.init ();
 
    for ( i = 0 ; i < COUNT ; ++i)
    {
        cout << " Enter val = ";
        cin >> value ;
        q1.qput(value);
    }
 
    cout << " QUEUE : " ;
 
    for ( i = 0 ; i < COUNT ; ++i )
        cout << q1.qget() << "   ";
 
    cout << endl;
 
 
    system ("pause");
    return 0;
}
А можно с объяснением по строчкам??? И почему там нет удаления???
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
26.01.2012, 20:23     Реализация очереди массивом #10
Цитата Сообщение от Sobaka21 Посмотреть сообщение
И почему там нет удаления???
Удаления??? Вы имеете ввиду сдвиг? Зачем он в такой реализации.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.01.2012, 02:21     Реализация очереди массивом
Еще ссылки по теме:

C++ Простейшая реализация стека и очереди
Реализация очереди на основе связанного списка C++
Реализация очереди: код не компилируется C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
27.01.2012, 02:21     Реализация очереди массивом #11
Цитата Сообщение от silent_1991 Посмотреть сообщение
полагаю, что-то в этом роде
Ну я примерно так же думал... Вот решил повыпендриваться
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <stdio.h>
#include <stdlib.h>
 
enum STATE_CODES { SC_OK = 0, SC_EMPTY = 1, SC_FULL = 2, SC_WRONGPTR = 4 };
 
typedef struct FIXED_QUEUE {
    int *  fq_ptr;
    int    fq_read;
    int    fq_write;
    int    fq_size;
    int    fq_state;
} fqueue_t;
 
fqueue_t * new_queue(int size){
    fqueue_t * queue;
    
    if ( size < 1 || ! ( queue = malloc(sizeof(fqueue_t)) ) )
        return NULL;
    
    if ( ! ( queue->fq_ptr = malloc(sizeof(int) * size) ) ){
        free(queue);
        return NULL;
    }
    
    queue->fq_read = 0;
    queue->fq_write = 0;
    queue->fq_size = size;
    queue->fq_state = SC_EMPTY;
    
    return queue;
}
 
void del_queue(fqueue_t * queue){
    free(queue->fq_ptr);
    free(queue);
}
 
int push(fqueue_t * queue, const int value){
    if ( ! queue )
        return SC_WRONGPTR;
        
    if ( queue->fq_state == SC_FULL )
        return SC_FULL;
    
    queue->fq_ptr[queue->fq_write] = value;
    
    if ( ++(queue->fq_write) == queue->fq_size )
        queue->fq_write = 0;
    
    queue->fq_state = ( queue->fq_write == queue->fq_read ) ? SC_FULL : SC_OK;
    
    return SC_OK;
}
 
int pop(fqueue_t * queue, int * valptr){
    if ( ! queue || ! valptr )
        return SC_WRONGPTR;
        
    if ( queue->fq_state == SC_EMPTY )
        return SC_EMPTY;
    
    *valptr = queue->fq_ptr[queue->fq_read];
    
    if ( ++(queue->fq_read) == queue->fq_size )
        queue->fq_read = 0;
    
    queue->fq_state = ( queue->fq_read == queue->fq_write ) ? SC_EMPTY : SC_OK;
    
    return SC_OK;
}
 
#define flush_input() ({ char c; while ( scanf("%c", &c) == 1 && c != '\n' ) ; })
 
enum MENU_CHOICE { MC_QUIT = 0, MC_PUSH = 1, MC_POP = 2, MC_ERROR = 4 };
 
int menu(void){
    int ret;
    
    printf("\n----------------------------------------------------------------------\n");
    printf("%d - push value\n", MC_PUSH);
    printf("%d - pop value\n", MC_POP);
    printf("%d - quit\n", MC_QUIT);
    printf("----------------------------------------------------------------------\n\n> ");
    
    if ( scanf("%d", &ret) != 1 )
        ret = MC_ERROR;
    
    flush_input();
    return ret;
}
 
#define QUEUE_SIZE 5 /* маленькая такая очередь... */
 
int main(void){
    fqueue_t * fq;
    int val, ret;
    
    if ( ! ( fq = new_queue(QUEUE_SIZE) ) ){
        fprintf(stderr, "Memory error!\n");
        exit(1);
    }
    
    while ( ( ret = menu() ) != MC_QUIT ){
        switch ( ret ) {
            case MC_PUSH :
                printf("Value: ");
                if ( scanf("%d", &val) != 1 ){
                    fprintf(stderr, "Try to patch your hands.sys file\n");
                    flush_input();
                    break;
                }
                switch ( push(fq, val) ){
                    case SC_OK :
                        printf("Ok.\n");
                        break;
                    case SC_FULL :
                        printf("Queue is full!\n");
                        break;
                    case SC_WRONGPTR :
                        fprintf(stderr, "Wrong pointer exception!\n");
                        exit(1);
                    default :
                        fprintf(stderr, "Unknown error!\n");
                        exit(1);
                }
                break;
            case MC_POP :
                switch ( pop(fq, &val) ){
                    case SC_OK :
                        printf("Got value %d\n", val);
                        break;
                    case SC_EMPTY :
                        printf("Queue is empty!\n");
                        break;
                    case SC_WRONGPTR :
                        fprintf(stderr, "Wrong pointer exception!\n");
                        exit(1);
                    default :
                        fprintf(stderr, "Unknown error!\n");
                        exit(1);
                }
                break;
            default :
                fprintf(stderr, "Wrong menu choice!\n");
                break;
        }
    }
    
    del_queue(fq);
    printf("Good bye!\n");
    
    exit(0);
}
Yandex
Объявления
27.01.2012, 02:21     Реализация очереди массивом
Ответ Создать тему
Опции темы

Текущее время: 13:40. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru