# Stack implementation using an array

I am trying a stack implementation using an array. I want to know if this approach is OK or if there is a logical problem. This program is working fine.

#include <stdio.h>
#define MAXSIZE 5

struct stack            /* Structure definition for stack */
{
int stk[MAXSIZE];
int top;
} s;

void push ();
void pop();
void display ();
void search();

int main(){

int element, choice;

s.top = -1;

clrscr();

while (1)
{
printf ("------------------------------------------\n");
printf ("1. PUSH\n");
printf ("2. POP\n");
printf ("3. DISPLAY\n");
printf ("4. SEARCH\n");
printf ("5. EXIT\n");
printf ("------------------------------------------\n");

scanf   ("%d", &choice);

switch (choice)
{
case 1: push();
break;
case 2: pop();
break;
case 3: display();
break;
case 4: search();
break;
case 5: return;
}

}

}

/*Function to add an element to the stack*/
void push() {
int num;

if (s.top == (MAXSIZE - 1))
{
printf ("Error: Overflow\n");
}
else
{
printf ("Enter the element to be pushed\n");
scanf ("%d", &num);
s.top = s.top + 1;
s.stk[s.top] = num;
}
}

/*Function to delete an element from the stack*/
void pop ()
{
int num;
if (s.top == - 1)
{
printf ("Error: Stack Empty\n");
}
else
{
num = s.stk[s.top];
printf ("poped element is = %d\n", num);
s.top = s.top - 1;
}
}

/*Function to display the status of the stack*/
void display()
{
int i;
if (s.top == -1)
{
printf ("Error: Stack Empty\n");
}
else
{
printf ("\nItems in Stack\n");
for (i = s.top; i >= 0; i--)
{
printf ("%d\n", s.stk[i]);
}
}
printf ("\n");
}

void search(){

int i;
int num;
int counter=0;
if (s.top == -1)
{
printf ("Error: Stack Empty\n");
}
else
{
printf ("Enter the element to be searched\n");
scanf ("%d", &num);

for (i = s.top; i >= 0; i--)
{
if(num==s.stk[i]) {
counter++;
break;
}
}

if(counter>0){
printf ("Element %d found in stack\n", num);
}
else {
}
}
printf ("\n");

}


# sscanf is not safe

It's not part of your stack but part of your driver code, but scanf() is not a good function to use. There are many reasons for this, but the basic problem in this case is that if the user enters a letter rather than a digit for input in push() for example, the program will loop forever.

Better, in this case, would be to use something like getchar().

# separate stack operations from input/output

Having a function like push() only do one thing (pushing an item to the stack) is generally better design because it makes it easier to re-use your code. In this code, push() cannot be easily re-used because it is tied directly to user I/O. Better would be to cleanly separate all stack operations from the I/O to better foster re-use.

# operations should operate on passed parameters

In this code, there can only be one stack because it's globally defined and used by all stack operation functions. A better scheme would be to pass the address of the stack structure to each function to make it more flexible and more general.

Additionally, a function like push() should also require an argument that speccifies what is to be pushed onto the stack, and a function like pop() should return either a copy of or a pointer to the data item that was popped from the stack.

# use C idioms to make the code shorter and easier to read

Writing code such as

s.top = s.top + 1;
s.stk[s.top] = num;


is not incorrect, but is not idiomatic C. The C way of writing that would be

s.stk[++s.top] = num;


Writing code in this way will make it easier for others to understand you, in the same way that speaking, say, idiomatic Italian will make it easier for native Italian speakers to understand you.

# avoid non-portable code

The clrscr() call is not in <stdio.h> and is not portable. I had to comment out that line to get the code to compile and run. Ideally, you'd avoid all non-portable code. If you can't avoid that, however, you should state what dependencies the code has and also include the header files that clearly indicate those dependencies.

It's good that you avoided using "magic numbers" and instead you wisely chose to define MAXSIZE to indicate the size of your stack. However, it would be useful to have a comment indicating what it's for, and also to maybe rename it to something a little more descriptive, such as MAXSTACKSIZE.

# avoid single-letter variable names

While i or j might be perfectly fine variable names for looping indexes, naming your stack s is not very user-friendly. We are long beyond the days that each line of code had to fit on an 80-character punch card!

I hope these items inspire you to write more code, and to strive to continuously improve the quality of the code that you write.

• s.stk[s.top++] = num; and s.top += 1; s.stk[s.top] = num; are not the same thing, though. I take it you meant s.stk[++s.top] = num; – Elias Van Ootegem Apr 10 '14 at 8:41
• @EliasVanOotegem I proposed that edit already. It's in the queue. – Brian Gordon Apr 10 '14 at 8:45
• @BrianGordon: I've noticed, and I approved the edit, probably while you were commenting :) – Elias Van Ootegem Apr 10 '14 at 8:52

Much can be improved here, but I'll mention several things:

• Everything within main() should be indented, just as you've already done with the other functions. Otherwise, it's hard to tell where it starts and what's in it.

Maintain consistency throughout your program. These little things do matter.

• You could eliminate the function prototypes by declaring main() lastly. In this way, main() will already be aware of the other functions when calling them.

• Your stack would be more usable if it were dynamic as opposed to static. If it's dynamic, you can keep pushing elements without worrying about reaching a limit. But if you stay with static, you'll have to check for a full stack when pushing, otherwise you'll run into problems.

• In C, use a typedef with struct so that you don't have to type struct elsewhere.

• Use puts() instead of printf() when outputting an unformatted line with a newline. This would apply to your menu item output.

• I would refrain from having output in push() and pop(). They should only perform their primary purposes, while the testing output should just be done in the calling code.

display() really shouldn't display anything if the stack is empty. Just return early if it is.

• push() is doing too much; it's asking for a value and pushing the value. It should just be doing the latter after receiving a value as an argument from the calling code.

• search() is also doing too much; it's asking for a value and searching for it.

It should also not display any messages (again, this all goes in the calling code) and it should return a bool. If the stack is empty (check for this first), simply return false.

There is no logical issue to what you are doing, as indeed that is a stack and does what a stack needs to do.

One thing you may want to consider though is that a fixed size array is typically not the manner in which stacks are implemented. For as to why, consider the case where your stack is full and you want to push more things too it. A costly solution would by to allocate a new array of greater size, and copy all values over. Moreover, what if all elements of the stack are popped off after allocating a huge space for it? The array is still allocated in full in memory.

To avoid these problem, a Linked List is generally used instead. It allows for removals and insertions from the front and back in constant time, and is only as large as necessary. Link Lists also make a good project in general when learning C.

• Using an array and resizing it as necessarily is usually faster in practice, even though it sounds worse. Linked lists require more memory allocations, which are slow, and cause the cache to perform worse (because the memory isn't close together). – Brendan Long Apr 10 '14 at 4:19
• True, not being contiguous in memory is a significant blow against linked lists as it generally yields to poor locality of reference (and hence cache missing), but for the purposes of pedagogy I am inclined towards them. They allow novice programmers to appreciate the notion (at least conceptually) of Big-O and how data may be given structure in code, which is later useful in understanding more complex structures such as trees. This is all a matter of preference admittedly, but it is worth explicating. – Juser1167589 Apr 10 '14 at 12:08