Slide #1.

Stacks, Queues, and Linked Lists • Stacks (Last in/First out List) – Operations: Push, Pop, Test Empty, Test Full, Peek, Size • Queue(First in/First out List) – Operations: Insert, Remove, Test Empty, Test Full, Peek, Size • Linked List(A list of elements connected by pointers) – Insert, Delete, Find, Traverse, Size – Advantages: can grow, delete/insert with assignments
More slides like this


Slide #2.

Complexities • Stack: – – – – – Push O(1) Pop O(1) Peek O(1) isEmpty O(1) isFull O(1) • Queue – – – – – Insert O(1) Remove O(1) Peek O(1) isEmpty O(1) isFull O(1) • List – Insert O(1) – Remove O(1) – Search O(N)
More slides like this


Slide #3.

Stack Implementation • With an array – Need stack array and top members. – Push: (top; – Pop: (top>0) ? return stack[--top]:; • With a linked list – Push: insert at front of list. – Pop: remove from front of list. • What are the complexities?
More slides like this


Slide #4.

Stack: Array Implementation int top, arraySize; Data *array[]; void Stack(int s) { array = malloc(sizeof(Data)*s; arraySize = s; top = -1; } int push(Data *s) { if (isFull()) return false; array[++top] =s; return true; } Data *pop() { if (isEmpty()) return null; return array[top--]; } int isEmpty() { return (top < 0); } int isFull() { return top+1 == arraySize; } Data *peek() { if (isEmpty()) return null; return array[top];} Note: In C, non-zero = true, zero = false
More slides like this


Slide #5.

Stack: Linked List Implementation Data *top; Stack() { top = NULL; } void push(Data* d) { d->link=top; top=d; } Data *Pop() { if (isEmpty()) return null; Data *value = top; top = value->link; return value; } int isEmpty() {return (top == NULL);} Data *peek() { return top; }
More slides like this


Slide #6.

Queue Implementation • With an array – – – – Circular Queue Need queue array, size, head, and tail pointers. Insert: (size; Remove: (size > 0) ? return queue[++head%MAX] : ; • With a linked list – Insert: Insert to back of queue – Remove: Remove from front of queue. • What are the complexities?
More slides like this


Slide #7.

Queue: Array Implementation int head, tail, entries; int size; Data *array[]; public Queue(int s) { array = malloc(sizeof(Data)*s); size = s; head =0; tail = -1; entries = 0;} public boolean insert(Data s) { if (isFull()) return 0; if (tail==size) tail = -1; array[++tail] = s; entries++; return 1; } public Data *remove() { if (isEmpty()) return NULL; Data *temp = array[head]; head = (head+1)%size; entries--; return temp; } int isEmpty() Data *peek() } { return entries == 0; } { if (isEmpty() return 0; return array[head]; }
More slides like this


Slide #8.

Queue: Linked List Implementation Data *head, *tail; Queue(int s) { head =null; tail = null; } int Insert(Data *s) { if (isEmpty()) { head = tail = s } else { last->link = value; tail= s; } return true; } Data *Remove() { Data *value = head; if (isEmpty()) return NULL; head = head->link; if (head == NULL) : tail = NULL; return value; } int isEmpty() Data peek() { return (head == null; } { return head; }
More slides like this


Slide #9.

Linked List Implementation See Text Example • With dynamic memory – The data structure uses object links. – Insert/Delete: Search; assignments to change pointers • With an array (Use indices instead of data links) – – – – – Need to list array, size, and pointer to initial entry. Initialization: Create free entry chain. Insert: retrieve from free list if any and do normal insertion. Delete: Do normal insertion logic and then add to free list. The data structure uses primitive links rather than object links.
More slides like this


Slide #10.

Ordered Linked List Insertion Item first; void insert(Item *d ) { Item *previous = null; Item *current = first; while (current!=NULL && d->key > current->key) { previous=current; current=current->next); } if (previous == NULL) first = d; else previous->next = d; d->next = current; } Note: Duplicates OK in this implementation
More slides like this


Slide #11.

Linked List Removal Item remove(Item *d) { Item *current = first; *previous = NULL; do { if (current == null) return NULL; if (!equals(current->key, d->key)) { previous = current; current = current->next; } } while (current!=null && !equals(current->key, d->key)) if (previous == NULL) first = first->next; else previous->next = current->next; return current; }
More slides like this


Slide #12.

Doubly Linked List See Text Example • Two links. One to next record and one to previous. • Characteristics. – – – – More assignments to maintain links. Don’t need the previous temporary pointer. More memory per record. More secure. Used for operating systems.
More slides like this


Slide #13.

Doubly Linked Insertion void insert( Item *d ) { Item *current = first, *previous = NULL; while (current!=NULL&&compareTo(d->key, current->key)<0) { previous = current; current=current->next); } if (current == NULL) { if (previous == NULL) first = current; else previous->next = d; } else { if (current->previous==NULL) { first=d; d->next=current; current->previous=d;} else { d->previous = current->previous; d->next = current; current->previous->next = d; current->previous = d; }
More slides like this


Slide #14.

Doubly Linked Removal int remove(Item *d) { Item *current = first; do { if (current == NULL) return NULL; if (current->key != d->key) {current = current->next; } } while (!equals(current->key, d->key)); if (current->previous == NULL) first = current->next; else current->previous->next = current->next; if (current->next != NULL) current->next->previous = current->previous; return true; }
More slides like this


Slide #15.

Stack Examples • Matching pairs of delimiters • Evaluating infix expressions – Two stacks – First convert to postfix and then evaluate • Expression examples {…{….[..{.<.{..{…}…}…>..].}..} 500/(1+2*(3+4*5/2))*(3*2+1)
More slides like this