Scribd
Upload
2 views93 pages

Lectures Stack Queue Edited

This document covers Abstract Data Types (ADTs) focusing on data structures such as Stacks, Queues, and Priority Queues. It discusses stack operations, implementations, and applications, including infix to postfix conversion and evaluation of expressions. Additionally, it addresses queue operations and their implementations, particularly using linked lists and heaps for priority queues.

Uploaded by

guptacherag
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views93 pages

Lectures Stack Queue Edited

This document covers Abstract Data Types (ADTs) focusing on data structures such as Stacks, Queues, and Priority Queues. It discusses stack operations, implementations, and applications, including infix to postfix conversion and evaluation of expressions. Additionally, it addresses queue operations and their implementations, particularly using linked lists and heaps for priority queues.

Uploaded by

guptacherag
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Abstract Data Type (ADT)

programming language.

but we don't know about the implementation details.

In this lecture, we will look into Stacks, Queue and Priority Queues
Stack Data Structure
Stack Examples in Real Life
Stack Data Structure
Stack Data Structure
Stack Data Structure Applications
Standard Stack Operations
Stack Push Operation
Stack Push Operation
Stack Push Operation
Stack Push Operation
Stack Push Operation
Stack Push Operation
Stack Pop Operation
Stack Pop Operation
Stack Pop Operation
Stack Pop Operation
Stack Pop Operation
Stack Pop Operation
Checking if Stack is Full?

if TOP equals to MAXSIZE // Maximum size of stack


Checking if Stack is Empty?

if TOP==-1 /*If 0 based indexing is used*/


Peep Operation

end routine
Count elements of stack
Representation of stacks
Representation of stacks
An Array-Based Stack
Pseudo-code for Array-Based Stack
Pseudo-code (contd.)
Pseudo-code for Array-Based Stack
Representation of stacks
Implementation of Stack
Hint for Implementation in Labs (C)
Infix, Postfix and Prefix Notations
Postfix simplifies expressions
Using stack to help in evaluation
Evaluating Postfix Expressions
Evaluating Postfix Expressions
Evaluating Postfix Expressions
Question
Evaluating Postfix Expressions

int op1 = [Link]()

[Link] (token);
Infix to Postfix
Order of precedence
Algorithm for Infix to Postfix conversion
A*B+C
A+B*C
A * ( B + C)
FPE
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
FPE Infix to Postfix
Homework exercise
Homework Solution
Recursion based on stacks: Factorial
Recursion based on stacks: Factorial Program
Queues in real life
Queue Data Structure
Basic operations-Queue Data Structure

dequeue(): To remove items from queue.

isfull(): To check if queue is full or not.


Queue: Enqueue operation
Queue: Dequeue operation
Enqueue-dequeue operations
Implementation of Queue Data Structure
Linked list implementation of Queue

Rear
Linked List implementation of Queue
Linked List implementation of Queue

QNode* new_node = new

return;

}
isempty()

// If the front and rear are null, then the queue is

}
peek() / getFront()
Priority Queues
Priority Queues-Example
Priority Queue
Priority Queue
Implementation of Priority Queue

How would you implement using:

a heap data structure,

You might also like