Очереди и стэки

@Koketka · Регистрация: 27.11.2009

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

Привет!!!
вот код программы, не пойму где ошибки, не выводит элементы стека на основе массива, и с циклической очередью тоже что то не так...

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
#include<stdio.h>
#include<iostream.h>
#include<fstream.h>
 
int *m1 = new int[10];
 
struct Stack {
  int left, right;
  Stack *p;
};
 
struct Queue {
  int d;
  Queue *p;
};
 
 
Stack *pushS(Stack *top, const int l, const int r);   //stack zatalkivanie
Stack *popS(Stack *top, int &l, int &r);              //stack izvlechenie
Queue *firstQ(int d);                                //ochered formirovanie
void addQ(Queue **end, int d);                        //ochered dobavlenie
int delQ(Queue **beg);                                //ochered viborka
Stack *firstS(int left);                             //stek na spiske formirovanie
void push(Stack **top, int left);                    //stek na spiske +
int pop(Stack **top);                                //stek na spiske -
Queue* head = NULL;
void add(Queue *tmp);                                //ciklicheskaya ochered +
Queue *del();                                        //ciklicheskaya ochered - 
 
 
int main() {
  int i, n, l, left, right;
  cout << "Vvedite kol-vo elementov massiva 1: "; cin >> n;
  int *M = new int[n];
  cout << "Vvedite elementi massiva: ";
  for (l = 0; l < n; l++) cin >> M[l];
 
  Stack *top = 0;
  top = pushS(top, 0, n - 1);
  cout << "Stack na massive: ";
  while (top) 
    cout << popS(top, left, right) << "  ";
  cout << endl;
 
  Queue *beg = firstQ(1);                            //ukazatel na nachalo
  Queue *end = beg;                                  //ukazatel na konec
  for(l = 1; l < n; l++) addQ(&end, M[l]);
  cout << "Prostaya ochered: ";
  while (beg)
    cout << delQ(&beg) << " ";
  cout << endl;
  
  top = firstS(1);
  for (i = 1; i < n; i++) push(&top, M[i]);
  cout << "Stack na spiske: ";
  while (top)
    cout << pop(&top) << " ";
  cout << endl;
 
  char s[1];
  gets(s);
 
  return 0;
 
}
 
/*stek na baze massiva + */
Stack *pushS(Stack *top, const int l, const int r) {
  Stack *pv = new Stack;
  pv->left = l;
  pv->right = r;
  pv->p = top;
}
 
/*stek na baze massiva - */
Stack *popS(Stack *top, int &l, int &r) {
  Stack *pv = top->p;
  l = top->left;
  r = top->right;
  delete top;
  return pv;
}
 
/*prostaya ochered formirovanie*/
Queue *firstQ(int d){
  Queue *pv = new Queue;
  pv->d = d;
  pv->p = 0;
  return pv;
}
 
/*prostaya ochered + */
void addQ(Queue **end, int d){
  Queue *pv = new Queue;
  pv->d = d;
  pv->p = 0;
  (*end)->p = pv;
  *end = pv;
}
 
/*prostaya ochered - */
int delQ(Queue **beg){
  int temp = (*beg)->d;
  Queue *pv = *beg;
  *beg = (*beg)->p;
  delete pv;
  return temp;
}
 
/*stek na spiske formirovanie*/
Stack *firstS(int left){
  Stack *pv = new Stack;
  pv->left = left;
  pv->p = 0;
  return pv;
}
 
/*stek na spiske + */
void push(Stack **top, int left){
  Stack *pv = new Stack;
  pv->left = left;
  pv->p = *top;
  *top = pv;
}
 
/*stek na spiske - */
int pop(Stack **top){
  int temp = (*top)->left;
  Stack *pv = *top;
  *top = (*top)->p;
  delete pv;
  return temp;
}
 
/*ciklicheskaya ochered + */
void add(Queue *tmp, int d){
  Queue *tail = new Queue ;
  tail->d = tmp->d;
  tail->p = head;
  Queue *ip = tail->p;
  while(!(ip->p==head))   ip = ip->p;
  ip->p = tail;    
}
 
/*ciklicheskaya ochered - */
Queue *del(Queue *tmp){
  tmp = head;
  head = (head==head->p)?NULL:head->p;        
  return tmp;  
}

заранее спасибо

@Aye Aye · 18.12.2009, 11:32

функция Stack *pushS(Stack *top, const int l, const int r) {...} не заполняет стек. Среди её агрументов нет значения, которое нужно вставить в стек.

@Koketka · 19.12.2009, 02:24 **[ТС]**

а вот эти функции правильно написаны?!!

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*stek na baze massiva + */
Stack *pushS(Stack *top, const int l, const int r) {
  Stack *pv = new Stack;
  pv->left = l;
  pv->right = r;
  pv->p = top;
}
 
/*stek na baze massiva - */
Stack *popS(Stack *top, int &l, int &r) {
  Stack *pv = top->p;
  l = top->left;
  r = top->right;
  delete top;
  return pv;
}

@outoftime · 19.12.2009, 09:37

/*stek na baze massiva + */
а куда делось top = pv ?

Добавлено через 1 минуту
/*stek na baze massiva - */
Stack *pv = top - для стека вроде так

@Sekt · 19.12.2009, 12:58

C++
1
2
3
4
5
6
Stack *pushS(Stack *top, const int l, const int r) {
  Stack *pv = new Stack;
  pv->left = l;
  pv->right = r;
  pv->p = top;
}

Поставте return pv;
P.s

C++
1
const int l,int r;

необязательно.

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

функция Stack *pushS(Stack *top, const int l, const int r) {...} не заполняет стек. Среди её агрументов нет значения, которое нужно вставить в стек.

Все заполняется stack работает.
P.z не понимаю для чего тут массив вообще.

@Aye Aye · 19.12.2009, 13:15

если стек работает то где же тогда поле данных в обявлении структуры?

C++
1
2
3
4
struct Stack {
  int left, right;
  Stack *p;
};

и где его заполнение?

C++
1
2
3
4
5
6
Stack *pushS(Stack *top, const int l, const int r) {
  Stack *pv = new Stack;
  pv->left = l;
  pv->right = r;
  pv->p = top;
}

и да, стек здесь явно не на массиве.

Добавлено через 5 минут
стек на массиве это

C++
1
2
3
4
5
6
7
8
struct Stack{
         int index;
         const max=256;
         int info[max];
         Stack(){index=0;}
         int pop(){if (index>1){ info[index];index--;}else cout <<"empty stack\n";}
         void push(int ii){if (index<max){ index++;info[index]=ii;}else cout << "stack is full\n";}
};

примерно так.
использование

C++
1
2
3
Stack S;
S.push(5);
int i=S.pop();

@Aye Aye · 31.12.2009, 10:43

вот рабочий вариант:

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
#include <iostream>
#include <conio.h>
using namespace std;
struct Stack{
         int index;
         int max;
         int info[256];
         Stack(){index=0;max=256;}
         int pop()
         {
             if (index > 0)
             {
                index--; 
                return info[index+1];
             }
             else
             {
                 cout <<" empty stack ";
                 return 0;
             }
         }
         void push(int ii)
         {
              if (index<max)
              {
                 index++;
                 info[index]=ii;
              }
              else cout << " stack is full ";
         }
};
int main()
{
    Stack S;
    S.push(5);
    S.push(6);
    cout << S.pop();
    cout << S.pop();
    cout << S.pop();
    getch();
}

@grrrrr · 13.09.2011, 16:09

Aye Aye, в чем разница - стек на массиве и просто стек? Я так понимаю, если на массиве то - есть граница - начало и конец массива, по нему мы перемещаемся используя стек. Это мне понятно. А в каких случаях применяется стек не на массиве? И где он используется? Можно простой пример?

@Сыроежка · 13.09.2011, 18:51

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

Aye Aye, в чем разница - стек на массиве и просто стек? Я так понимаю, если на массиве то - есть граница - начало и конец массива, по нему мы перемещаемся используя стек. Это мне понятно. А в каких случаях применяется стек не на массиве? И где он используется? Можно простой пример?

В стандартной библиотеки STL стек - это адаптирующий контейнер, который для управления своими элементами использует другой стандартный контейнер, например, std::deck.

@Nameless One · 13.09.2011, 18:53

Не по теме:

Сообщение от Сыроежка

std::deck.

только не deck, а deque

@Nameless One · 13.09.2011, 18:56

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

А в каких случаях применяется стек не на массиве?

допустим, когда нужно часто вставлять-удалять элементы из стека. Если он будет сделан на массиве, то будут бОльшие издержки на перераспределение памяти

@grrrrr · 13.09.2011, 23:55

Nameless One спасибо, решил освоить ООП и в первую очередь наталкиваюсь на стеки, списки, очереди, так там не все так просто

@easybudda · 14.09.2011, 00:51

grrrrr, вот незатейливый пример со стеком

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
 
int main(){
    std::string str;
    
    while ( std::cout << "String: " && std::getline(std::cin, str) && ! str.empty() ){
        std::istringstream ist(str);
        std::stack<std::string> stack;
        while ( ist >> str )
            stack.push(str);
        std::cout << "Result: ";
        while ( ! stack.empty() ){
            std::cout << stack.top() << ' ';
            stack.pop();
        }
        std::cout << std::endl;
    }
    
    return 0;
}

Не по теме:

Знатного покойника откопали - почти два года пролежал... :)

@Nameless One · 14.09.2011, 05:48

grrrrr, тут ООП ни при чем

@easybudda · 14.09.2011, 08:32

Не по теме:

Сообщение от Nameless One

тут ООП ни при чем

При желании можно за уши притянуть, вроде "Навыки работы с объектами классов библиотеки STL", ну или как-то так... ;)

Новые блоги и статьи Все статьи Все блоги /
Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .

@Aye Aye 373 / 287 / 97 Регистрация: 17.12.2009 Сообщений: 567
	18.12.2009, 11:32
	функция Stack pushS(Stack top, const int l, const int r) {...} не заполняет стек. Среди её агрументов нет значения, которое нужно вставить в стек. 1

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,360 Записей в блоге: 5
	19.12.2009, 09:37
	/stek na baze massiva + / а куда делось top = pv ? Добавлено через 1 минуту /stek na baze massiva - / Stack *pv = top - для стека вроде так 1

@grrrrr 49 / 49 / 13 Регистрация: 21.04.2009 Сообщений: 265
	13.09.2011, 16:09
	Aye Aye, в чем разница - стек на массиве и просто стек? Я так понимаю, если на массиве то - есть граница - начало и конец массива, по нему мы перемещаемся используя стек. Это мне понятно. А в каких случаях применяется стек не на массиве? И где он используется? Можно простой пример? 0

@grrrrr 49 / 49 / 13 Регистрация: 21.04.2009 Сообщений: 265
	13.09.2011, 23:55
	Nameless One спасибо, решил освоить ООП и в первую очередь наталкиваюсь на стеки, списки, очереди, так там не все так просто 0

@Nameless One 5828 / 3479 / 358 Регистрация: 08.02.2010 Сообщений: 7,448
	14.09.2011, 05:48
	grrrrr, тут ООП ни при чем 0