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

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

Already have an account? Log in
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
Unlock document

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

Already have an account? Log in

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

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents