Stack & data-structure

Question

I am new to data structure and algorithm and i want to ask why it is necessary to implement a stack using array via structure data type we can directly make the global pop & push functions, global array & top variable then why we create a structure and inside that structure we declare a top variable and a array pointer.

I am trying to understand what are the benefits or the flaws in both the method of implementing the stack using the array one in which we declare the array inside the structure and in another one we directly make a global array.

Can you provide some code showing the two examples? It's much better to see the code than see a description of the code. — Support Ukraine, Aug 21 '23 at 13:01
If you use a global array and global functions that operate on it then your program can only have one stack. — Verpous, Aug 21 '23 at 13:03
@Verpous If you need N stacks in your program, you could make N arrays and N top-variables. But that will like become a mess as the program grows. — Support Ukraine, Aug 21 '23 at 13:12
@SupportUkraine sure, but an array is nearly always the best underlying representation for a stack. — Cubic, Aug 21 '23 at 13:15
@Cubic Agree. But it's still worth to know that it's not a law of nature. — Support Ukraine, Aug 21 '23 at 13:19
It's not entirely clear to me what you are asking, but chances are, the basic answer is that what you describe is *not* necessary. If you want to know about the characteristics of a particular approach to implementing a stack, then you would be best served by providing example code for us to talk about. — John Bollinger, Aug 21 '23 at 14:00
This all boils down to *"why not use global variables for everything we need?"* It is not specific to stacks, but to any data structure. See also [What are the pros and cons in use of global variables?](https://stackoverflow.com/q/484635/5459839) — trincot, Aug 21 '23 at 14:50

Support Ukraine · Accepted Answer · 2023-08-23T05:33:38.403

A complete answer will require a long, long, long answer. And it could turn into opinion based examples (which is unpopular/forbidden on SO). But below I have written a few of the many things that you new to consider.

You are mixing two unrelated things together. Using a structure (a struct) doesn't prevent you from making the stack a global variable. Not using a structure doesn't prevent you from using local stack.

int stack_data[N];     // Global stack
int stack_size = 0;    // without a struct

struct stack {
    int data[N];
    int size;
};
struct stack stack = {0};   // Global stack using struct

void foo(void) {
    int foo_stack_data[N];     // Local stack
    int foo_stack_index = 0;   // without a struct
    ...
    ...
}

void bar(void) {
    struct stack bar_stack = {0};  // Local stack using struct
    ...
    ...
}

In other words - whether the stack is global or local hasn't anything to do with the use of struct.

There are several reasons for using struct. Gathering closely related variables like "stack data" and "stack size" in a struct will in many cases make you code easier to read and maintain.

As an example assume your program needs 100 stacks. Without the struct you would need 2 * 100 = 200 lines of code. With a struct stack you'll only need 100 lines (plus 4 for the definition). And this would just get worse as the number of variables related to the data structure increased.

And if you need a dynamic allocated stack a single call of malloc would do using struct while you would need 2 calls of malloc without struct.

Global variables.... hmmm, there are situations where a (few) global variables makes sense. But extensive use of global variables (nearly) always leads to a mess. A good rule is to avoid globals unless you have a very strong argument.

Look at this:

int stack_data[N];     // Global stack
int stack_size = 0;    // without a struct

void push(int value) {
    // error check omitted
    stack_data[stack_size] = value;
    stack_size = stack_size + 1;
}

void bar(void) {
    push(42);
}

Well... it will work. But... what if I need two stacks or 8 stacks. Should I then write 8 version of the push function? Doesn't sound like fun to me...

So I do:

void push(int value, int* d, int* sz) {
    // error check omitted
    d[*sz] = value;
    *sz = *sz + 1;
}

void bar(void) {
    push(42, stack_data, &stack_size);
    push(65, another_stack_data, &another_stack_size);
}

Passing the stack related variable allows me to have multiple stacks.

But I had to pass both the data and the size. Two arguments. And what if I need 5 variables to describe my data structure.... then I would have to pass 5 arguments. Besides all the typing, it would/could also hurt performance.

By using the struct method I could do with a single argument, i.e. a pointer to a struct variable:

void push(int value, struct stack *s) {
    // error check omitted
    s->data[s->size] = value;
    s->size = s->size + 1;
}

void bar(void) {
    struct stack stack1 = {0};
    push(42, &stack1);
    struct stack stack2 = {0};
    push(65, &stack2);
    ...
}

Stack & data-structure

1 Answers1