Stacks without class - URGENT help needed

[connor grimes]

Hello, i put up a post a while ago about stacks, and im yet still to grasp the concept and after googling for hours on end cannot seem to find an answer, so i thought i'd ask here ans see what comes up.

I've been assigned to create a stack or a queue for a university assignment but every tutorial i go across showing me how are using classes which im not allowed to do, has anyone got a simple approach to making a stack or a queue without all the classes.

Thanks in advance

[booradley60]

Use an array.

It makes it easier if you have an established upper bound on the number of items your stack or queue can hold. You can declare the array size to be the upper bound.

Once you have the array, the rest of the program is managing the indicies into the array every time you do a [push | enqueue], [pop | dequeue], and empty.

With a stack, it should be easy. The base index is 0, the top index points to whatever index holds the top of the stack. When you push, you increment the top index and write the new item to that index. When you pop, you grab the element at the top index and decrement the top index. You must also do some error checking so you don't overflow/underflow the stack. To check for empty, you compare the base index to the top index to determine if there is anything in your stack.

For a queue, it is a little more difficult, since your base pointer moves up on a dequeue, your "top" pointer moves up on an enqueue. You have to make your indexes wrap around so they don't eventually run out of bounds.

There are lots of caveats and gotchas when trying to do these by hand, so try to get some code together and post an update this thread when you run into a snag. Hope this helps.

[IWishIKnew]

std::stack http://en.cppreference.com/w/cpp/container/stack

std::queue http://en.cppreference.com/w/cpp/container/queue

At least, that is what you use if you're using the standard template library.

-----------------------------------------------------------------------------

@booradley60
Absolutely not. I would not use dynamic memory like that. If you want to use an array, use a vector. You can set limits by using common sense. Vector emplements a dynamic array that over-allocates to avoid reallocs, so if you want to be memory efficient, you can use shrink_to_fit() to free the extra memory that was allocated.

A queue is easy: push to the front, reference and delete at the back. If you are using a dynamic array, then you will have to create these functions manually.

-----------------------------------------------------------------------------

if you use a dynamic array, make specialized templates for objects like strings, and any other object that allocates its own memory. Otherwise, there will be a huge risk of memory leak.

[keskiverto]

A class/struct is about encapsulation. They define some variables and procedures that operate on those variables as one unit that can be used as a (more complex) variable.

You have a memory block (variable) that contains what has been stored in "stack".
You have a variable that shows how many items are in the stack.
You have a method that adds a value into the stack.
You have a method that removes a value from the stack.
Both methods modify both variables.
You have a method that shows whether the stack is empty.

You have to define the functions and declare the variables whether you wrap them as a class or not.


You have been given a university-level assignment, but have not been explained basics of a programming language?

[MiiNiPaa]

Once you have the array, the rest of the program is managing the indicies into the array every time you do a [push | enqueue], [pop | dequeue], and empty.

For integral types I prefer to store size of array/stack in the stack itself at index 0. Kinda like Pascal strings.

[booradley60]

@IWishIKnew
I interpreted this as a beginner question, since the OP stated he's not allowed to use classes. Therefore, I avoided giving a response saying 'use the STL', 'use Templates', 'be resource conscious', etc. I think this question belongs in the beginners forum, and once OP learns more then your suggestions will be more helpful to him.

It sounds like a Data Structures assignment. The whole point of the exercise is to do these things by hand to figure out these caveats and understand exactly how to manage storage of elements.

[IWishIKnew]

@booradley
well, it's in general C++, so I gave a general answer.

[connor grimes]

IWishIKnew/Booradley60 - thanks for your help! yes its a data structure assignment and even in the general c++ thread i've gained more insight then anywhere else. unfortunately my Microsoft visual studio isn't working at the moment so i will post the code i have when i gain access again.

[connor grimes]

hello guys, after trying to make a stack, i have this, any moire advice or where i can build it from here? im trying also to include test plans and debugging, thanks in advance!

#include<iostream>
#include<stdlib.h>
using namespace std;

int stack[5];
int top;

void push (int x)
{
	if (top>5)
	{
		cout<<"your stack has overflowed or is full, returning to a past state"<<endl;
		return;
	}
	stack[++top]=x;
cout<<"inserted2"<<x<<endl;
}

void pop()
{
	if(top<0)
	{
		cout<<"stack is underflowed,restoring last state"<<endl;
	return;
	}
	cout<<"deleted"<<stack[top--];
}

void display()
{
	if (top<0)
	{
		cout<<"The stack is empty"<<endl;
		return;
	}
	for ( int i = top;i>=0;i--)
		cout<<stack[i]<< " ";
}



int main;
{
	int choice;
		int ele;
		stack stk;
		while(1)

	{
		cout<< "Implementation of a stack"<<endl;
	cout<<" The following programme represents a stack, which follows the L.I.f.O system\n"endl;
	cout<< "L.I.F.O means Last in, First Out.\n For example, if you stack dinner plates\nthe last one to be stacked ontop of the stack, will be the first to be used"endl;
	cout<<" From the stack you can: Push - adds to the stack, Pop - Removes from the stack"<<endl;
	cout<<"You can also find out if the stack is full or empty, and have the stack be printed for a visual display"<<endl;
	cout<<"1.push, 2.pop, 3.display, 4. exit"<<endl;
	cout<<" Please enter your choice"<<endl;
	cin>>choice;

	switch(choice)
	{

	case 1: cout<<"eneter the number of elements you wish to have, remember the stack can only hold five elements"<<endl;
		cin>>ele;
		stk.push (ele);
		break;

	case 2: cout<<"you have popped an element out!"<<endl;
		stk.pop();
		break;

	case 3: stk.display()

	case 4: exit(0)
	}
		}
		return (0);
}

[Smac89]

Since this is an array based stack, you should make it resizeable. i.e. instead of creating the stack on the stack (...), you should create it on the heap. In simpler terms I mean you should have a dynamic array. Dynamic arrays allow you to change the size of the array at runtime, where as stack allocated arrays do not allow that option.

Now since memory allocation is expensive, you don't want the re-sizing of the array to be a bottleneck for your program. So the general method of implementing such array based approach is to double the size of the array when it is full or halving the size of the array when it is a quarter full

[cire]

It looks like you have the basics down. One thing your code doesn't get right, though, is what top represents. top is the index of the first free slot in the array, so stack[top] is not, at any given point, a valid element of the stack.

const int stack_size = 5 ;
int stack[stack_size];
int top;

void push (int x)
{
    if ( top == stack_size )
    {
        cout << "Unsuccessful push (" << x << ")\n" ;
    }
    else
    {
        // What you want to do:
        stack[top] = x ;
        ++top ;
        // which is equivalent to: stack[top++] = x ;
        // what you actually did: stack[++top] = x ; 

        cout << "Successful push (" << x << ")\n";
    }
}

Similar adjustments need to be made to pop and display.

edit: You also seem to be confused in main. stack is a variable, not a type. As it seems you are forbidden to use classes, it is odd that you're attempting to use stack as a type in main.

int main()
{
    while(1)
    {
         // cout << "instructions" ;

        int choice ;
        cout<<" Please enter your choice\n";
        cin>>choice;

	switch(choice)
	{
        case 1:
            { 
                 int num ;
                 cout << "Enter a number\n" ;
                 cin >> num ;
                 push(num) ;
                 break ;
            }

        case 2: cout<<"you have popped an element out!"<<endl;
                pop();
                break;

        case 3: display();
                break ;

        case 4: exit(0);
        }
    }
}

[connor grimes]

Smac89 thanks that was helpful!

and cire! thank you so much, you have been a wonder, yeah theres a lot of confusion on this assignment but you've helped me alot! i'll post more code soon to see if i got it right!

[connor grimes]

thanks for the help! butr can you help with my pop and display functions??

i tried to follow what you do with the popbut it didnt work

heres my code

void pop
{
    if ( top == < 0 )
    {
        cout<<"stack is underflowed"<<endl;
    }
    else
    {
        stack[top] = x;
        --top;
        cout<< " good pop" <<endl;
    }

}
void display()
{
    if (top<0)
    {
        cout<<"stack is empty"<<endl;
    }
    else
    {
        for (int i = top; i>0;i--)
        cout<<stack[i]<<" "<<endl;
    }
}

i just cant see where im going wrong, these error codes keep coming up

E:\uni\Nigel - Maths_Programming\Programming\Lab 6 - Data\data structures\main.cpp|23|error: variable or field 'pop' declared void|
E:\uni\Nigel - Maths_Programming\Programming\Lab 6 - Data\data structures\main.cpp|23|warning: extended initializer lists only available with -std=c++0x or -std=gnu++0x|
E:\uni\Nigel - Maths_Programming\Programming\Lab 6 - Data\data structures\main.cpp|25|error: expected primary-expression before 'if'|
E:\uni\Nigel - Maths_Programming\Programming\Lab 6 - Data\data structures\main.cpp|25|error: expected '}' before 'if'|
E:\uni\Nigel - Maths_Programming\Programming\Lab 6 - Data\data structures\main.cpp|29|error: expected unqualified-id before 'else'|
E:\uni\Nigel - Maths_Programming\Programming\Lab 6 - Data\data structures\main.cpp|36|error: expected declaration before '}' token|
||=== Build finished: 5 errors, 1 warnings ===|

[Jaybob66]

void pop -->> void pop()

if ( top == < 0 ) -->> if ( top =< 0 )

[cire]

void pop()
{
    if (top > 0)
    {
        cout << "pop is successful\n";
        --top;
    }
    else
        cout << "pop is unsuccessful (underflow)\n";
}

Again, remember that top is the index of the first free element in the stack. stack[top] is not a valid element.

[connor grimes]

thanks cire, its hard getting my head around programming, always found it difficult, thank you,

[connor grimes]

whats a function definition?

i.e, i used the pop you provided, but every time i click build, its saying { is not allowed before the function definition, and apart from this and my display im almost done D:!

void pop()
{
    if ( top > 0 )
    {
        cout<<"pop is successful"<<endl;
        --top;
    }
    else
    {
       cout<< "pop is unsuccessful, stack is underflowed"<<endl;

}

E:\uni\Nigel - Maths_Programming\Programming\Lab 6 - Data\data structures\main.cpp||In function 'void push(int)':|
E:\uni\Nigel - Maths_Programming\Programming\Lab 6 - Data\data structures\main.cpp|24|error: a function-definition is not allowed here before '{' token|
E:\uni\Nigel - Maths_Programming\Programming\Lab 6 - Data\data structures\main.cpp|79|error: expected '}' at end of input|
||=== Build finished: 2 errors, 0 warnings ===|
E:\uni\Nigel - Maths_Programming\Programming\Lab 6 - Data\data structures\main.cpp||In function 'void push(int)':|
E:\uni\Nigel - Maths_Programming\Programming\Lab 6 - Data\data structures\main.cpp|24|error: a function-definition is not allowed here before '{' token|
E:\uni\Nigel - Maths_Programming\Programming\Lab 6 - Data\data structures\main.cpp|79|error: expected '}' at end of input|
||=== Build finished: 2 errors, 0 warnings ===|

[TwilightSpectre]

You haven't closed the ending brace after the else clause. Add a '}' on line 11.

[connor grimes]

thanks for the advice, it was like this for the void push as well, its now up and running! all i have to do is sort out the max number of elements as it lets me push continuously, and sort out the display, any advice guys???

thanks in advance if you can help me finish it off, and thanks to everyone thats help me complete it :)

[connor grimes]

this is getting ridiculous now, if anyone can help it would be greatly appriciated, i have written out the code, an d it worked fine, came back a day later and two { are mssing and i put them in everywhere yet apprently my code now doesnt work, can anyone see why? i'll post my code below.

thanks

#include<iostream>
#include<stdlib.h>
using namespace std;

const int stackSize = 5;
int stack[stackSize];
int top;

void push (int x)
{
    if ( top == stackSize )
    {
        cout << "Unsuccessful push (" << x << ")\n";
    }
    else
    {
        stack[top] = x ;
        ++top ;
        cout << "Successful push (" << x << ")\n";
}

void pop()
{
    if ( top > 0 )
    {
        cout<<"pop is successful"<<endl;
        --top;
        }
    else
    {
       cout<< "pop is unsuccessful, stack is underflowed"<<endl;
}
}


void display()
{
    if (top<0)
    {
        cout<<"stack is empty"<<endl;
    }
    else
    {
        for (int i = top; i>0;i--)
        cout<<stack[i]<<" "<<endl;
    }
}



int main()
{
    while(1)
    {
         int choice ;
         cout<<" Welcome to the stack implemention"<<endl;
         cout<< "Please look at the following options"<<endl;
         cout<<" key in the corresponding number to sleect that option"<<endl;
        cout<<" 1. PUSH 2. POP 3. DISPLAY 4. Exit\n"<<endl;

        cout<<" Please enter your choice\n"<<endl;
        cin>>choice;

	switch(choice)
	{
        case 1:
            {
                 int num ;
                 cout << "Enter a number\n" ;
                 cin >> num ;
                 push(num) ;
                 break ;
            }

        case 2: cout<<"you have popped an element out!"<<endl;
                pop();
                break;

        case 3: display();
                break ;

        case 4: break;


        }
    }

}