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

@Sobaka21 · 25.01.2012, 19:58. **Показов** 13635. **Ответов** 10

Студворк — интернет-сервис помощи студентам

Как реализовать очередь с помощью массива????

go · 25.01.2012, 20:03

Очень давно писал, где-то год назад, но код сохранился

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

Не по теме:

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

@NoMasters · 26.01.2012, 00:19

Не по теме:

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

silent_1991 · 26.01.2012, 00:58

Не по теме:

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

@NoMasters · 26.01.2012, 01:12

Не по теме:

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

@easybudda · 26.01.2012, 03:41

Сообщение от NoMasters

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

Очень хотелось бы реализацию посмотреть. Мне вот тоже не представляется очередь на массиве без сдвигов. Кольцевой буфер, кстати, тоже лучше на списке делать по-моему...

silent_1991 · 26.01.2012, 04:52

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 **[ТС]**

Сообщение от 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 · 26.01.2012, 20:23

Сообщение от Sobaka21

И почему там нет удаления???

Удаления??? Вы имеете ввиду сдвиг? Зачем он в такой реализации.

@easybudda · 27.01.2012, 02:21

Сообщение от 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);
}

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@Sobaka21 Заблокирован

	Реализация очереди массивом 25.01.2012, 19:58. Показов 13635. Ответов 10 Метки нет (Все метки) Как реализовать очередь с помощью массива???? 0

silent_1991
	26.01.2012, 00:04
	Не по теме: Да уж, только очередь на массиве и реализовывать... 1

@NoMasters
	26.01.2012, 00:19
	Не по теме: silent_1991, не скажи, мне тут недавно показывали весьма годную версию. Правда, постоянной максимальной длинны. 0

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

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