Unit-III:

Stack, Queue, Linked List

Dinesh Satre
dinesh.satre@mmit.edu.in
Syllabus
• Unit III: Stacks, Queues and Linked Lists
• Stacks: Stack operations, Multiple Stacks, Applications of Stack for
Expression Conversion [infix, prefix and postfix], Postfix expression
evaluation
• Queues: Queue Operations, Circular Queue, Priority Queue and its
advantages and applications
• Linked list: Introduction of Linked Lists, Primitive Operations on
Linked List- Create, Traverse, Search, Insert, Delete, Sort, and
Concatenate. Types of Linked List: Singly linked, linear and Circular
Linked Lists, Doubly Linked List,
• Case study: Implementation of Stack and Queue operations using
Linked lists
Stacks
● In our everyday life, we come across many examples of stacks,
● For example, a stack of books, a stack of dishes, or a stack of chairs.
● The data structure stack is very similar to these practical examples
Stacks
● We can easily put a new book on the top of the stack, and similarly, we can
easily remove the topmost book as compared to the books lying in-between
or at the bottom positions.
● Elements may be added to or removed from only one end, called the top of a
stack.
Stacks
● A stack is defined as a restricted list where all insertions and deletions are
made only at one end, the top.
● There are two basic operations push and pop that can be performed on a
stack; insertion of an element in the stack is called push and deletion of an
element from the stack is called pop.
● In stacks, we cannot access data elements from any intermediate positions
other than the top position
Primitive Operations
● The three basic stack operations are push, pop, and getTop.
● Besides these, there are some more operations stack_empty, and stack_full.
● The stack_empty operation is useful as a safeguard against an attempt to pop
an element from an empty stack.
● The stack_empty condition is also termed stack underflow.
● Computers always have finite memory capacity, and we do need to check the
stack_full condition before doing push because pushing an element in a full
stack is also an error condition.
● Such a stack full condition is called stack overflow
Push
● The push operation inserts an element on the top of the stack. The recently
added element is always at the top of the stack. Before every push, we must
ensure whether there is a room for a new element
Pop
● The pop operation deletes an element from the top of the stack and returns
the same to the user. It modifies the stack so that the next element becomes
the top element
GetTop
● The getTop operation gives information about the topmost element and
returns the element on the top of the stack
Stack Abstract Data Type
Representation of Stacks using Array
● A stack can be implemented using both a static data structure (array) and a
dynamic data structure (linked list). The simplest way to represent a stack is
by using a one-dimensional array. A stack implemented using an array is also
called a contiguous stack.
Create
● int Stack[100];
● int top = −1;
●
● These statements create an empty stack of size 100, which will hold integer
values, and the variable top is initialized to -1.
Empty
● The stack empty state can be checked by comparing the value of top with the
value -1, because top = -1 represents an empty stack.
●
GetTop
● its behaviour can be described using the following statement
Push
● The push operation inserts an element onto the stack of maximum size
MaxCapacity.
Pop
● The pop operation deletes the element at the top of the stack and returns the
same
Q&A
Which of the following data structures uses the LIFO (Last In First Out) principle?

A. Queue

B. Array

C. Stack

D. Linked List
Q&A
What is the time complexity of the push() operation in a stack implemented using an array?

A. O(n)

B. O(1)

C. O(log n)

D. O(n log n)
Q&A
What operation is used to remove an element from the top of the stack?

A. Insert

B. Delete

C. Push

D. Pop
Q&A
If a stack contains elements [A, B, C] (A at the bottom, C on top), what will be the order of elements popped out?

A. A, B, C

B. C, B, A

C. B, A, C

D. None of the above

Q&A
Which of the following is not an application of a stack?

A. Reversing a string

B. Undo feature in text editors

C. Backtracking algorithms

D. CPU job scheduling

Q&A
Which condition indicates that a stack is full (in an array implementation)?

A. top == 0

B. top == -1

C. top == size - 1

D. top == size + 1
Q&A
In a stack implemented using a linked list, where is the top pointer usually pointing?

A. First node

B. Last node

C. Middle node

D. Null
Multiple Stacks
● Often, data is represented using several stacks. The contiguous stack (stack
using an array) uses separate arrays for more than one stack, if needed. The
use of a contiguous stack when more than one stack is needed is not a
space-effi cient approach, because many locations in the stacks are often left
unused. An effi cient solution to this problem is to use a single array to store
more than one stack.
Multiple Stacks
● Multiple stacks can be implemented by sequentially mapping these stacks
into A[0], ..., A[n − 1]. The solution is simple if we implement only two stacks.
The first stack grows towards A[n - 1] from A[0] and the second stack grows
towards A[0] from A[n − 1].
● This way, we can make use of the space most efficiently so that the stack is
full only when the top of one stack reaches the top of other stack.
Multiple Stacks
● The difficulty arises when we have to represent m stacks in the memory. We
can divide A[0, ..., n - 1] into m segments and allocate one of these segments
to each of the m stacks
Applications of Stack
● The stack data structure is used in a wide range of applications
○ 1. Converting infix expression to postfix and prefix expressions
○ 2. Evaluating the postfix expression
○ 3. Checking well-formed (nested) parenthesis
○ 4. Reversing a string
○ 5. Processing function calls
○ 6. Parsing (analyse the structure) of computer programs
○ 7. Simulating recursion
○ 8. In computations such as decimal to binary conversion
○ 9. In backtracking algorithms (often used in optimizations and in games)
Expression Evaluation And Conversion
● The most frequent application of stacks is in the evaluation of arithmetic
expressions. An arithmetic expression is made of operands, operators, and
delimiters.
● For instance, consider the following expression: X = a/b * c - d
● Let a = 1, b = 2, c = 3, and d = 4.
● One of the meanings that can be drawn from this expression could be X =
(1/2) * (3 - 4) = -1/2
Expression Evaluation And Conversion
●
Expression Evaluation And Conversion
●
Example
● Convert the following expression to its postfix and prefix notations: X = A/B ^
C+D*E-A*C
● By applying the rules of priority and associativity, this expression can be
written in the following form: X = ((A/(B ^ C)) + (D * E) - (A * C))
● Postfix: ABC ^/ DE *+ AC *-
● Prefix: -+/ A ^ BC * DE * AC
Need for Prefix and Postfix Expressions
● The postfix and prefix expressions possess many advantages as follows
○ 1. The need for parenthesis as in an infix expression is overcome in postfix and prefix
notations.
○ 2. The priority of operators is no longer relevant.
○ 3. The order of evaluation depends on the position of the operator but not on priority and
associativity.
○ 4. The expression evaluation process is much simpler than attempting a direct evaluation from
the infix notation
Postfix Expression Evaluation
● The postfix expression may be evaluated by making a left-to-right scan,
stacking operands, and evaluating operators using the correct number from
the stack as operands and again placing the result onto the stack.
Q&A
What is the main reason for using multiple stacks in a single array?

A. To increase memory size

B. To reduce time complexity

C. To optimize memory utilization

D. To simplify stack operations

Q&A
In a two-stack implementation in a single array, how do the two stacks grow?

A. Both grow from left to right

B. Both grow from right to left

C. One grows from left, the other from right

D. Both grow toward the center

Q&A
Which condition is checked to determine if a two-stack array is full?

A. top1 == top2

B. top1 == size - 1

C. top1 + top2 == size

D. top2 - top1 == 1
Q&A
Which of the following is a benefit of using multiple stacks in an array?

A. Dynamic allocation of memory

B. Fixed size for each stack

C. No need for overflow check

D. Better cache performance

Q&A
What is the role of a stack in recursive function calls?

A. It stores all variables

B. It stores return addresses and local variables

C. It replaces the need for memory

D. It executes instructions directly

Q&A
Which of the following real-world applications uses stack logic?

A. Browser history navigation

B. Disk scheduling

C. CPU time slicing

D. Memory paging
Q&A
Which notation does not require parentheses to maintain operator precedence?

A. Infix

B. Prefix

C. Postfix

D. Both B and C
Q&A
What is the postfix form of the expression: (A + B) * (C - D)?

A. AB+CD-*

B. A+B*C-D

C. ABCD+-*

D. +AB-CD*
Q&A
Which of the following is the correct evaluation of the postfix expression 4 5 * 8 2 / +?

A. 24

B. 26

C. 22

D. 18
Queues
● In our daily life, we have experienced standing in queues for various reasons
such as purchasing tickets or getting admission to educational institutes. In all
such places, we have to wait in a queue for our turn to get the service
Queues
● A queue is a common example of a linear list or an ordered list where data
can be inserted at and deleted from different ends. The end at which data is
inserted is called the rear and that from which it is deleted is called the front.
These limits guarantee that the data is processed in the sequence in which
they are entered. In short, a queue is a fi rst in fi rst out (FIFO) or last in last
out (LILO) structure
Queues
● Let Q be an empty queue with Front = Rear = -1. Let max = 5

● Q.Add(11)
Queues
● Q.Add(12)

● . Q.Add(13)
Queues
● A = Q.Delete()

● Q.Add(14)
Queues
● A = Q.Delete()

● A = Q.Delete()
Queue As Abstract Data Type
Realization of queues using Arrays
● Let us see the implementation of the various operations on the queue using
arrays.
● Create:
Realization of queues using Arrays
● Let us see the implementation of the various operations on the queue using
arrays.
● Is_Empty:
Realization of queues using Arrays
● Let us see the implementation of the various operations on the queue using
arrays.
● Is_Full:
Realization of queues using Arrays
● Let us see the implementation of the various operations on the queue using
arrays.
● Add:
Realization of queues using Arrays
● Let us see the implementation of the various operations on the queue using
arrays.
● Delete:
Realization of queues using Arrays
● Let us see the implementation of the various operations on the queue using
arrays.
● getFront:
Circular Queue
● The linear queues using arrays have certain drawbacks
○ 1. The linear queue is of a fixed size. So the user does not have the flexibility to dynamically
change the size of the queue.
○ 2. An arbitrarily declared maximum size of queues leads to poor utilization of memory. For
example, the queue is declared of size 1000 and only 20 of them are used.
○ 3. We need to write a suitable code to make the front regularly catch up with the rear and reset
both. Array implementation of linear queues leads to the Queue_Full state even though the
queue is not actually full.
○ 4. To avoid this, when Queue_Full is signalled, we need to rewind the entire queue to the
original start location (if there are empty locations) so that the first element is at the 0th
location and Front is set to -1. Such movement of data is an efficient way to avoid this
drawback.
Circular Queue
● The technique that essentially allows the queue to wraparound upon reaching
the end of the array eliminates these drawbacks. Such a technique which
allows the queues to wraparound from end to start is called a circular queue.
Virtually, we want the insertion process and the rear to wraparound the
queue.
Advantages of Using Circular Queues
● The following are the merits of using circular queues
○ 1. By using circular queues, data shifting is avoided as the front and rear are modified by using
the mod() function. The mod()operation wraps the queue back to its beginning.
○ 2. If the number of elements to be stored in the queue is fixed (i.e., if the queue size is
specific), the circular queue is advantageous.
○ 3. Many practical applications such as printer queue, priority queue, and simulations use the
circular queue.
Priority Queue
● A priority queue is a collection of a finite number of prioritized elements.
Priority queues are those in which we can insert or delete elements from any
position based on some fundamental ordering of the elements. Elements can
be inserted in any order in a priority queue, but when an element is removed
from the priority queue, it is always the one with the highest priority
Priority Queue
● The following rules are applied to maintain a priority queue:
○ 1. The element with a higher priority is processed before any element of lower priority.
○ 2. If there were elements with the same priority, then the element added first in the queue
would get processed first.
Priority Queue
● The following are some examples of a priority queue
○ 1. A list of patients in an emergency room; each patient might be given a ranking that depends
on the severity of the patient’s illness.
○ 2. A list of jobs carried out by a multitasking operating system; each background job is given a
priority level. Suppose in a computer system, jobs are assigned three priorities, namely, P, Q,
R as first, second, and third, respectively. According to the priority of the job, it is inserted at
the end of the other jobs having the same priority.
Priority Queue
● An example of a priority queue

● After inserting 81 with priority 3

ApplicatIons of Queues
● The most useful application of queues is the simulation of a real world
situation so that it is possible to understand what happens in a real world in a
particular situation without actually observing its occurrence.
● Queues are also very useful in a time-sharing computer system where many
users share a system simultaneously. Whenever a user requests the system
to run a particular program, the operating system adds the request at the end
of the queue of jobs waiting to be executed. Now, when the CPU is free, it
executes the job that is at the front of the job queue. Similarly, there are
queues for shared I/O devices too. Each device maintains its own queue of
requests
ApplicatIons of Queues
● Another useful operation of queues is the solution of problems involving
searching a non-linear collection of states. A queue is used for finding a path
using the breadth-first search of graphs.
Q&A
What is the order of elements in a queue?
A. Last In First Out (LIFO)
B. First In First Out (FIFO)
C. Random
D. Sorted
Q&A
Which of the following is not an operation on a queue?
A. Enqueue
B. Dequeue
C. Peek
D. Push
Q&A
Which data structure is typically used to implement a queue?
A. Array
B. Linked List
C. Both A and B
D. Stack
Q&A
In a circular queue, what condition indicates that the queue is full (assuming 0-based indexing and size is the maximum
size)?
A. rear == size - 1
B. front == rear
C. (rear + 1) % size == front
D. rear == front - 1
Q&A
Which queue variant is used in CPU scheduling?
A. Simple Queue
B. Circular Queue
C. Priority Queue
D. Double-Ended Queue
Q&A
What is the output of the following sequence of operations on an empty queue?
Enqueue(10), Enqueue(20), Dequeue(), Enqueue(30), Dequeue()
A. 10, 20
B. 10, 30
C. 20, 30
D. 10, 30
Q&A
Which of the following is an application of a queue?
A. Recursion
B. Expression evaluation
C. Job Scheduling
D. Tree Traversal (post-order)
Linked Lists
● One of the drawbacks of an array is that it is a static data structure, that is, the
maximum capacity of an array should be known before the compilation
process. Therefore, we must explicitly define its size before compilation.
Practically, defining such static sizes before the compilation of a program
reduces effective space utilization. Accurate predictions about data structure
sizes are very difficult. Another drawback of arrays is that the elements in an
array are stored a fixed distance apart, and the insertion and deletion of
elements in between require a lot of data movement. The linked list is the
solution to overcome all these problems. A linked list using dynamic memory
management follows this principle—allocate and use memory when you need
it and release it (free or deallocate) when you are done
Linked Lists
● A linked list is a very effective and efficient dynamic data structure for linear
lists. Items may be added or deleted from it at any position more easily as
compared to arrays. A programmer does not need to worry about how many
data items a program will have to store. This enables the programmer to
make effective use of the memory, since it works on the principle of need and
supply. This reduces the maintenance of the program, as program
maintenance often includes the need to increase the capacity of a program to
handle larger collections.
Linked Lists
● Arrays and linked lists are examples of linear lists. Linear lists are those in
which each member has a unique successor. Arrays contain consecutive
memory locations that are a fixed Arrays and linked lists are examples of
linear lists. Linear lists are those in which each member has a unique
successor. Arrays contain consecutive memory locations that are a fixed
●
Linked Lists
● A linked list is an ordered collection of data in which each element (node)
contains a minimum of two values, data and link(s) to its successor (and/or
predecessor). A list with one link field using which every element is associated
to its successor is known as a singly linked list (SLL). In a linked list, before
adding any element to the list, a memory space for that node must be
allocated.
●
Linked Lists
● Each node of the linked list has at least the following two elements:
● 1. The data member(s) being stored in the list.
● 2. A pointer or link to the next element in the list.
●
Comparison of Sequential and Linked Organizations
● Sequential organization The features of this organization are the following:
● 1. Successive elements of a list are stored a fixed distance apart.
● 2. It provides static allocation, which means, the space allocation done by a
compiler once cannot be changed during execution, and the size has to be known in
advance.
● 3. As individual objects are stored a fixed distance apart, we can access any
element randomly.
● 4. Insertion and deletion of objects in between the list require a lot of data
movement.
● 5. It is space inefficient for large objects with frequent insertions and deletions.
● 6. An element need not know/store and keep the address of its successive element.
Comparison of Sequential and Linked Organizations
● Linked organization The features of this organization include the following:
● 1. Elements can be placed anywhere in the memory.
● 2. Dynamic allocation (size need not be known in advance), that is, space allocation as per
need can be done during execution.
● 3. As objects are not placed in consecutive locations at a fixed distance apart, random
access to elements is not possible.
● 4. Insertion and deletion of objects do not require any data shifting.
● 5. It is space efficient for large objects with frequent insertions and deletions.
● 6. Each element in general is a collection of data and a link. At least one link field is a must.
● 7. Every element keeps the address of its successor element in a link field.
● 8. The only burden is that we need additional space for the link field for each element.
However, additional space is not a severe penalty when large objects are to be stored.
● 9. Linked organization needs the use of pointers and dynamic memory allocation.
Linked List Terminology
● Header node A header node is a special node that is attached at the
beginning of the linked list. This header node may contain special information
(metadata) about the linked list
●
Linked List Terminology
● Data node The list contains data nodes that store the data members and
link(s) to its predecessor (and/or successor).
● Head pointer The variable (or handle), which represents the list, is simply a
pointer to the node at the head of the list. A linked list must always have at
least one pointer pointing to the first node (head) of the list. This pointer is
necessary because it is the only way to access the further links in the list. This
pointer is often called head pointer, because a linked list may contain a
dummy node attached at the start position called the header node.
● Tail pointer Similar to the head pointer that points to the first node of a linked
list, we may have a pointer pointing to the last node of a linked list called the
tail pointer.
Primitive Operations
● The following are basic operations associated with the linked list as a data
structure:
● 1. Creating an empty list
● 2. Inserting a node
● 3. Deleting a node
● 4. Traversing the list
Primitive Operations
● Some more operations, which are based on the basic operations, are as
follows:
● 5. Searching a node
● 6. Updating a node
● 7. Printing the node or list
● 8. Counting the length of the list
● 9. Reversing the list
● 10. Sorting the list using pointer manipulation
● 11. Concatenating two lists
● 12. Merging two sorted lists into a third sorted list
Realization of linked list
● In a linked organization, the data elements are not necessarily placed in
continuous locations. The relationship between data elements is by means of
a link. Along with each data element, the address of the next element is
stored. Thus, the associated link with each data element to its successor is
often referred to as a pointer. In general, a node is a collection of data and
link(s). Data is a collection of one or more items. Each item in a node is called
a field. A field contains either a data item or a link. Every node must contain at
least one link field.
Realization of Linked List Using Arrays
● Let L be a set of names of months of
the year.
● L = {Jan, Feb, Mar, Apr, May, Jun,
Jul, Aug, Sep, Oct, Nov, Dec}
● Here, L is an ordered set. The linked
organization of this list using arrays
is
Linked List Using Dynamic Memory Management
● We learnt that unlike arrays, linked lists need not be stored in adjacent
locations. Individual elements can be stored anywhere in the memory. Each
data element is called a node. Each node contains at least two fields namely
data and link. Every node holds a link to the next node in the list. During
run-time (execution of a program), as per the need, a node is allocated (i.e.,
memory is allocated for a new node). In other words, a new node of the list
will be created dynamically. We just remember the pointer to the list at the
end, that is, pointer to the first node. In addition, the last node’s link field can
be set to 0 to mark the end of the list. The 0 here represents null. A linked list
thus maintains the data elements in a logical order rather than in a physical
order or in other words separates the physical view from the logical view
Empty Linked List
● An empty linked list is a head pointer with the value Null. An empty list is also
called a null list. The length of a null or empty list is 0.

● We should note the following facts while creating and inserting a node in a
linked list:
● 1. The nodes may not actually reside in sequential locations.
● 2. The locations of nodes may change during different runs of program.
● 3. Therefore, when we write a program that works on lists, we should never
look for a specific address except when we test for 0 (i.e., null).
Empty Linked List
● We need the following for the implementation of linked list:
● 1. A means for allocating memory for a node that has at least one link field.
● 2. A mechanism to verify whether the allocation is successful.
● 3. A mechanism to release the allocated node and add to free pool of
memory, as and when needed.
●
Dynamic Memory Management
● Many languages permit a programmer to specify an array’s size at run-time.
Such languages have the ability to calculate and assign, during execution, the
memory space required by the variables in a program. The process of
allocating memory at run-time is known as dynamic memory allocation.
●
Dynamic Memory Management in C++
● A special area of main memory, called the heap, is reserved for the dynamic
variables. Any new dynamic variable created by a program consumes some
memory in the heap. The heap is a pool of memory from which the new
operator allocates memory. The memory allocated from the system heap
using the new operator is de-allocated (released) using the delete operator.
C++ enables programmers to control the allocation and de-allocation of
memory in a program. The users can dynamically allocate and de-allocate
memory for any built-in or user-defined data structure.
The new Operator
● The new operator creates a new dynamic object of a specified type and
returns a pointer that points to this new object (if it fails to create the desired
object, it returns 0). In standard C++, a program that uses dynamic memory
management should include a standard header <new>, which provides
access to the standard version of the operator new.
●
The Null Pointer
● Null is a special constant pointer value that is used to give a value to a pointer
variable that would not otherwise have a value. It can be assigned to a pointer
variable of any type. In earlier compliers, a check was needed by the user for
the successful operation of new. Newer compliers do not require such a
check. Current compilers throw the exception std::badalloc and the program
automatically aborts with an error message. We need no explicit check in the
code. The users can ‘catch’ the exception.
The delete Operator
● The object created exists till it is explicitly deleted, or till the function/program
runs. To destroy a dynamically allocated variable/object and free the space
occupied by the object, the delete operator is used
●
Linked List Abstract Data Type
data structure of node
insertion of a node
● Insertion of a Node at a Middle Position
insertion of a node
● Insertion of a Node at the First Position
insertion of a node
● Insertion of a Node at the End
Linked List traversal
Deletion of a Node
● Deleting the First Node
Deletion of a Node

● Deleting a Middle Node

Types of Linked List
● Linked lists can be classified broadly as follows
● 1. Singly linked list
● 2. Doubly linked list
●
Singly Linked List
● A linked list in which every node has one link fi eld, to provide information
about where the next node of the list is, is called as singly linked list (SLL). It
has no knowledge about where the previous node lies in the memory. In SLL,
we can traverse only in one direction. We have no way to go to the ith node
from (i + 1)th node, unless the list is traversed again from the first node
●
Doubly Linked List
● In a doubly linked list (DLL), each node has two link fields to store information
about the one to the next and also about the one ahead of the node. Hence,
each node has knowledge of its successor and also its predecessor. In DLL,
from every node, the list can be traversed in both the directions
●
Linear and Circular Linked Lists
● The other classification of linked lists based on their method of traversal is as
follows:
● 1. Linear linked list
● 2. Circular linked list
●
Circular Linked List
● Although a linear linked list is a useful and popular data structure, it has some
shortcomings. For example, consider an SLL. Given a pointer A to a node in a
linear list, we cannot reach any of the nodes that precede the node to which A
is pointing. This disadvantage can be overcome by making a small change.
This change is without any additional data structure. The link field of the last
node is set to Null in a linear list to mark the end of the list. This link field of
the last node can be set to point to the first node rather than Null. Such a
linked list is called a circular linked list
●
Q&A
What is a linked list?

A. A data structure that stores elements in contiguous memory locations

B. A data structure where elements are linked using pointers
C. A collection of arrays
D. A type of stack
Q&A
What does each node in a singly linked list contain?

A. Only data
B. Data and previous node pointer
C. Data and next node pointer
D. Only a pointer
Q&A
What is the time complexity of inserting an element at the beginning of a singly linked list?

A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
Q&A
Which of the following allows traversal in both directions?

A. Singly linked list

B. Doubly linked list
C. Circular singly linked list
D. Array
Q&A
Which type of linked list has the last node pointing to the first node?

A. Circular linked list

B. Doubly linked list
C. Singly linked list
D. Array
Q&A
In a circular doubly linked list with n nodes, how many pointers does each node contain?

A. 1
B. 2
C. 3
D. 4
Q&A
Which of the following is not an advantage of linked lists over arrays?

A. Dynamic size
B. Ease of insertion/deletion
C. Random access of elements
D. Efficient memory usage
Q&A
In a singly linked list, if the head node is NULL, what does it signify?

A. List has one node

B. List is empty
C. List is full
D. Invalid list
Q&A
What will be the result of the following operation?

node->next = node;
A. Node is deleted
B. Node is linked to itself
C. Runtime error
D. Node is linked to null