SYSC 2006 Lecture Notes - Lecture 5: C Dynamic Memory Allocation, Linked List
4 May 2018
School
Department
Course
Professor
Implementing a Stack with a Linked List:
A stack is a collection in which the elements are maintained in the order in which they were added
•
•
A stack is a last
-
in, first out (LIFO) collection
-
the most recently added element is the first one retrieved or
removed
•Use a singly-linked list as the data structure where top points to the top of the stack
search for a specific element
○
remove a specific element from the stack
○
retrieve/replace/insert/delete an element at a specific position in the stack
○
Since they are last in, first out stacks do not:•
Structure Definition:
typedef struct {
intnode_t *top;
int size;
} intstack_t;
○NULL if the stack is empty
Top points to the node at the head of the stack's
•
Size contains # of items/nodes in the stack
•
Constructing a Stack:
intstack_t *intstack_construct(void)
{
intstack_t *ptr;
ptr = malloc(sizeof(intstack_t));
// assert(ptr != NULL);
ptr->top = NULL;
ptr->size = 0;
return ptr;
}
Stacks
May 4, 2018
4:46 PM
New Section 1 Page 1
•This returns a pointer to a new, empty stack which is created in malloc and has the structure of a
Creating a Node in a Stack (inserting at the top):
void intstack_push(intstack_t *stack, int value)
{
// assert(stack != NULL);
stack->top = intnode_construct(value, stack->top);
stack->size += 1;
}
• See Previous notes for intnode construct function and it's structure definition
•
○The intnode construct creates a new node at the top of the stock and top now points to the newest
node
○Size is increased as well
This function receives the stack, sends the stack to intnode construct function
Deleting the most recent node and returning that node's value :
int intstack_pop(intstack_t *stack)
{
//assert(stack != NULL);
// terminate via assert if the stack is empty
// assert(stack->top != NULL); or
// assert(stack->size != 0);
int popped;
intnode_t *node_to_delete;
popped = stack->top->value;
node_to_delete = stack->top;
stack->top = stack->top->next;
free(node_to_delete);
stack->size -= 1;
return popped;
}
See Previous notes for intnode construct function and it's structure definition
•
This function receives the stack, stores the value of the newest node in variable popped•
Then a new pointer called node_to_delete points to the newest node while the top pointer is updated
the next member of the newest node ( second newest node)
•
• Then node_to_delete is deleted by freeing it
• Size is decreased and the popped value is returned
New Section 1 Page 2
Document Summary
Since they are last in, first out stacks do not: search for a specific element remove a specific element from the stack retrieve/replace/insert/delete an element at a specific position in the stack. Structure definition: typedef struct { intnode_t *top; int size; Top points to the node at the head of the stack"s. Size contains # of items/nodes in the stack. Constructing a stack: intstack_t *intstack_construct(void) intstack_t *ptr; ptr = malloc(sizeof(intstack_t)); // assert(ptr != null); ptr->top = null; ptr->size = 0; return ptr; New section 1 page 1: this returns a pointer to a new, empty stack which is created in malloc and has the structure of a. Creating a node in a stack (inserting at the top): void intstack_push(intstack_t *stack, int value) // assert(stack != null); stack->top = intnode_construct(value, stack->top); stack->size += 1: see previous notes for intnode construct function and it"s structure definition. This function receives the stack, sends the stack to intnode construct function.
