I am trying to sort a stack of elements but the function overflow and I don't know why it do that.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define type int //type of element in the stack
#define max 100
typedef struct {
int top;
type array[max];
} stack;
stack *initialize () {
stack *s = malloc (sizeof (stack));
s->top = 0;
return s;
}
void push (stack *s, type x) {
s->array[s->top ] = x;
}
type pop (stack *s) {
return s->array[--s->top];
}
type isfull (stack *s) {
return s->top >= max;
}
type isempty (stack *s) {
return !s->top;
}
type peek (stack *s) {
return s->array[s->top - 1];
}
void sortstack (stack *s) { //sorting the stack
stack *temp = initialize();
int x, flag;
do {
flag = 0;
while (!isempty (s)) {
x = pop (s);
if (x > peek (s)) {
push (temp, pop (s));
push (s, x);
flag = 1;
} else push (temp, x);
}
while (!isempty (temp)) push (s, pop (temp));
} while (flag);
}
int main() {
stack *s = initialize();
push (s, 2);
push (s, 4);
push (s, 4);
push (s, 7);
push (s, 9);
push (s, 18);
sortstack (s);
while (!isempty (s)) printf ("%d ", pop (s));
return 0;
}
CodePudding user response:
There are multiple problems in the code:
in
if (x > peek (s))
you should test if the stacks
is not empty to avoid undefined behavior accessings->array[-1]
.x
should be defined with typetype
.you should free the temporary stack
temp
before leaving the functionsortstack
.you should use
typedef int type;
instead of#define type int
it is idiomatic to define macros such as
max
in uppercase, using a more descriptive name is recommended.adding
assert
statements helps catch unexpected error conditions.
Here is a modified version:
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int type; //type of element in the stack
#define STACKSIZE 100
typedef struct {
int top;
type array[STACKSIZE];
} stack;
stack *initialize(void) {
stack *s = malloc(sizeof(stack));
assert(s != NULL);
s->top = 0;
return s;
}
void discard(stack *s) {
free(s);
}
void push(stack *s, type x) {
assert(s->top < STACKSIZE);
s->array[s->top ] = x;
}
type pop(stack *s) {
assert(s->top > 0);
return s->array[--s->top];
}
type isfull(stack *s) {
return s->top >= max;
}
type isempty(stack *s) {
return !s->top;
}
type peek(stack *s) {
assert(s->top > 0);
return s->array[s->top - 1];
}
void sortstack(stack *s) { //sorting the stack
stack *temp = initialize();
int flag;
do {
flag = 0;
while (!isempty(s)) {
type x = pop(s);
if (!isempty(s) && x > peek(s)) {
push(temp, pop(s));
push(s, x);
flag = 1;
} else {
push(temp, x);
}
}
while (!isempty(temp)) {
push(s, pop(temp));
}
} while (flag);
discard(temp);
}
int main() {
stack *s = initialize();
push(s, 2);
push(s, 4);
push(s, 4);
push(s, 7);
push(s, 9);
push(s, 18);
sortstack(s);
while (!isempty(s)) {
printf("%d ", pop(s));
}
printf("\n");
discard(s);
return 0;
}