A stack is not defined by its structure, so much as it is defined by its operations. Basically, anything where you can only remove(pop) the most recently added(pushed) object is a stack. The shunting yard algorithm, which appears to be what you are looking for, is a good example of stack use.
If you understand how to construct a tree, then it is surprising for you to not have been taught to construct a stack. Following is basically a minimalist implementation of a stack, with some testing code.
Code:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// There are basically two good ways to implement a stack,
// One is to use a linked list, in which you add and remove elements from the head of the list.
// The other (generally better) manner is to use a resizable array.
#define STACKSIZE 500
typedef struct {
int data[STACKSIZE];
unsigned int top;
} intstack;
// Pops the top element of the intstack into result.
// Returns 1 on success, 0 on failure.
// This should only fail if the stack is empty.
int intstack_pop (intstack * pop_me, int * result) {
if (pop_me->top == 0) return 0;
--pop_me->top;
*result = pop_me->data[pop_me->top];
return 1;
}
// Pushes push_me onto intstack target.
// Returns 1 on success, 0 on failure
int intstack_push (intstack * target, int push_me) {
if (target->top == STACKSIZE) return 0;
target->data[target->top] = push_me;
++target->top;
return 1;
}
int main (void) {
intstack my_intstack;
int i;
my_intstack.top = 0;
printf ("Pushing 1\n");
assert(intstack_push (&my_intstack, 1));
printf ("Pushing 2\n");
assert(intstack_push (&my_intstack, 2));
assert(intstack_pop (&my_intstack, &i));
printf ("Popping %d\n", i);
for (i = 5; i < 26; ++i) {
printf ("Pushing %d\n", i);
assert(intstack_push(&my_intstack, i));
}
while (intstack_pop(&my_intstack, &i)) {
printf ("Popping %d\n", i);
}
return 0;
}
Originally Posted by +Azazel+
