Algorithms and Data Structures 1
CS 0445
Fall 2024
ADT Stack and ADT Queue
Sherif Khattab
ksm73@[Link]
(Slides are adapted from Textbook and Dr. Ramirez’s CS 0445 slides.)
Stacks
• Some familiar stacks
• Add item on top of stack
• Can only remove topmost item
• Last In, First Out (LIFO)
• First In, Last Out (FILO)
• Items removed in reverse chronological order
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 2
Specifications of the ADT Stack
• Check [Link]
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 3
Design Decision
• When stack is empty
• What to do with pop and peek?
• Possible actions
• Assume that the Stack is not empty
• Return null
• Throw an exception (which type?)
• Can use [Link]
• or define our own Exception class
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 4
Design guidelines for Interfaces
• Use preconditions and postconditions to document assumptions
• Do not trust client to use public methods correctly
• Avoid ambiguous return values
• Prefer throwing exceptions instead of returning values to signal problem
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 5
Interface for ADT Stack
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 6
Interface
An interface for the ADT stack
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 7
Example
push Jim push push Jill push push Joe pop pop
Jess Jane
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 8
Array-Based Implementation
• Each operation involves top of stack
• push
• pop
• peek
• End of the array easiest to access
• Let this be top of stack
• Let first entry be bottom of stack
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 9
In-efficient Implementation
An array that implements a stack; its first location references (a) the top
entry in the stack;
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 10
Efficient Array-Based Implementation
An array that implements a stack; its first location references (b) the
bottom entry in the stack
(b)
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 11
Array-Based Implementation
An outline of an array-based
implementation of the ADT stack
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 12
Array-Based Implementation
• Adding to the top.
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 13
Array-Based Implementation
• Retrieving the top, operation is O(1)
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 14
Array-Based Implementation
An array-based stack after its top entry is removed by (a) decrementing
topIndex;
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 15
Array-Based Implementation
An array-based stack after its top entry is removed by (b) setting
stack[topIndex] to null and then decrementing topIndex
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 16
Array-Based Implementation
• Removing the top
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 17
Linked Implementation
• Each operation involves top of stack
• push
• pop
• peek
• Head of linked list easiest, fastest to access
• Let this be the top of the stack
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 18
Linked Implementation
A chain of linked nodes
that implements a stack
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 19
Linked Implementation
An outline of a linked implementation
of the ADT stack
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 20
Linked Implementation
An outline of a linked implementation
of the ADT stack
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 21
Linked Implementation
A new node that references
the node at the top of the stack;
(a)
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 22
Linked Implementation
(b) the new node is now at the top of the stack
(b)
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 23
Linked Implementation
• Definition of push
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 24
Linked Implementation
The stack before the
first node in the chain is deleted
(a)
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 25
Linked Implementation
The stack after the
first node in the chain is deleted
(b)
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 26
Linked Implementation
• Definition of pop
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 27
Linked Implementation
• Definition of rest of class.
CS 0445 – Algorithms & Data Structures 1 – Sherif Khattab 28
The ADT Queue
• A queue is another name for a waiting line
• Used within operating systems and to simulate real-
world events
• Come into play whenever processes or events must wait
• Entries organized first-in, first-out
© 2016 Pearson Education, Ltd. All rights reserved.
The ADT Queue Interface
© 2016 Pearson Education, Ltd. All rights reserved.
Linked Implementation of a Queue
© 2016 Pearson Education, Ltd. All rights reserved.
Circular-Array Implementation of a Queue
An array that represents a queue: (c) after several
additions, removals; (d) after two more additions that
wrap around to beginning of array
© 2016 Pearson Education, Ltd. All rights reserved.
Circular-Array with One Unused Location
A 7-location circular array holding at most six entries
© 2016 Pearson Education, Ltd. All rights reserved.
Circular-Linked Implementations of a Queue
A circular linked chain with only last-node reference
(a)has more than one node
(b)has one node
(c)is empty
© 2016 Pearson Education, Ltd. All rights reserved.
Two-Part Circular Linked Chain
A two-part circular linked chain that represents:
• a queue and
• nodes available
(a)Empty
(b)after adding one entry
(c)after adding three more entries
© 2016 Pearson Education, Ltd. All rights reserved.
Two-Part Circular Linked Chain
A two-part circular linked chain that represents a queue:
(d) after removing the front entry;
(e) after adding one more entry
© 2016 Pearson Education, Ltd. All rights reserved.
Two-Part Circular Linked Chain
A chain that requires a new node for an addition to a
queue: (a) before the addition; (b) after the addition
© 2016 Pearson Education, Ltd. All rights reserved.
Doubly-Linked Implementation of a Deque
A doubly linked chain with head and tail references
© 2016 Pearson Education, Ltd. All rights reserved.