Lab46 Wiki

Was in the hospital a few days. Matt went over “stacks” while I was gone. A Stack uses a First In Last Out or Last In First Out data structure. A Queue uses a First In First Out or Last In Last Out data structure. Stacks have 3 main functions:

1. pop(): Removes the top element off the stack.
2. push(): Adds an element to the top of the stack.
3. peek(): Shows the top of the stack. It does this by poping an element from the stack then pushing the same element back onto the stack.

Stacks also have an important pointer, top(), that always points to the top of the stack. This is sometimes called the “Stack Pointer”. Matt emailed the code from class (with no comments ). Also, the knowledge assessments should be finished by next week. While brainstorming ideas I realized that it might be easier to write my sortList() function using the appendNode() and removeNode() functions.

pop.c

#include "stack.h"
 
Node *pop(Stack **myStack)
{
	Node *tmp = NULL;
 
	if ((*myStack) != NULL)
	{
		tmp = removeNode((*myStack) -> data, (*myStack) -> data -> end);
		(*myStack) -> top = (*myStack) -> data -> end;
	}
 
	return (tmp);
}

push.c

#include "stack.h"
 
Stack *push(Stack *myStack, Node *newNode)
{
	if ((myStack -> size <= 0) || ((myStack -> data -> qty) < (myStack -> size)))
	{
		myStack -> data = append(myStack -> data, myStack -> data -> end, newNode);
		myStack -> top  = myStack -> data -> end;
	}
 
	return(myStack);
}

peek.c

#include "stack.h"
 
Node *peek(Stack *myStack)
{
	// exercise left to the implementer
}

stackops.c

#include "stack.h"
 
Stack *mkstack(int size)
{
	Stack *myStack;
 
	myStack = (Stack *) malloc (sizeof(Stack));
 
	myStack -> data = mklist();
	myStack -> size = size;
	myStack -> top  = myStack -> data -> end;
 
	return (myStack);
}

stack.h

#ifndef _STACK_H
#define _STACK_H
 
#include "list.h"
 
struct stack {
	List *data;
	Node *top;
	int size;
};
typedef struct stack Stack;
 
Stack *mkstack(int);
Stack *push   (Stack *, Node *);
Node  *pop    (Stack **);
Node  *peek   (Stack *);
 
#endif

A copy of the code is also available in the /var/public/data/fall2013/stacks/ directory on lab46.

Matt also added a few new things that need to be implemented into the doubly linked list program:

1. Add a qty variable (int) to your Linked List struct.
2. Update linked list functions to appropriately update qty so it contains an accurate list count
3. Add a mklist() function, in the spirit of create() function on the knowledge assessments, and a mkstack() in our stack implementation.