CMP 313
Data Structure & Algorithm
INSTRUCTOR
Prof. Dr Rashidah Funke Olanrewaju
Email: frashidah@iium.edu.my
frashidah@nsuk.edu.ng
TEL NO: EXT. 4502/ +6011133097094
FACEBOOK: rashidah lanre
Data Structure: Stack
and Queue
TOPIC 2
Queues
8
Queue
▪ A queue is a first in, first out (FIFO) data
structure
Analysis of Algorithms
A queue represents a waiting list. A queue can
be viewed as a special type of list, where the
elements are inserted into the end (tail) of the
queue, and are accessed and deleted from the
beginning (head) of the queue.
9
Array implementation of queues
front = 0 rear = 3
Initial queue: 17 23 97 44
After insertion: 17 23 97 44 333
After deletion: 23 97 44 333
front = 1 rear = 4
▪ Notice how the array contents “crawl” to the right as
elements are inserted and deleted
▪ This will be a problem after a while!
10
11
Linked-list implementation of queues
BUT: there is a simple
Operations at the
In a queue, insertions way to use a singly-
front of a singly- Because you have to
occur at one end, linked list to
linked list (SLL) are find the last element
deletions at the other implement both
O(1), but at the other each time
end insertions and
end they are O(n)
deletions in O(1) time
You can keep an
You always need a
additional pointer to
pointer to the first
the last thing in the
thing in the list
list
12
SLL implementation of queues
In an SLL you can easily find
Remember, pointers (references)
the successor of a node, but are one-way
not its predecessor
If you know where the last node in a list is, it’s hard to
remove that node, but it’s easy to add a node after it
Use the first element in an SLL as the front of the queue
Hence, Use the last element in an SLL as the rear of the queue
Keep pointers to both the front and the rear of the SLL
Enqueueing a node
Node to be
last enqueued
first
44 97 23 17
To enqueue (add) a node:
Find the current last node
Change it to point to the new last node
Change the last pointer in the list header
13
Dequeueing Node a
node
last
first
44 97 23 17
▪ To dequeue (remove) a node:
▪ Copy the pointer from the first node into the header
14
15
Queue implementation details
With a linked-
With an array
list
implementation:
implementation:
you should set overflow is a there is no
you can have
deleted you can have global out-of- reason to set
both overflow
elements to null underflow memory deleted
and underflow
condition elements to null
16
Queue Operations
Analysis of Algorithms
Queue Animation
Queue Animation
http://liveexample.pearsoncmg.com/liang/animation/web/Queue.
html
17
18
https://people.ok.ubc.ca/ylucet/DS/QueueArray.html
▪ https://people.ok.ubc.ca/ylucet/DS/Qu
https://people.ok.ubc.ca/ylucet/DS/QueueArray.html
eueArray.html
Queue https://people.ok.ubc.ca/ylucet/DS/QueueLL.html
▪ https://people.ok.ubc.ca/ylucet/DS/Qu
implementation https://people.ok.ubc.ca/ylucet/DS/QueueLL.html
eueLL.html
(Array and LL)
Analysis of Algorithms
Priority Queue
A regular queue is a first-in
and first-out data structure.
Elements are appended to the end of
the queue and are removed from the
beginning of the queue.
In a priority queue, elements are assigned
with priorities. When accessing elements, the
element with the highest priority is removed first. A
priority queue has a largest-in, first-out behavior.
For
Example, the emergency room in a hospital
assigns patients with priority numbers; the
patient with the highest priority is treated first.
19
Stacks
A stack is a last in, first out (LIFO) data structure
Items are removed from a stack in the reverse
order from the way they were inserted
Stacks ADT
A stack can be viewed as a
special type of list, where
the elements are accessed,
inserted, and deleted only
from the end, called the top,
of the stack.
23
24
▪ An abstract data type (ADT) is an
abstraction of a data structure
Abstract ▪ An ADT specifies:
Data ▪ Data stored
Types ▪ Operations on the data
▪ Error conditions associated with
operations
Analysis of Algorithms
Abstract Data Types
▪ Focus on what the data structure does
▪ Ignore how it does.
▪ ADT is a class considered without regard to its
implementation.
▪ Examples: Stacks and Queues
▪ They can also be implemented using linked
lists as opposed to array
26
▪ Think of a spring-loaded plate dispenser,
or CD rack
▪ Main stack operations:
▪ push(object): inserts an element
▪ object pop(): removes and returns the
The Stack last inserted element
ADT ▪ Auxiliary stack operations:
▪ object top(): returns the last inserted
element without removing it
▪ integer size(): returns the number of
elements stored
▪ boolean isEmpty(): indicates whether
no elements are stored
27
▪ In the Stack ADT, operations pop and
top cannot be performed if the stack is
empty
▪ Attempting the execution of pop or top
on an empty stack throws an
EmptyStackException
Exceptions
▪ Attempting the execution of an
operation of ADT may sometimes cause
an error condition, called an exception
▪ Exceptions are said to be “thrown” by
an operation that cannot be executed
28
There are two stack errors that can
occur:
• Underflow: trying to pop (or peek at) an empty
stack
• Overflow: trying to push onto an already full stack
For underflow, you should throw an
exception
Error
checking • If you don’t catch it yourself, Java will throw an
ArrayIndexOutOfBounds exception
• You could create your own, more informative
exception
For overflow, you could do the same
things
• Or, you could check for the problem, and copy
everything into a new, larger array
29
Direct applications
• Page-visited history in a Web
browser
• Undo sequence in a text editor
• Reversing of strings
• Chain of method/function calls
Applications (Recursion)
of Stacks • Compiler : Postfix notation
Indirect applications
• Auxiliary data structure for
algorithms
• Component of other data
structures
Pushing and popping
0 1 2 3 4 5 6 7 8 9
stk: 17 23 97 44
top = 3 or count = 4
▪ If the bottom of the stack is at
location 0, then an empty stack is
represented by top = -1 or count =
0
▪ To add (push) an element, either:
▪ Increment top and store the element in stk[top], or
▪ Store the element in stk[count] and increment
count
▪ To remove (pop) an element,
either:
▪ Get the element from stk[top] and decrement top,
or
▪ Decrement count and get the element in stk[count]
Linked-list ▪implementation of stacks
Since all the action happens at the top
of a stack, a singly-linked list (SLL) is
a fine way to implement it
▪ The header of the list points to the
top of the stack
myStack:
44 97 23 17
▪ Pushing is inserting an element at the front of the
list
▪ Popping is removing an element from the front of
31 the list
With a linked-list representation,
overflow will not happen (unless you
exhaust memory, which is another
kind of problem)
Underflow can happen, and should
be handled the same way as for an
Linked-list array implementation
implementation
details When a node is popped from a list,
and the node references an object,
the reference (the pointer in the
node) does not need to be set to null
• Unlike an array implementation, it really is
removed--you can no longer get to it from the
linked list
• Hence, garbage collection can occur as
appropriate
33
Stack operations
Analysis of Algorithms
Stack Animation
www.cs.armstrong.edu/liang/animation/StackAnimation.html
www.cs.armstrong.edu/liang/animation/StackAnimation.html
34
35
https://people.ok.ubc.ca/ylucet/DS/StackArray.html
▪ https://people.ok.ubc.ca/ylucet/DS/Sta
https://people.ok.ubc.ca/ylucet/DS/StackArray.html
ckArray.html
Stack Animation
https://people.ok.ubc.ca/ylucet/DS/StackLL.html
▪ https://people.ok.ubc.ca/ylucet/DS/Sta
(Array and LL
https://people.ok.ubc.ca/ylucet/DS/StackLL.html
ckLL.html
based)
Analysis of Algorithms
36
Python Stack
Implementation
Programming class
Analysis of Algorithms
▪Using an array list to implement Stack
▪Use a linked list to implement a Queue
Since the insertion and deletion operations on
a stack are made only at the end of the stack,
CHECK THIS using an array list to implement a stack is
more efficient than a linked list. Since
deletions are made at the beginning of the
list, it is more efficient to implement a queue
using a linked list than an array list.
37
