Chapter 3:

Objectives:
At the end of the chapter, the students will be able to:

• Differentiate Stack and Queue

• Identify the methods that are being used in stack and queue.
• Know the different linked list operations in stack and queue.
Chapter 3: Stack and Queue Abstract Data Types and Its Linked Lists
Operations
Lesson 1: Stack and Queue
Stack

• In programming, a stack is an abstract, linear data type with a predefined capacity (or
boundary).
• It follows a particular order for adding or removing elements.
• Linear data structures organized their components in a straight line, so if we add or
remove an element, they will grow or shrink respectively.

• Last In First Out (LIFO) or First In Last Out (FILO) - To conceptualized stacks using a stack
of plates placed in a box. The first plate placed in the stack (the plate at the bottom of
the stack) will be the last one to removed, and the plate added last would be the first
to be removed.
• Stacks are used in a variety of ways when we code. We use stacks to implement
functions, parsers, expression evaluation, and some algorithms.
• Stacks are great for processing nested structures, so they are important for
understanding recursion.
• A simple real-world application of a stack is reversing a string letter by letter. Another
good example of a data stack is the undo and redo function on a computer or text
editor. Undo removes your mist recent change, and redo builds upon already existing
changes.
• How do Stacks work?
- The pop method removes or deletes elements from the stack, while
the push method adds items to the stack.
- When an element is inserted into a stack, it takes the top position and the
variable storing this position points to the number below it. The top variable
should be updated anytime an element is inserted or removed from it.
- What’s important to remember is that insertion and deletion happen on the
same end of a Stack.

Linked List Implementation of Stack

• Instead of using array, we can also use linked list to implement stack. Linked list
allocates the memory dynamically. However, time complexity in both the scenario is
same for all the operations i.e. push, pop and peek.
• In linked list implementation of stack, the nodes are maintained non-contiguously in the
memory. Each node contains a pointer to its immediate successor node in the stack.
• Stack is said to be overflown if the space left in the memory heap is not enough to
create a node.

• The top most node in the stack always contains null in its address field.

Queue

• Queue is a lot like stack.

• Queue is also a linear structure that follows a First in First Out (FIFO) order, but they differ
in how elements are removed.
• Queues are open from both ends: one end for inserting data (enqueue), and the other
end for removing data (dequeue).
• Note that in stack, we remove the most recently added element, but for queue, we
remove the “oldest” element.
• When it comes to queues, think of a checkout counter at your favorite grocery store. The
first person in the checkout line will be attended to first before others, and the last person
in line will be attend to last. This is how queue works. It has two ends, front and rear.
• Elements enter from the rear and leave from the front.

Types of Queues

• There are three common types of queues you can expect to encounter. So farm we
learned about the Linear Queue. The other two queues are:
1. Circular Queue: In a circular queue, the last element is connected to the first
element to form a circle. Initially, the front and rear parts of the queue point to
the same location, but they move apart as more elements are inserted into the
queue. A real-life example of a circular queue is an automated traffic signal
system.
2. Priority Queue: In priority queues, elements are sorted based on priority. The most
important element appears first, and the least important appears last. Priority
queues are used in operating systems for load balancing to determine which
programs should be given more priority.

Linked List implementation of Queue

• The array implementation cannot be used for the large scale applications where the
queues are implemented. One of the alternatives of array implementation is linked list
implementation of queue.
• In a linked queue, each node of the queue consists of two parts i.e. data part and the
link part. Each element of the queue points to its immediate next element in the
memory.
• In the linked queue, there are two pointers maintained in the memory i.e. front pointer
and rear pointer. The front pointer contains the address of the starting element of the
queue while the rear pointer contains the address of the last element of the queue.
• Insertion and deletions are performed at rear and front end respectively. If front and
rear both are NULL, it indicates that the queue is empty.
• The linked representation of queue:

Pros and Cons of Stack and Queues

Stacks Queues
Pros
• It is easy to implement and logical • Queues are flexible.
for beginners. • They can handle multiple data
• It allows you to control how memory types.
is allocated. • Data queues are fast and
• Easier to use than queues. optimized.
Cons
• Neither flexible nor scalable. • Inserting/removing elements from
• Random access to elements in a the middle is complex.
stack is nearly impossible. • Queues are not readily searchable.

Essential Operations for Stacks & Queues

• A typical stack must contain the following methods:

- pop(): this method removes an element from the top of the stack and returns it.
- push(): this method adds an element to the top of the stack.

• A queue allows for the following operations:

- enqueue(): this method adds an element to the end/rear of the queue

- dequeue(): this method removes an element from the front of the queue
- top(): returns the first element in the queue
- initialize(): creates an empty queue

• From there we can apply all sorts of methods for more functionality and information
retrieval:

- top(): returns the element most recently added to the stack

- intStack.peek(): returns the top of the stack without removing an element
- poll(): removes the head of a queue and returns it
- size(): returns the size of the queue as number of elements
- isEmpty(): returns true if the stack/queue is full
- isFull(): returns true if the stack/queue is full

Stack in Python

Sample Program
Push Stack
class Stack:

def init (self):

self.stack = []

def add(self, dataval):

# Use list append method to add element
if dataval not in self.stack:
self.stack.append(dataval)
return True
else:
return False
# Use peek to look at the top of the stack

def peek(self):
return self.stack[-1]

AStack = Stack()
AStack.add("Mon")
AStack.add("Tue")
AStack.peek()
print(AStack.peek())
AStack.add("Wed")
AStack.add("Thu")
print(AStack.peek())

OUTPUT

Tue
Thu

Sample Program
POP from a Stack
class Stack:

def init (self):

self.stack = []

def add(self, dataval):

# Use list append method to add element
if dataval not in self.stack:
self.stack.append(dataval)
return True
else:
return False

# Use list pop method to remove element

def remove(self):
if len(self.stack) <= 0:
return ("No element in the Stack")
else:
return self.stack.pop()

AStack = Stack()
AStack.add("Mon")
AStack.add("Tue")
AStack.add("Wed")
AStack.add("Thu")
print(AStack.remove())
print(AStack.remove())
OUTPUT

Thu
Wed

Implementing the Queue Class

Sample Program
class Queue:

def init (self):

self.queue = list()

def addtoq(self,dataval):
# Insert method to add element
if dataval not in self.queue:
self.queue.insert(0,dataval)
return True
return False

def size(self):
return len(self.queue)

TheQueue = Queue()
TheQueue.addtoq("Mon")
TheQueue.addtoq("Tue")
TheQueue.addtoq("Wed")
print(TheQueue.size())

OUTPUT

Sample Program
class Queue:

def init (self):

self.queue = list()

def addtoq(self,dataval):
# Insert method to add element
if dataval not in self.queue:
self.queue.insert(0,dataval)
return True
return False
# Pop method to remove element
def removefromq(self):
if len(self.queue)>0:
return self.queue.pop()
return ("No elements in Queue!")

TheQueue = Queue()
TheQueue.addtoq("Mon")
TheQueue.addtoq("Tue")
TheQueue.addtoq("Wed")
print(TheQueue.removefromq())
print(TheQueue.removefromq())

OUTPUT

Mon
Tue
Assessment
I. Code the following output:
1. Remove Saturday from the output below:
Sunday
Monday
Tuesday
Wednesday
Thursday
Friday
Saturday
2. Print the number of elements showing below:
Jher
Ryan
Derech
Mervin
3. Provide the output of the code below:
class Stack:

def init (self):

self.stack = []

def add(self, dataval):

# Use list append method to add element
if dataval not in self.stack:
self.stack.append(dataval)
return True
else:
return False

# Use list pop method to remove element

def remove(self):
if len(self.stack) <= 0:
return ("No element in the Stack")
else:
return self.stack.pop()
AStack = Stack()
AStack.add("Enero")
AStack.add("Pebrero")
AStack.add("Marso")
AStack.add("Abril")
AStack.add("Mayo")
AStack.add("Hunyo")
print(AStack.remove())
print(AStack.remove())
print(AStack.remove())

References

Ejonavi, J. (2020). Data Structures 101: how to use Stacks and Queues in Java. Retrieved
2021, from Educative: https://www.educative.io/blog/data-structures-stack-
queue-java-tutorial

Linked List implementation of Queue. (n.d.). Retrieved 2021, from Java T. Point:
https://www.javatpoint.com/linked-list-implementation-of-queue

Linked list implementation of stack. (n.d.). Retrieved 2021, from Java T Point:
https://www.javatpoint.com/ds-linked-list-implementation-of-stack