CHAPTER6-9:CORE DATA
STRUCTURES
COSC 221 (Computer Science B)
Contents
• Motivation
• Stacks
• Queues
• Linked Lists
• Priority Queues
• Applications
Objective
• Define and explain the purpose of Stacks,
Queues, Linked Lists, and Priority Queues.
• Understand and apply the LIFO principle for
stacks and the FIFO principle for queues.
• Perform basic operations for:
• Stacks: push(), pop(), top().
• Queues: enqueue(), dequeue(), first().
• Linked Lists: Insertion, deletion, traversal.
• Priority Queues: insert(), remove_min().
Motivation
Motivation
In computing, we often need to manage data in
specific ways:
• Undoing actions or processing tasks in reverse
order.
• Managing multiple requests in the order they
arrive.
• Efficiently updating and accessing data that
changes over time.
Motivation
To address these, we use data structures like:
• Stacks for reversing data (undo operations).
• Queues for processing data in sequence (task
scheduling).
• Linked lists for flexible data storage.
• Priority queues for prioritizing tasks based on
importance.
These structures help solve common problems and
improve program efficiency.
Stacks
• A stack is a collection of objects that are
inserted and removed according to the last-in,
first-out (LIFO) principle.
Important Operations:
• push(): Add an object to the top
of the stack.
• pop(): Remove and return the
top object from the stack.
• top(): Access (but do not
remove) the top object.
Stacks
• Applications of Stacks:
o Problem: How does a browser
let you go back to previously
visited sites?
o Solution:
Each time you visit a new
site, its address is pushed
onto a stack.
When you click the "back"
button, the browser pops
the most recent address
from the stack.
Stacks
Problem 1: Reversing a String Using a Stack
Steps to Solve:
[Link] each character of the
string onto the stack.
[Link] each character from the
stack to build the reversed string.
[Link] Phase:
•The string "hello" is iterated character by character.
•Each character (h, e, l, l, o) is pushed onto the stack.
•Stack after pushing: ['h', 'e', 'l', 'l', 'o'] (top is o).
Stacks
Problem 1: Reversing a String Using a Stack
2. Pop Phase:
• Characters are popped from the stack one
by one.
• Since the stack is LIFO, the first character
popped is o, then l, l, e, and finally h.
• These characters are concatenated to
form the reversed string "olleh".
Stacks
Problem 2:
Q &A
• Lecture-Code:
13.1 - 13.7
Queue Implementation in Python
• Using a list to implement a simple queue:
Python Code: Queue
• from collections import deque
• queue = deque()
• [Link](1)
• [Link](2)
• print([Link]()) # Output: 1
Priority Queue in Python
• Using heapq for priority queue
implementation:
Python Code: Priority Queue
• import heapq
• pq = []
• [Link](pq, (1, 'Task A'))
• [Link](pq, (3, 'Task C'))
• print([Link](pq)) # Output: (1, 'Task
A')
Linked List Implementation
• Creating a simple linked list in Python:
Python Code: Linked List
• class Node:
• def __init__(self, value):
• [Link] = value
• [Link] = None
• head = Node(10)
• [Link] = Node(20)
• print([Link]) # Output: 20
Applications of Data Structures
• 1. Stacks for Undo functionality
• 2. Queues in task scheduling
• 3. Linked Lists in memory allocation
