structures

Stack Implementation in C

As an exercise I decided to combine my Data Structures class which is taught mostly through the medium of the Java programming language and my Procedural Programming class using C.  I built a stack implementation based on a linked list


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

struct node* peek(struct stack *stk);
struct node* pop(struct stack *stk);
void push(struct stack *stk, struct node *n);

struct node
{
	//you could put any variables you like in here and be able to use the stack the same
	int index;
	struct node *next;
};

struct stack
{
	//basically just a variable pointing to the head of the linked list
	struct node *head;
};

void main()
{
	int i;
	struct node n, x;
	struct stack stackyStack;

	stackyStack.head = &n;
	n.index=0;
	printf("test: %d\n", peek(&stackyStack)->index);
	

	for(i = 1; i < 10; i++)
	{
		x.index=i;
		push(&stackyStack, &x);
		printf("test: %d\n", peek(&stackyStack)->index);
	}

	printf("\n\n");
	for(i = 9; i >= 0; i--)
	{
		printf("pop pop! %d\n", pop(&stackyStack)->index);
	}

	system("pause");
}

struct node* peek(struct stack *stk)
{	
	//shows the contents of the top of the stack without removal
	return stk->head;
}

struct node* pop(struct stack *stk)
{
	struct stack newstk = *stk;
	struct node tmp; 

	//store the current head in local variable
	tmp = *newstk.head;

	//making the top of the stack be where the current head is pointing
	stk->head = stk->head->next;
	
	return &tmp;
}

void push(struct stack *stk, struct node *n)
{
	//allocate new memory of node size for dynamically growing stack
	struct node* tmp = (struct node*)malloc(sizeof(struct node));

	//fill info in new node
	tmp->index = n->index;
	//point the new node to the old head
	tmp->next = stk->head;
	//make the new node the head of the stack
	stk->head = tmp;
}

stackImp

My next project with it is to make it a character stack and then use it in a program capable of evaluating basic arithmetic expressions or convert arithmetic expressions to inverse polish notation.

I still have to get round to fixing the memory allocation issue but I have decided to do that when I make it into a header file and have to fix the return types etc.

Any feedback or pointers welcome as usual!