Implementacja stosu na bazie tablicy, struktura

Mam takie zadanie. Napisz program, w którym zaimplementujesz stos na bazie tablicy. Liczbę elementów tablicy dobierz samodzielnie. Przetestuj tę implementację. Twój program powinien wykrywać sytuacje, kiedy stos jest pusty i kiedy jest pełny.

I mam taki kod:

#include <stdlib.h>
#include <stdio.h>
#define STACK_SIZE 4


    int stack_array[STACK_SIZE];
    int top = -1;


void push(int data){
    if(top == STACK_SIZE - 1){
        printf("Przeladowanie!");
        return;
    }
    top=top+1;
    stack_array[top] = data;
}

int pop(){
    int value;
    if(top == -1){
        printf("Stos jest pusty");
        exit(1);
    }
    value = stack_array[top];
    top = top - 1;
    return value;
}

int peek(){
    if(top == -1){
        printf("Stos jest pusty");
        exit(1);
    }
        return stack_array[top];
}
    
void print(){
    if(top == -1){
        printf("Stos jest pusty\n");
        return;
    }
    for(int i = top; i >= 0; i--){
        printf("%d ", stack_array[i]);
    }
    printf("\n");
}

int main(){
    
    int choice, data;

    while(1){
        printf("\n1. push\n"
               "2. pop\n"
               "3. wypisz wierzcholek stosu\n"
               "4. wypisz wszytskie elementy stosu\n"
               "5. koniec\n"
               "Wybierz opcje: ");
        scanf("%d", &choice);
    
    
        switch(choice){
            case 1:
                printf("Wrzuc element na stos: ");
                scanf("%d", &data);
                push(data);
                break;
                
            case 2:
                data = pop();
                printf("Usuniety elemet ze stosu to: %d\n", data);
                break;
            case 3:
                printf("na szczycie stosu jest %d", peek());
                break;
            case 4:
                print();
                break;
            case 5:
                exit(1);
            default:
                printf("Zly wybor");
        }
    }
    
    return 0;
}

I teraz chce zamiast zmiennych globalnych użyć struktury:

struct stack{
  int stack_array[STACK_SIZE];
  int top;
}

Tylko nie wiem teraz jak ugryźć temat, chyba trzeba coś rzeźbić ze wskaźnikami...

I też prosił bym o ewentualne uwagi co do kodu :)

Tak, trzeba ze wskaznikami. Poza tym:

• wywal to exit. Ogolnie na razie zaponij o intnieniu tej funkcji (przy okazji o sleep tez zapomnij). Moze kiedys przyjdzie czas zeby sobie przypomniec, ale mozliwe ze przez lata pracy nie bedzie to potrzebne.
• z reguly w funkcji cos moze sie nie udac wiec jakos trzeba zwrocic blad. A to oznacza ze, szczegolnie w publicznym API, funkcja raczej bedzie zwracala informacje o bledzie a nie wynik, a wynik bedzie zwracany przez argument (choc oczywiscie mozna to odwrocic) np: *result = data;
• kod powinien byc spojny. Ty czasami wolasz exit czasami nie. Czasami jest \n w printf, czasami nie.
• funkcja oprocz kodu bledu moze tez zwracac komunikat bledu (trzeba wtedy poprawnie obsluzyc pamiec dla tego komunikatu), ale nie powinna go sama wyswietlac

Przyklald z uzyciem wskaznika:

int push(Stack* stack, int data) {
  if (stack == NULL) {
    return RESULT_INVALID_ARGUMENT;
  }
  int newTop = stack->top + 1;
  if (newTop == STACK_SIZE) {
    return RESULT_STACK_OVERFLOW;
  }
  stack->array[newTop] = data;
  stack->top = newTop;
  return RESULT_SUCCESS;
}

Fakt ze zamienilem kolejnosc przypisania i zmiany top nie ma tu znaczenia, ale czesto bywa mozliwe ze podczas modyfikacji cos sie moze nie udac wiec nie mozna zmienic rozmiaru wczesniej.
Mozna tez zaszalec i int stack_array[STACK_SIZE]; zamienic na int* stack_array; - wtedy latwo mozesz tworzyc stos z rozymi rozmiarami (pamietajac o free i obsludze bledow w malloc)

Prosty szablon stosu z użyciem struktury, trzeba popracować nad errorami, czyszczeniem pamięci, testami. Brakowało Ci, isEmpty, kluczowej metody dla stosu.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>


int CAPACITY = 100;


struct Stack 
{
	int top;
	int capacity;
	int* array;
};

struct Stack* createStack()
{
	struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
	stack->capacity = CAPACITY;
	stack->top = -1;
	stack->array = (int*)malloc(stack->capacity * sizeof(int));
	return stack;
}

int isFull(struct Stack* stack)
{
	return stack->top == stack->capacity - 1;
}

int isEmpty(struct Stack* stack)
{
	return stack->top == -1;
}

void push(struct Stack* stack, int item)
{
	if (isFull(stack))
		return;
	stack->array[++stack->top] = item;
}

int pop(struct Stack* stack)
{
	if (isEmpty(stack))
    {
        fprintf(stderr, "%s", "Stack: popping from empty stack!\n");
		abort();
    }
	return stack->array[stack->top--];
}

int peek(struct Stack* stack)
{
	if (isEmpty(stack))
		return INT_MIN;
	return stack->array[stack->top];
}

void printStack(struct Stack* stack)
{
    printf("[");
    for (int i = 0; i <= stack->top; i++)
    {
        printf("%d ", stack->array[i]);
    }
    printf("]");
}


int main() 
{   
    struct Stack* stack = createStack();
    push(stack, 10);
    push(stack, 42);
    printStack(stack);
    pop(stack);
    printStack(stack);
}

Ja nie przepadam za alokacjami na stercie jeśli nie jest to absolutnie konieczne. W dodatko w C wszystkie struktury są POD także nie widzę przeciwskazań by przekazywać stos przez wartość do funkcji, które nie potrzebują modyfikować zawartości. Jedyną rzeczą co do której nie mam preferencji to, czy status operacji zwracać przez return czy przez argument. Niżej przykład z użyciem tego pierwszego.

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

typedef struct
{
    int *data;

    size_t size;
    size_t capacity;
} stack_t;

stack_t init(size_t size)
{
    stack_t ret = {
        .data = (int*)malloc(size * sizeof(int)),
        .size = 0,
        .capacity = size
    };

    return ret;
}

bool push(stack_t *stack, int val)
{
    if(stack->data && stack->size < stack->capacity)
    {
        stack->data[stack->size] = val;
        stack->size += 1;
        return 1;
    }

    return 0;
}

bool pop(stack_t *stack, int *retVal)
{
    if(stack->data && stack->size && retVal)
    {
        *retVal = stack->data[stack->size - 1];
        stack->size -= 1;

        return 1;
    }

    return 0;
}

bool is_empty(const stack_t stack) { return stack.size == 0 ;}

bool peek(const stack_t stack, int *retVal)
{
    if(stack.data && stack.size && retVal)
    {
        *retVal = stack.data[stack.size - 1];
        return 1;
    }

    return 0;
}

int main()
{
    stack_t stack = init(5);
    push(&stack, 1);
    push(&stack, 2);
    push(&stack, 3);

    printf("stack size %d\n", stack.size);
    printf("stack capacity %d\n", stack.capacity);
    
    int at0, at1, peek0;
    peek(stack, &peek0);
    pop(&stack, &at0);
    pop(&stack, &at1);
    printf("stack peek 0 %d\n", peek0);
    printf("stack pop 0 %d\n", at0);
    printf("stack pop 1 %d\n", at1);

    printf("stack size %d\n", stack.size);
}

@several: mam na myśli coś takiego (jako bazę użyłem twego kodu):

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

typedef struct
{
    int *data;
    size_t size,capacity;
    bool bad;
} stack_t;

bool is_empty(stack_t *const stack) { return !stack->size; }
bool is_full(stack_t *const stack) { return stack->size>=stack->capacity; }
bool is_bad(stack_t *const stack) { return stack->bad; }
bool is_good(stack_t *const stack) { return !is_bad(stack); }
bool set_bad(stack_t *stack) { return stack->bad|=1; }
bool clear_bad(stack_t *stack) { return stack->bad&=0; }

stack_t init(size_t size)
{
    stack_t ret={ .data=(int*)malloc(size * sizeof(int)), .size=0, .capacity=size, .bad=false };
    return ret;
}

void push(stack_t *stack,int val)
{
	if(is_bad(stack)) return;
    if(is_full(stack)) set_bad(stack);
    else stack->data[stack->size++]=val;
}

int pop(stack_t *stack)
{
	if(is_bad(stack)) return 0;
	if(is_empty(stack)) set_bad(stack);
	else return stack->data[--stack->size];
	return 0;
}

int peek(stack_t *stack)
{
	if(is_bad(stack)) return 0;
	if(is_empty(stack)) set_bad(stack);
	else return stack->data[stack->size-1];
	return 0;
}

int main()
{
    stack_t stack=init(5);
    if(is_good(&stack)) printf("all ok\n");
    int a=pop(&stack),b=pop(&stack),c=pop(&stack);
    push(&stack,1);
    push(&stack,2);
    push(&stack,3);
    if(is_bad(&stack)) printf("one of previouse operation fault\n");
    clear_bad(&stack);
    printf("now all right, stack good %d\n",is_good(&stack));

    push(&stack,1);
    push(&stack,2);
    push(&stack,3);

    printf("stack size %d\n",stack.size);
    printf("stack capacity %d\n",stack.capacity);
    printf("stack good %d\n",is_good(&stack));
    
    int peek0=peek(&stack), at0=pop(&stack), at1=pop(&stack);
    printf("stack peek 0 %d\n",peek0);
    printf("stack pop 0 %d\n",at0);
    printf("stack pop 1 %d\n",at1);
    printf("stack size %d\n",stack.size);
}

Zalety:

• da się łatwo wyśledzić (za pomocą debugera) kiedy i gdzie wartość bad została zmieniona na true,
• ułatwiamy kontrole błędów w kodzie,
• pozbywamy się zwracania statusu po każdej operacji:

A w jaki sposób można napisać taki stos, żeby działał dla różnych typów danych?
W C++ wystarczyłoby dodać template<typename T>, a tutaj?

Malk9 napisał(a):

A w jaki sposób można napisać taki stos, żeby działał dla różnych typów danych?
W C++ wystarczyłoby dodać template<typename T>, a tutaj?

Jesli mozliwe typy sa znane przy pisaniu kolekcji to wydaje sie ze najprosciej zamknac w union. Tyle ze wtedy kolekcja moze zajmowac za duzo pamieci. Jesli typy nie sa znane, lub problem z pamiecia boli, to void* zadziala (oczywiscie wtedy znika pomoc ze strony kompilatora). W API tez bedzie sie musial pojawic rozmiar elementu.

Dla różnych danych kiedyś popełniłem takie coś:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef enum { dt_int, dt_double, dt_string } data_type;
typedef struct { data_type type; char data[0]; } data_node;
typedef void base_proc(data_node *node);
typedef void scan_proc(FILE *fd,data_node *node,size_t count);
typedef void show_proc(FILE *fd,data_node *node);

void init_int(data_node *node) { *(int*)(node->data)=0; }
void init_double(data_node *node) { *(double*)(node->data)=0; }
void init_string(data_node *node) {  *(char**)(node->data)=(char*)calloc(1,1); }

void free_base(data_node *node) {}
void free_string(data_node *node) { free(*(char**)(node->data)); }

void scan_int(FILE *fd,data_node *node,size_t count) { fscanf(fd,"%d",node->data); }
void scan_double(FILE *fd,data_node *node,size_t count) { fscanf(fd,"%lg",node->data); }
void scan_string(FILE *fd,data_node *node,size_t count)
{
	char fmt[16],*tmp=(char*)malloc(count+1);
	free_string(node);
	sprintf(fmt," %%%d[^\n]*%%*[^\n]",count);
	fscanf(fd,fmt,tmp);
	*(char**)(node->data)=strdup(tmp);
	free(tmp);
}

void show_int(FILE *fd,data_node *node) { fprintf(fd,"%d",*(int*)(node->data)); }
void show_double(FILE *fd,data_node *node) { fprintf(fd,"%lg",*(double*)(node->data)); }
void show_string(FILE *fd,data_node *node) { fprintf(fd,"%s",*(char**)(node->data)); }

struct { size_t size,count; base_proc *init,*free; scan_proc *scan; show_proc *show; } dts[]=
{
	{ sizeof(int),     0, &init_int,    &free_base,   &scan_int,    &show_int    },//dt_int
	{ sizeof(double),  0, &init_double, &free_base,   &scan_double, &show_double },//dt_double
	{ sizeof(char*),  32, &init_string, &free_string, &scan_string, &show_string },//dt_string
};

data_node *init_node(data_type type)
{
	data_node *node=(data_node*)malloc(sizeof(data_node)+dts[type].size);
	node->type=type;
	dts[type].init(node);
	return node;
}

void free_node(data_node *node)
{
	dts[node->type].free(node);
	free(node);
}

void scan_node(FILE *fd,data_node *node) { dts[node->type].scan(fd,node,dts[node->type].count); }
void show_node(FILE *fd,data_node *node) { dts[node->type].show(fd,node); }

int main()
{
	const char *caption[] = {"Name","Count","Price"};
	data_node *tb[3];
	tb[0]=init_node(dt_string);
	tb[1]=init_node(dt_int);
	tb[2]=init_node(dt_double);
	for(int i=0;i<sizeof(tb)/sizeof(*tb);++i) { printf("%s: ",caption[i]); scan_node(stdin,tb[i]); }
	for(int i=0;i<sizeof(tb)/sizeof(*tb);++i) { printf("%s: ",caption[i]); show_node(stdout,tb[i]); printf("\n"); }
	for(int i=0;i<sizeof(tb)/sizeof(*tb);++i) free_node(tb[i]);
	return 0;
}