Реализация стека

[kei91]

Здравствуйте, знаю, что есть много литературы и примеров кода по этому вопросу, но мне непонятно все же. Дали "шаблон задания", выглядит так

 class Stack {
 Stack* next;
//...
int value;
};

int main() {
Stack s(10);
s.push(7);
s.push(8);
cout << s.pop();
//...
}

cout << s.pop() - выводит последнее записанное в стек значение, далее надо написать вывод всех значений, записанных в стек. Вот, что попыталась сделать я:

#include "stdafx.h"
#include <iostream>

using namespace std;

class Stack {
      
public:
 Stack* next;
 int value;

 Stack(int _value) {
  value = _value;
 };

 void push(int _value){
  next = new Stack(_value);
  //next[1].value = _value;
 // free(next); 
 }

int pop() { 
 return next[0].value;

}

 void insert() {
	 cout << Stack::value << endl;
 }

};

int main()
{
	Stack s(10);
	s.push(7); 
	s.push(8);
	s.pop();
	cout << s.pop() << endl;
	s.insert();

}

Что я не понимаю: как реализовать запись всех значений в next, ведь же он получается перезаписывается каждый раз.
Помогите, пожалуйста, разобраться.

[Son Of Pain]

Это - достаточно нетипичный шаблон для стека, обычно учат хранить связный список внутри объекта. Тут тебе придется извращаться как-то так, например:

void push(int _value)
{
	Stack* elem = new Stack(value);
	elem->next=next;
	next=elem;
	value=_value;
}

[kei91]

Спасибо большое! Я правильно понимаю, что

 Stack* elem = new Stack(value);

здесь создается указатель на значение стека (в моем случае сначала оно будет равно 10, так?)

 elem -> next = next;

вот здесь не очень понимаю, тут получаем доступ к элементу next и присваиваем ему же значение next, но его же у нас нет изначально или я что-то неправильно понимаю?

И ещё вопрос как можно вывести все элементы, содержащиеся у меня в стеке?
Через next[i].value? Или это совсем бред?

[Son Of Pain]

Мы создаем новый элемент; записываем в него то, что было раньше записано в вершине стека; вместо этого в вершину записываем новое значение; а потом полю next новосозданного элемента присваиваем то, что было в поле next вершины. Проще говоря - вставляем новый элемент в цепочку между вершиной и следующим за ней элементом, если он был. Если его не было - в его поле next просто запишется 0 и ничего страшного не случится

А перебирать элементы проще всего через несколько последовательных вызовов pop (только ее сначала придется написать, да).

А через next[i] обращаться нельзя, это ж единственный указатель )

[kei91]

..., я прошу прощение за свою тупость, но можете ещё объяснить, как вообще происходит запись в стек? Никак я не понимаю, куда вообще записывается что, и как к этой записи обращаться.

Вот у меня изначально создается объект - Stack s(10), значение 10 записывается в value, затем, по методу s.push(7) создается новый элемент и записывается значение 7, опять же в value, но уже нового элемента? Т.е. выделяется ещё одна ячейка памяти под этот элемент? Если да, то как к ней обратиться?

И еще вопрос, вот у меня записано в стеке 10,7,8. Если я пишу Stack::value, он у меня выводит соответственно, последнее записанное значение - 8.
В методе pop() получается я должна вывести, находящееся значение в стеке и удалить это значение, вот это самое 8, и при повторном вызове pop() у меня уже в стеке будет храниться уже предыдущее значение -7. Так?

[Сыроежка]

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

..., я прошу прощение за свою тупость, но можете ещё объяснить, как вообще происходит запись в стек? Никак я не понимаю, куда вообще записывается что, и как к этой записи обращаться.

Вот у меня изначально создается объект - Stack s(10), значение 10 записывается в value, затем, по методу s.push(7) создается новый элемент и записывается значение 7, опять же в value, но уже нового элемента? Т.е. выделяется ещё одна ячейка памяти под этот элемент? Если да, то как к ней обратиться?

И еще вопрос, вот у меня записано в стеке 10,7,8. Если я пишу Stack::value, он у меня выводит соответственно, последнее записанное значение - 8.
В методе pop() получается я должна вывести, находящееся значение в стеке и удалить это значение, вот это самое 8, и при повторном вызове pop() у меня уже в стеке будет храниться уже предыдущее значение -7. Так?

Вы правильно поняли. У вас есть связный список элементов вашего класса, которые собой имитируют работу стека. У стека есть открытый интерфейс. Это методы push, pop и top. Поэтому если вы хотите обратиться к предыдущему элементу стека, вы должны сначала извлечь из него текущий элемент стека.
То есть операция просмотра стека связана с операцией последовательного удаления из стека элементов. В этом и состоит суть стека.
Но у вас в дизайне вашего стека есть проблема. Когда у вас в стеке один элемент, то не понятно, как его удалить и какое при этом будет состояние стека.

[Son Of Pain]

Все правильно, да. Только тебе все же придется чуть переделать этот "шаблон" - внести связный список внутрь объекта полностью. Иначе функции push и pop получатся чересчур эзотеричными )

В общем, добавься ко мне в аську, если еще будут вопросы, там удобнее разбираться.

[kei91]

Спасибо, вроде разобралась =), вот, что у меня вышло

#include "stdafx.h"
#include <iostream>

using namespace std;

class Stack {
      
public:
 
 Stack *next; // указатель на следующий элемент стека
 int value;

 Stack *Head; // верхушка стека

 Stack(int _value) {
  value = _value;
 };



 void push(int _value){
	
	Stack *element = new Stack(value);
	element -> value = _value;
	element -> next = Head; // тащим наверх
	Head = element; // новые значение - на верхушку

 }

int pop() { 
 
	 int element = Head -> value; // берем указатель на 1-ый элемент
	 Head = Head -> next; // верхушка переносится
	 return element;

}


};

int main()
{
	Stack s(10);
	s.push(7); 
	s.push(8);
	cout << s.pop() << endl;
	cout << s.pop() << endl;
//	cout << s.pop() << endl;

}

Но вот есть вопрос как бы записать первое значение s в стек, Stack s(10) - вот из этой строчки?
Пробовала писать Head -> value = _value в конструкторе, выводит ошибку Необработанное исключение в "0x013814fc" в "stack22.exe": 0xC0000005: Нарушение прав доступа при записи "0xccccccd0".

[Son Of Pain]

Осталось добавить в конструктор строчку

Head=this;

и оно заработает, в принципе.

[kei91]

Спасибо огромное!!! =)