# SYSC 2006 Lecture Notes - Lecture 5: C Dynamic Memory Allocation, Linked List

78 views5 pages
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
Unlock document

This preview shows pages 1-2 of the document.
Unlock all 5 pages and 3 million more documents.

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
Then node_to_delete is deleted by freeing it
Size is decreased and the popped value is returned
New Section 1 Page 2
Unlock document

This preview shows pages 1-2 of the document.
Unlock all 5 pages and 3 million more documents.

## 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.

## Get access

\$8 USD/m\$10 USD/m
Billed \$96 USD annually
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class