Transcript ELEMENTARY DATA STRUCTURES

ELEMENTARY DATA
STRUCTURES
Stacks, Queues, and
Linked Lists
Elementary Data
Structures
Used as programming tools
(stacks & queues)
- software (i.e. compilers)
- used in the operations of a certain task
Implemented in CPU instructions
- hardware
Stacks
Definition
 container of objects
 uses LIFO principle for object operations
 operations are push and pop
Sample uses :
 Internet browsers
 Undo / Redo feature
Other Applications
Parsing
- check for matching parenthesis or
brackets
- aid for algorithms applied to complex
data structures (traverse nodes of a tree
and searching vertices of a graph)
Basic Stack Operations
push(o)
pop()
Inserts object o onto
top of stack
Input: object
Output: none
Removes the top
object of stack and
returns it to calling
method
Input: none
Output: object
Related Stack Operations
isEmpty()
isFull()
Returns a boolean
indicating if stack is
empty.
Input: none
Output: boolean
Returns a boolean
indicating if stack is
full
Input: none
Output: boolean
Other Stack Operations
size() :
top()
Returns the number
of objects in stack.
Input: none
Output: integer
Returns the top
object of the stack.
Input: none
Output: object
An Array-Based Stack
Create an array A of size N
Store elements of stack S in array A
Let t (integer) - index of the top element
of stack S
S
0 1 2 3
t ... N-1
Array Implementation
Algorithm size()
return t + 1
Algorithm isempty()
return (t<0)
Algorithm push(o)
if size()=N then
throw a STACKEMPTYEXCEPTION
t=t+1
S[t]=o
Array Implementation
 Algorithm pop()
if isempty() then
throw a STACKEMPTYEXCEPTION
e=S[t]
S[t]=null
t=t-1
return e
 Algorithm top()
if isempty() then
throw a STACKEMPTYEXCEPTION
return S[t]
Class Problem
Using the stack functions, make an
algorithm that will determine that given a
string x :
a) has matching operands (i.e. (),{},[])
b) report an error if an operand is missing
Example :
x = “(12xxs3e)”, correct
x = “(sdfsdfs}”, error
Class Problem - Summary
1.
2.
3.
4.
Make an empty stack
Read characters until end of file
If the character is an open anything, push it in the stack
If it’s a close anything,then if stack is empty, report an
error, otherwise, pop the stack
5. If popped symbol is not the corresponding opening
symbol, then report an error
6. At end of file, if stack is not empty report an error
Stacks- other applications
Recursion
- i.e. computing for N factorial
Operand parsing
- evaluating an expression
- i.e. ((4*5)+(6+2)/5))
- postfix notation
A*B+C = AB*C+
function calls
- variables and routine position are saved
Stacks - Query
How can the undo/redo function be
implemented using stacks ?
QUEUES
A queue is a container of objects that are
inserted and removed according to the FIFO
principle.
Operations:
Enqueue - insert an item at the rear of
queue
 Dequeue - remove an item from the front of
the queue
Sample uses : movie line
printing queue
The Queue Abstract Data
Type
enqueue(o)
dequeue()
Insert object o at the
rear of the queue
Input: object
Output: none
Remove the object
from the front of the
queue and return it.
Input: none
Output: object
The Queue Abstract Data
Type
size() : Returns the number of objects in
the queue.
Input: none
Output:
object
isEmpty(): Return a boolean indicating if
the queue is empty.
Input: none
Output:boolean
front(): Return the front object of the
queue.
Array Implementation
Create a queue using an array in a circular
fashion
Queue consists of an N-element array Q
and two integer variables:
f : index of the front element
r: index of the element after the
rear one
Configurations : “normal”
“wrapped around”
Queue Implementation
f
Array Q
r
f is an index to a cell Q storing the first
element, r is an index to the next
available cell in Q
Queues- Example
Print Jobs
- All requests from workstations are
enqueued to the print queue on a first
come first served basis
- The current (first) printjob is dequeued
and sent to the printer for processing
Queue - Applications
I/O Request Handling
File server - Workstation (print, data
access,etc.)
Telephone Call Handling
History functions in applications
Limitations - Using Arrays
Maximum size needs to be predetermined
Potential wastage of allocated memory
Need to handle overflow
Linked List ADT
Head
next
next
next
null
Each node stores a reference to an element
and a reference, called next to another node
Singly Linked List
Queue Implementation
Nodes connected in a chain by links
head
tail
head of the list - front of the queue
tail of the list - rear of the queue
Removing at the Head
head
tail
advance head reference
head
tail
Inserting at the Tail
create a new node
head
tail
chain it and move the tail reference
head
tail
Other Advantages
Insertions and deletions are easier
compared to an array implementation
when dealing with “lists”
Linked Lists - Query
If a stack will be implemented using a
linked list, is it better to assign the head
or the tail as the top of the stack ? Why ?
Double-Ended Queues
Data structure that allows insertion and
deletion at the front and the rear end of
the queue (pronounced as “deck”)
Doubly linked lists
A node in a doubly linked list is like a
node in a singly linked list except that, in
addition to the next link, it also has a prev
link to the previous node in the list.
Advantage over singly linked lists :
deletions at the tail of the list can be done
in constant time
Doubly-Linked Lists
Linked Lists - Query
What is the running time to search for an
entry in a linked list ? Deleting from the
tail ? Inserting from the head ?