Scribd
Upload
41 views

Data Structure: Instructor: Dr. Wei (Lisa) Li Department of Computer Science, GSU

This document provides an overview of different data structures including stacks, queues, linked lists, and binary trees. It describes the key elements and operations for each structure, such as LIFO for stacks, FIFO for queues, pointers for linked lists, and parent/child relationships for binary trees. Example code is given for common operations like insert, delete, search on each structure.

Uploaded by

Cory Patterson
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
41 views

Data Structure: Instructor: Dr. Wei (Lisa) Li Department of Computer Science, GSU

This document provides an overview of different data structures including stacks, queues, linked lists, and binary trees. It describes the key elements and operations for each structure, such as LIFO for stacks, FIFO for queues, pointers for linked lists, and parent/child relationships for binary trees. Example code is given for common operations like insert, delete, search on each structure.

Uploaded by

Cory Patterson
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 13

Data Structure

Instructor: Dr. Wei (Lisa) Li


Department of Computer Science, GSU

Data Structure
Dynamic sets (Data structures):
Change a dictionary, add/remove words
Reuse of structured information
On-line algorithms - very fast updating

record
index key

Elements:
Index: element ID
Key: value of element

Operations
Query/Search: return information about the set, e.g., maximum,
minimum
Modifying Operations: change data sets, e.g., insert, delete

Stack
Stack: S[1, 2, , S.top]
S.top points to the most recently inserted element

LIFO (last-in first-out) policy


Insert: O(1)
Push(S, x)
S.top = S.top + 1
S[S.top] = x
Push(S, 17) and Push(S, 3)

Stack (cont.)
Empty: O(1)
Stack-Empty(S)
if S.top == 0
return TRUE
else return FALSE

Pop(S)

Delete: O(1)
Pop (S, x)
if S.top == 0
Return Empty
else S.top = S.top -1
Return S[S.top+1]

Queue
Queue: Q[1, 2, , n]
Q.head points to head
Q.tail points to location at which a newly arriving element will be
inserted into the queue
Empty: Q.head == Q.tail
Full: Q.head == Q.tail + 1

FIFO (first-in first-out) Policy


Out from head
In to tail

Queue (cont.)
Insert: O(1)
Enqueue(Q, x)
Q[Q.tail] = x
if Q.tail == Q.length
Q.tail = 1
else Q.tail = Q.tail + 1

//Q.tail is at the end


//Place Q.tail in a circular order

Enqueue(Q, 17), Enqueue(Q, 3), and Enqueue(Q, 5)

Queue (cont.)
Delete: O(1)
Dequeue(Q)
x = Q[Q.head]
if Q.head == Q.length
//Q.head is at the end
Q.head = 1
//Place Q.head in a circular order
else Q.head = Q.head + 1
return x
Dequeue (Q)

Linked List
Doubly Linked List: prev and next
Head: x.prev == NIL
Tail: x.next == NIL
Empty: x.head == NIL

List Search
List-Search(L, k): O(n)
x = L.head
while x NIL and x.key k
x = x.next
return x

List Insertion
List-Insert(L, x): O(1)
x.next = L.head
if L.head NIL
L.head.prev = x
L.head = x
x.prev = NIL

10

List Deletion
List-Delet(L, x): (any element O(1); a given element O(n))
if x.prev NIL
x.prev.nex = x.next
else L.head = x.next
//x is head of list
if x.next NIL
x.next.prev = x.prev

11

Binary Tree
Structure Attributes: parent (p), left child (left),
and right child (right)
Root: x.p == NIL
Leaf: x.left == x.right == NIL
Empty: T.root == NIL

12

Exercise
Draw the binary tree rooted at index 6 that is represented
by the following attributes:

13

You might also like