PAMANTASAN NG CABUYAO

COLLEGE OF COMPUTING AND ENGINEERING

COURSE CODE: CPP 104

COURSE DESCRIPTION: DATA STRUCTURES AND ALGORITHM

COURSE INTENDED On the completion of the course, student is expected to be able to do the
LEARNING OUTCOMES: following:

[Link] of basic algorithmic complexity.

[Link] the ability to perform simple inductive proofs and proofs by

contradiction and reason about program correctness and invariants.

[Link] the fundamental abstract data types which can include:

Maps, Sets and Vectors.

LEARNING MATERIAL FOR 4

WEEK NUMBER:

I. TITLE: Stack Abstract Data Type and Linked List Operation

II. OBJECTIVES: By the end of this module you should be able to:

1. Implement the abstract data type list as a linked list using the node
and reference pattern
2. Compare the performance of our linked list implementation with
Python’s list implementation
3. Compare the performance of our linked list implementation with
Python’s list implementation

III. INTRODUCTION:
The major problem with the stack implemented using an array is, it works
only for a fixed number of data values. That means the amount of data
must be specified at the beginning of the implementation itself. Stack
implemented using an array is not suitable, when we don't know the size
of data which we are going to use.

A stack data structure can be implemented by using a linked list data

structure. The stack implemented using linked list can work for an
unlimited number of values. That means, stack implemented using linked
list works for the variable size of data. So, there is no need to fix the size
at the beginning of the implementation. The Stack implemented using
linked list can organize as many data values as we want.

IV. CONTENTS:

Lesson Coverage:

Stack
Operation
Push
POP

LECTURE NOTES COMPILATION Page 1 of 7

2nd Semester A.Y. 2021-2022
 PAMANTASAN NG CABUYAO
COLLEGE OF COMPUTING AND ENGINEERING

Introduction

In linked list implementation of a stack, every new element is inserted as 'top' element. That means every newly
inserted element is pointed by 'top'. Whenever we want to remove an element from the stack, simply remove the
node which is pointed by 'top' by moving 'top' to its previous node in the list. The next field of the first element
must be always NULL.

In the above example, the last inserted node is 99 and the first inserted node is 25. The order of elements inserted
is 25, 32,50 and 99

A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is named stack as
it behaves like a real-world stack, for example – a deck of cards or a pile of plates, etc.

A real-world stack allows operations at one end only. For example, we can place or remove a card or plate from
the top of the stack only. Likewise, Stack ADT allows all data operations at one end only. At any given time, we
can only access the top element of a stack.

This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. Here, the element which is placed
(inserted or added) last, is accessed first. In stack terminology, insertion operation is called PUSH operation and
removal operation is called POP operation.

Stack Representation

The following diagram depicts a stack and its operations −

A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can either be a fixed
size one or it may have a sense of dynamic resizing. Here, we are going to implement stack using arrays, which
makes it a fixed size stack implementation.

LECTURE NOTES COMPILATION Page 2 of 7

2nd Semester A.Y. 2021-2022
 PAMANTASAN NG CABUYAO
COLLEGE OF COMPUTING AND ENGINEERING

STACK OPERATION

Basic Operations

Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from these basic
stuffs, a stack is used for the following two primary operations −

• push() − Pushing (storing) an element on the stack.

• pop() − Removing (accessing) an element from the stack.

When data is PUSHed onto stack.

To use a stack efficiently, we need to check the status of stack as well. For the same purpose, the following
functionality is added to stacks −

• peek() − get the top data element of the stack, without removing it.
• isFull() − check if stack is full.
• isEmpty() − check if stack is empty.

At all times, we maintain a pointer to the last PUSHed data on the stack. As this pointer always represents the top
of the stack, hence named top. The top pointer provides top value of the stack without actually removing it.

First we should learn about procedures to support stack functions −

Algorithm of peek() function −

begin procedure peek

return stack[top]
end procedure

Algorithm of isfull() function −

begin procedure isfull

if top equals to MAXSIZE
return true
else
return false
endif
end procedure

Algorithm of isempty() function −

begin procedure isempty

if top less than 1
return true
else
return false
endif
end procedure

LECTURE NOTES COMPILATION Page 3 of 7

2nd Semester A.Y. 2021-2022
 PAMANTASAN NG CABUYAO
COLLEGE OF COMPUTING AND ENGINEERING

Implementation of isempty() function in C programming language is slightly different. We initialize top at -1, as
the index in array starts from 0. So we check if the top is below zero or -1 to determine if the stack is empty.

Push Operation

The process of putting a new data element onto stack is known as a Push Operation. Push operation involves a
series of steps −

Step 1 − Checks if the stack is full.

Step 2 − If the stack is full, produces an error and exit.

Step 3 − If the stack is not full, increments top to point next empty space.

Step 4 − Adds data element to the stack location, where top is pointing.

Step 5 − Returns success.

If the linked list is used to implement the stack, then in step 3, we need to allocate space dynamically.

Algorithm for PUSH Operation

A simple algorithm for Push operation can be derived as follows −

begin procedure push: stack, data

if stack is full
return null
endif
top ← top + 1
stack[top] ← data
end procedure

Pop Operation

Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation
of pop() operation, the data element is not actually removed, instead top is decremented to a lower position in the
stack to point to the next value. But in linked-list implementation, pop() actually removes data element and
deallocates memory space.

LECTURE NOTES COMPILATION Page 4 of 7

2nd Semester A.Y. 2021-2022
 PAMANTASAN NG CABUYAO
COLLEGE OF COMPUTING AND ENGINEERING

A Pop operation may involve the following steps −

Step 1 − Checks if the stack is empty.

Step 2 − If the stack is empty, produces an error and exit.

Step 3 − If the stack is not empty, accesses the data element at which top is pointing.

Step 4 − Decreases the value of top by 1.

Step 5 − Returns success.

Algorithm for Pop Operation

A simple algorithm for Pop operation can be derived as follows −

begin procedure pop: stack

if stack is empty
return null
endif
data ← stack[top]
top ← top - 1
return data
end procedure

This is a Python program to implement a stack using a linked list.

• Create a class Node with instance variables data and next.

• Create a class Stack with instance variable head.
• The variable head points to the first element in the linked list.
• Define methods push and pop inside the class Stack.
• The method push adds a node at the front of the linked list.
• The method pop returns the data of the node at the front of the linked list and removes the node. It returns
None if there are no nodes.
• Create an instance of Stack and present a menu to the user to perform operations on the stack.

LECTURE NOTES COMPILATION Page 5 of 7

2nd Semester A.Y. 2021-2022
 PAMANTASAN NG CABUYAO
COLLEGE OF COMPUTING AND ENGINEERING

TRY ME:

class Node:
def __init__(self, data):
[Link] = data
[Link] = None

class Stack:
def __init__(self):
[Link] = None

def push(self, data):

if [Link] is None:
[Link] = Node(data)
else:
new_node = Node(data)
new_node.next = [Link]
[Link] = new_node

def pop(self):
if [Link] is None:
return None
else:
popped = [Link]
[Link] = [Link]
return popped

a_stack = Stack()
while True:
print('push <value>')
print('pop')
print('quit')
do = input('What would you like to do? ').split()

operation = do[0].strip().lower()
if operation == 'push':
a_stack.push(int(do[1]))
elif operation == 'pop':
popped = a_stack.pop()
if popped is None:
print('Stack is empty.')
else:
print('Popped value: ', int(popped))
elif operation == 'quit':
break

LECTURE NOTES COMPILATION Page 6 of 7

2nd Semester A.Y. 2021-2022
 PAMANTASAN NG CABUYAO
COLLEGE OF COMPUTING AND ENGINEERING

V. REFERENCES:

J. Bullinaria ( 2019) . Data Structure and Algorithm. Birmingham UK.

M. Goodrich (2013). Data Structures and Algorithms. Wiley

M. Weiss (2007) . Data Structures and Algorithms 2nd Edition . Pearson Int.
B. Baka (2018). Hands – On Data Structures and Algorithm in Python. Packt Publishing

Free Online Reference

[Link]

[Link]

[Link]

VI. ASSESSMENT TASK:

Assessment task is posted as scheduled in our MS Team.

DISCLAIMER

Every reasonable effort is made to ensure the accuracy of the information used in the creation of this
reference material, without prejudice to the existing copyrights of the authors. As an off-shoot of the innumerable
difficulties encountered during these trying times, the authors endeavored to ensure proper attribution of the
esteemed original works, by way of footnotes or bibliography, to their best abilities and based on available
resources, despite the limited access and mobility due to quarantine restrictions imposed by the duly constituted
authorities.

We make no warranties, guarantees or representations concerning the accuracy or suitability of the

information contained in this material or any references and links provided here. Links to other materials in our
CPOD and CAM was made in good faith, for non-commercial teaching purposes only to the extent justified for
the purpose, and consistent with fair use under Sec. 185 of Republic Act No. 8293, otherwise known as the
Intellectual Property Code of the Philippines.

COPYRIGHT NOTICE

Materials contained in the learning packets have been copied and conveyed to you by or on behalf of
Pamantasan ng Cabuyao pursuant to Section IV - The Copyright Act (RA) 8293 of the Intellectual Property Code
of the Philippines.

You are not allowed by the Pamantasan ng Cabuyao to reproduce or convey these materials. The content
may contain works which are protected by copyright under RA 8293. You may be liable to copyright infringement
for any copying and/ or distribution of the content and the copyright owners have the right to take legal action
against such infringement.

Do not remove this notice.

LECTURE NOTES COMPILATION Page 7 of 7

2nd Semester A.Y. 2021-2022