Push() and Pop() Methods for a Stack Class

[aardeehar]

Hello!

Hi everyone! I am currently attempting to code a stack class for C++.

The stack has two basic functions: push(double val) and pop().
Here is my code so far, please note that this is an assignment (so no outright answers please, I'm trying to learn), and also, that the Node struct must be used.
Here is the header file:

  class Stack {

private:

	struct Node {

		double data;
		Node* p;

	};

	int top = -1;
	int n = 5;

public:
	Node n1;
	Node n2; 

	Stack() {
		n1.p = nullptr; 
		n1.data = 0.0; 
	

	}
	
	void push(double value) {
		
		n1.data = value; 
		n1.p++; //move pointer forward (back to 'top')

		}
		
	
	double pop() {
		double temp = n1.data;
		n1.p--; //move back

		return temp;
		
	}
	
	
};

Here is the main method:

Stack stack;
	stack.push(11.8);
	stack.push(4.9);
	std::cout << stack.pop() << '\n'; // should print "4.9"
	stack.push(3.4);
	std::cout << stack.pop() << '\n'; // should print "3.4"
	std::cout << stack.pop() << '\n'; // should print "11.8"
	std::cout << stack.pop() << '\n';

Any and all help is appreciated, I'm beyond confused at the moment.

[highwayman]

lists are not in blocks, so why do you do this? (n1.p--)

Edit: also keep in mind what you currently have is basically a forward list, so n1.p-- wouldn’t even be able to be done the correct way.

[aardeehar]

I'm sorry, I'm not quite understanding this. What does "not in blocks" mean?

I was attempting to move the pointer, p, back one address. So, from pointing at 1004 (say, data 3.1) to 1000 (data 10.0).

[deleted account xyzzy]

A stack is a Last In-First Out (LIFO) container. The only position a stack cares about is the end of the stack. The end of the container is also known as the top of the stack.

std::stack is an adapter for a sequence container that restricts what member functions can be performed on the container.

push() ADDS an element to the end of the container, pop() REMOVES the last element at the end of the container. There is no pointer math magic involved.

You should try to replicate that behavior in your Stack class.

@highwayman, std::stack can adapt a std::vector, std::deque or std::list, or the implementation can create its own method to fulfilling the requirements of a stack. The OP using a list is not wrong as an implementation starting point.

The actual implementation has potential problems.

[aardeehar]

I realize that an array would be better, however, in this scenario I must use the data as outlined.

I understand what push and pop do, as an idea. I realize that I really only need something pointing to - or indicating - the "top" of the stack, as it were. However, I'm having trouble working it out. If I have my pointer, Node *p, which is a pointer pointing to a Node, p, then how do I update it to point at the top node of the stack? By default it points to nullptr...

I think I'm missing something here because I've been working on this program for hours with little success.

[deleted account xyzzy]

The only "pointer" needed is for the location of the end of the container. The "top" of the stack.

One way to implement a custom stack class, using a C style array as the class member container:

https://www.includehelp.com/code-snippets/stack-implementation-using-cpp-class-with-push-pop-traverse.aspx

std::stack likely uses a dynamic sized container, so "top" is updated as data is pushed and popped.

[highwayman]

I apologize, I was unclear. I did not mean to say that stack can’t be implemented using a list, I was just saying that since a list isn’t necessarily going to place all it’s objects next to each other in memory, so decrementing a pointer will not necessarily point to the previous object in the list.

[zapshe]

If you used a vector, all of the functions you want are built-in and can easily simulate a stack. If you want to do it without an array, you have two choice:

Either make a variable ahead of time (in the code) as many times as you're going to push_back, or make a dynamic array by using "new". If you do it right, you won't ever use "[]" and you can lie to yourself that it's not an array.

[lastchance]

@aardeehar,
A stack needs some sort of container or data structure to hold its values. It doesn't matter whether that is a fixed-size array, vector or linked-list. At the moment it looks as if you were trying to implement a linked list, but if that is so then the underlying list is wrong: you have no ++ or -- operators defined and nowhere do you create new nodes to add to the list. It would probably also have to be doubly-linked (forward and back) to use as a stack.

Unless specifically told otherwise, why don't you use a vector to implement the stack? Or, failing that, a fixed-size array with maximum-size check?

[aardeehar]

Unfortunately the task was to used a LL. I understand a linked list, and the idea of nodes - each node points to the next node, and each node contains one data value (a double, in this case). In theory, there should be one node that always points to the top of the stack - this is where nodes get pushed on, and popped off.

I did the same task using a fixed size array, and was able to get it working relatively easily. In an array this is relatively straightforward. Top defaults to -1. Every time you push, check that you have room, increment top, and add the value. Pop is also similar. Check that your array isn't empty, and if not, return the top and decrement it.

I have used LL before in Java but my issue appears to be translating this to C++ code. To clarify, you're saying the issue is with the Node funct itself?

[lastchance]

Your main problem is that you simply don't create any nodes (other than n1 - which should really be a head pointer, I assume). So there's nothing to link to. If you have a pop() function then, unless you want to scan through the entire list every time, you will need a doubly-linked list with tail pointer and each node having a pointer to a previous, as well as next node.

You will need new to allocate a new node and delete to free its memory. The rest of your operations will be setting or breaking next and prev pointers for nodes, and redirecting the tail and head pointers when necessary.

[jonnin]

LL makes a great stack, but you need to pay attention to the logic.
push should create a new node, then set next to head, then set head to the new one.
pop should set tmp to head, head to head -> next, save tmp.value to return, delete tmp
you never need to iterate through the list, its always interacting with the top node, see?

[lastchance]

Ah, you're right, @Jonnin. You do all the work around the head pointer, so one-way list would be fine.

[lastchance]

@aardeehar,
Here's one possible framework. You can fill in the blanks. Do the pointer rearrangement to delete the head node and return its value.

#include <iostream>
using namespace std;

class Stack
{
   struct Node
   {
      double data;
      Node *p;
   };

public:
   Node *head = nullptr;

   void push( double value )
   {
      head = new Node{ value, head };      // create a new node on the heap and point head at it
   }

   double pop()
   {
      if ( !head )                         // nothing to pop(); act accordingly
      {
         cout << "Attempt to pop() an empty stack\n";
         return 0;
      }
      else
      {
         // **** FILL IN THE BLANKS

         // Store the data in the current head node
         // Set a temporary pointer to the current head node
         // Point head at the following node
         // Delete the heap storage pointed to by the temporary pointer
         // return the stored data

         // **** END OF FILL IN THE BLANKS
      }
   }
};


int main()
{
   Stack stack;
   stack.push( 11.8 );
   stack.push( 4.9 );
   cout << stack.pop() << '\n'; // should print "4.9"
   stack.push(3.4);
   cout << stack.pop() << '\n'; // should print "3.4"
   cout << stack.pop() << '\n'; // should print "11.8"
   cout << stack.pop() << '\n';
}

4.9
3.4
11.8
Attempt to pop() an empty stack
0