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

Очередь - C++

Восстановить пароль Регистрация
 
AlexP11223
36 / 37 / 4
Регистрация: 20.04.2011
Сообщений: 288
21.04.2011, 17:03     Очередь #1
Задание из Лафоре, глава про массивы.
весь текст задания
Очередь — это устройство для хранения данных, похожее на стек. Отли-
чие в том, что в стеке последний сохраненный элемент будет первым
извлеченным, тогда как в очереди первый сохраненный элемент будет
первым извлеченным. То есть в стеке используется подход «последний
вошел — первый вышел» (LJFO), а в очереди используется подход «пер-
вый вошел — первый вышел» (FIFO). Очередь похожа на простую оче-
редь посетителей магазина: первый, кто встал в очередь, будет обслужен
первым.
Перепишите программу STAKARAY из этой главы, включив в нее класс
queue вместо класса stack. Кроме того, класс должен иметь два метода:
один, называемый put(), для помещения элемента в очередь; и другой, на-
зываемый get(), для извлечения элемента из очереди. Эти методы эквива-
лентны методам push() и pop() класса stack.
Оба класса, stack и queue, используют массив для хранения данных. Одна-
ко вместо одного поля top типа int, как в классе stack, вам понадобятся два
поля для очереди: одна, называемая head, указывающая на начало очере-
ди; и вторая, taiL, указывающая на конец очереди. Элементы помещаются
в конец очереди (как посетители банка, становящиеся в очередь), а извле-
каются из начала очереди. Конец очереди перемещается к началу по мас-
сиву по мере того, как элементы добавляются и извлекаются из очереди.
Такие результаты добавляют сложности: если одна из двух переменных head или tail примут значение конца массива, то следует вернуться на на-
чало. Таким образом, вам нужно выражение типа
if ( tail == М А Х - 1 )
tail = -1:
для возврата переменной tail и похожее выражение для возврата перемен-
ной head. Массив, используемый в очереди, иногда называют круговым
буфером, так как начало и конец очереди циркулируют по нему вместе с
ее данными
Код Stakaray
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
class Stack
   {
   private:
      enum { MAX = 10 };        //(non-standard syntax)
      int st[MAX];              //stack: array of integers
      int top;                  //number of top of stack
   public:
      Stack()                   //constructor
         { top = 0; }
      void push(int var)        //put number on stack
         { st[++top] = var; }
      int pop()                 //take number off stack
         { return st[top--]; }
   };
////////////////////////////////////////////////////////////////
int main()
   {
   Stack s1;
 
   s1.push(11);
   s1.push(22);
   cout << "1: " << s1.pop() << endl;  //22
   cout << "2: " << s1.pop() << endl;  //11
   s1.push(33);
   s1.push(44);
   s1.push(55);
   s1.push(66);
   cout << "3: " << s1.pop() << endl;  //66
   cout << "4: " << s1.pop() << endl;  //55
   cout << "5: " << s1.pop() << endl;  //44
   cout << "6: " << s1.pop() << endl;  //33
   return 0;
   }

Все вроде бы понятно и частично сделал, но мозг взрывает
если одна из двух переменных head или tail примут значение конца массива, то следует вернуться на начало. Таким образом, вам нужно выражение типа
if ( tail == М А Х - 1 )
tail = -1:
для возврата переменной tail и похожее выражение для возврата перемен-
ной head.
Почему МАХ - 1, а не просто МАХ?
Почему -1, а не 0? (если так, как в примере стека, то там с 1 начинается) Или это из-за того, что предполагается добавлять элемент с помощью [++tail], а head нужно возвращать на 0?

Кто занимался по Лафоре и сохранился код задания - покажите плз)

Добавлено через 1 час 59 минут
Вроде все понял и решил
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
#include <iostream>
#include <conio.h>
using namespace std;
////////////////////////////////////////////////////////////////
class queue
{
private:
    static const int MAX = 10;
    int qu[MAX];              
    int head;             
    int tail;
    unsigned int el; 
public:
    queue()                  
    { head = 0; tail = -1; el = 0; }
    void put(int var)        
    {
        if(tail == MAX - 1)
            tail = -1;
        if(el == MAX)
            cout << "Error: queue is full." << endl;
        else
        {qu[++tail] = var; el++;}
    }
    int get()                
    {
        if(head == MAX)
            head = 0;
        if(el == 0)
        {cout << "Error: no elements in queue" << endl; return 0;}
        else { el--; return qu[head++];}
    }
};
////////////////////////////////////////////////////////////////
int main()
{
    queue q1;
    char ans;
    int n;
 
    q1.put(11);
    q1.put(22);
    cout << "1: " << q1.get() << endl;   
    cout << "2: " << q1.get() << endl;   
    q1.put(33);
    q1.put(44);
    q1.put(55);
    q1.put(66);
    cout << "3: " << q1.get() << endl;  
    cout << "4: " << q1.get() << endl;   
    cout << "5: " << q1.get() << endl;  
    cout << "6: " << q1.get() << endl;   
 
    do
    {
        cout << "\nPress P to put element or G to get element" << endl; ans = getche(); cout << endl;
        switch(ans)
        {
        case 'p':
        case 'P':
            cout << "Enter value: ";
            cin >> n;
            q1.put(n);
            break;
        case 'g':
        case 'G':
            n = q1.get();
            if(n != 0)
                cout << "The value is: " << n << endl;
            break;
        }
        cout << "Continue?(y/n)";
    }while(getche()!='n');
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.04.2011, 17:03     Очередь
Посмотрите здесь:

Задача на очередь (вывод сообщения, что очередь пуста) C++
C++ Очередь
Очередь C++
C++ Очередь (сделать очередь, чтобы добавляло, удаляло, читало. Не STL.)
C++ Очередь
Создать очередь. Добавить элемент в очередь. Удалить элемент из очереди C++
Очередь, теория. Очередь на шести стеках C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
mansp
18 / 18 / 0
Регистрация: 07.11.2010
Сообщений: 136
21.04.2011, 17:35     Очередь #2
потому что tail у тебя просто напросто не может быть равен МАХ последний элемент твоей очереди будет qu[MAX-1]

Добавлено через 6 минут
встречный вопрос мож кто знает как проверить заполнена ли круговая очередь?
вот до чего пока додумался...
Код
template <typename Type> bool Queue<Type>::full(void)
{
	if(back>front)
		return (back-front)==mx;
	if(back<=front)
return (mx-(front - back))==mx;
}
но если очередь будет пустая тогда back=front . return(mx-(front - back))==mx будет true;
mx- размер очереди
back указывает на елемент после последнего
front указывает на первый елемент
Yandex
Объявления
21.04.2011, 17:35     Очередь
Ответ Создать тему
Опции темы

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