Stacks & Queues By Ms. Niti Arora

63 %
38 %
Information about Stacks & Queues By Ms. Niti Arora

Published on October 28, 2007

Author: kulachihansraj

Source: slideshare.net

Description

A lesson to teach Stacks & Queues.

Let’s learn TACKS & UEUES for CLASS XII( C++) SENIOR SECONDARY GROUP Presented By : NITI ARORA

STACKS AND QUEUES

Objective Introduction to Data Structure Array and Link list Stack Array implementation of Stack Linked Implementation of Stack Queue Array implementation of Queue Linked Implementation of Queue

Introduction to Data Structure

Array and Link list

Stack

Array implementation of Stack

Linked Implementation of Stack

Queue

Array implementation of Queue

Linked Implementation of Queue

A mathematical and logical model of data is known as Data Structure .   Primitive data structure : The data structure, which is available in the compiler, is known as a primitive data structure . Non-primitive data structure : The data structure, which is not available in the compiler, is known as non-primitive data structure .   DATA STRUCTURE: INTRODUCTION

  Linear Data Structure : The data structure in which each element has access to maximum of one predecessor element and maximum of one successor element is known as linear data structure . Example: Stack, Queue, etc . Non-linear Data Structure : The data structure in which each element can access any number of predecessor elements and any number of successor elements is known as Non-linear data structure . Example: Tree, Graphs, etc .   DATA STRUCTURE: INTRODUCTION

Static Data Structure: The data structure in which the number of elements is fixed, is known as Static Data Structure . Example: Arrays Dynamic Data Structure: The data structure in which the number of elements is not fixed, is known as Dynamic Data Structure . Example: Linked List. TYPES OF DATA STRUCTURE

It is a static data structure . It is a homogeneous collection of data. The elements in the array are stored on consecutive memory locations. Array is also known as a subscripted variable, e.g., A[i] is i th element of the array A. ARRAY

STACK It is a non-primitive linear data structure in which insertion and deletion of elements takes place from only one end , known as top. It is a non-primitive linear data structure in which insertion and deletion of elements takes place from two opposite ends rear and front respectively. QUEUE

STACKS Stacks is LIFO (Last In First Out) structure and physically can be implemented as an array or as a linked list. Stack, when implemented as an array is functionally same as any other array except that here, adding an element and deletion is done from the same direction just like a pile of books.

STACK Inserting an element in an array is known as PUSH . Deleting an element from an array is known as POP . Implementation of STACK in computers When functions are called. To convert a infix expression to postfix. To evaluate a postfix expression.

When functions are called.

To convert a infix expression to postfix.

To evaluate a postfix expression.

STACK A stack is a list in which insertion and deletion takes place only at one end called top. Thus, called LIFO. Representation of STACK Each one of the above has one open and one close end and data movement takes place from open end . data4 TOP data3 data2 data1 data2 data1 data3 data4 TOP TOP data4 data3 data2 data1 data1 data2 data3 data4 TOP

Basic operation and implementation of stacks Creation of stack Check for empty stack Check for full stack Add element in stack Delete element in stack Print stack

Creation of stack

Check for empty stack

Check for full stack

Add element in stack

Delete element in stack

Print stack

STACKS The fundamental operations that can be performed on stack are PUSH and POP . When element is added on the stack top is called PUSH . And When Data is removed from the stack top, the operation is called POP.

STACK The stack operation can be explained as follows: Stack operation Content of array Push(a) a Push(b) ba Push( c) cba Pop() ba Pop() a Push (a) a b a Push(b) b a C Push( c) b a Pop( c) a Pop(b)

STACKS A stack is a list, any list implementation can be used to implement stack. We can implement stack by the following data structures: Array called Linear Stack Linked List called Linked Stack

A stack is a list, any list implementation can be used to implement stack.

We can implement stack by the following data structures:

Array called Linear Stack

Linked List called Linked Stack

Linear Stack int S[5]; When PUSH is selected, TOP is incremented, And data is added at that subscript location When POP is selected, TOP is decremented, And data is removed from that subscript location Stack array int TOP; To hold address of location where data is inserted or deleted

Lets see working of Linear Stack Push 7 Push 20 Push 14 OVERFLOW ARRAY IS FULL TOP TOP TOP Top is incremented TOP++ 10 9 8 10 9 8 7 10 9 8 7 20

OVERFLOW

ARRAY IS FULL

CONTINUED…. Pop 20 Pop 7 UNDERFLOW OCCURS WHEN STACK IS EMPTY TOP Top Top TOP is decremented TOP -- 10 9 8 7 20 10 9 8 7 10 9 8

UNDERFLOW OCCURS WHEN STACK IS EMPTY

Lets see this using a program Program Code for the Same is Click here to execute program Click here to see program code

A variable which holds an address of a memory location of another variable is known as a Pointer Variable (or only pointer). Example int amt, *p; amt Requires 2 bytes 0x8ffebab4 *P Requires 2 bytes Pointer P holds address of amt POINTER     900     0x8ffebab4

NEW operator in C++ returns the address of a block of unallocated bytes (depending on data type a pointer pointing to). DELETE operator in C++ reverses the process of new operator, by releasing the memory location from a pointer. It de allocates memory assigned by NEW. DYNAMIC ALLOCATION

A pointer, which stores the address of struct type data, is known as Pointer to structure. struct abc { int X,Y; }; struct *g=new abc; Holds address of dynamic object of struct abc   G   0x8ff134ab G->X 0x8ff134ab G->X G->Y LINK LIST To allocate dynamic allocation and store address in point g    

struct STACK // structure for stack { int data; STACK *link; }; struct *TOP; LINK STACK To hold address of First node of the list TOP pointer to holds address of dynamic objects of link stack. As we push a node TOP element get shifted and new node becomes first node. LIFO implementation every new node becomes first node. When we pop Top node is deleted and next node becomes first node.

Lets see working of Linked stack * TOP * Temp NULL 0x8ffab2e6 A new memory is allocated and address is stored in temp X NULL data link 0x8ffab2e6 Top = Temp Top will hold address of new location * TOP 0x8ffab2e6 Thus, TOP will have this address. Push operation Initially top is assigned NULL Temp holds address of new location

Cont….. *TOP * Temp 0x8ffab2e6 0x8ffab2e8 Another new memory is allocated to an object Y data link 0x8ffab2e8 * TOP 0x8ffab2e8 X NULL data link 0x8ffab2e6 temp-> link = Top Top=temp 0x8ffab2e6 Now TOP is TOP will get shifted Y becomes first node X becomes second node

Cont….. * TOP * Temp 0x8ffab2e8 0x8ffab2e8 An object is deleted from top Y data link 0x8ffab2e8 Thus Top will be * TOP 0x8ffab2e6 X NULL data link Temp=TOP TOP=TOP->link 0x8ffab2e6 delete temp (to release memory) 0x8ffab2e6 TOP will get shifted X becomes first node Y will be released POP operation

Lets see this using a program Program Code for the Same is Click here to execute program Click here to see program code

Queues Queue is FIFO (First In First Out) structure and physically can be implemented as an array or as a linked list. Queue , when implemented as an array is functionally same as any other array except that here, adding an element and deletion is done from the one direction and deletion from other just like any queue of peoples.

Queue is FIFO (First In First Out) structure and physically can be implemented as an array or as a linked list.

Queues Inserting an element in an array is known as insert. Deleting an element from an array is known as delete But this is done with the help of two parameters rear and front. Implementation of queue in computers When program is executed.

Inserting an element in an array is known as insert.

Deleting an element from an array is known as delete

But this is done with the help of two parameters rear and front.

When program is executed.

Queue A Queue is a data structure in which insertion is done at the end and deletion is done from the front of queue. It is FIFO . Representation of Queue Each one of the above has two open end Front and Rear. Insertion is done from Rear and deletion form Front Rear Front Front Rear Front Rear Front Rear data4 data3 data2 data2 data3 data4 data4 data3 data2 data2 data3 data4

Basic operation and implementation of QUEUE Creation of Queue Check for empty Queue Check for full Queue Add element in Queue Delete element in Queue Print Queue

Creation of Queue

Check for empty Queue

Check for full Queue

Add element in Queue

Delete element in Queue

Print Queue

QUEUE The fundamental operations that can be performed on Queue are Insert and Delete . When element is added on the Queue Front is called Insert . And When Data is removed from the Queue Rear, the operation is called Delete.

QUEUE The Queue operation can be explained as follows: Queue operation Content of array Insert(a) Front=0 Rear=0 Insert(b) Front=0 Rear=1 Insert( c) Front=0 Rear=2 Delete() Front=1 Rear=2 Delete() Front=2 Rear=2 If we try to insert Overflow occurs Though first two cells are empty a b a c b a c b c

Linear Queue int Q[5]; When INSERT is selected, Rear is incremented, And data is added at that subscript location When DELETE is selected, Front is decremented, And data is removed from that subscript location Queue array int Front, Rear; To hold address of location where data is inserted or deleted

QUEUE A Queue is a list, any list implementation can be used to implement Queue. We can implement Queue by the following data structures: Array called Linear Queue Linked List called Linked Queue

A Queue is a list, any list implementation can be used to implement Queue.

We can implement Queue by the following data structures:

Array called Linear Queue

Linked List called Linked Queue

Lets see working of LINEAR QUEUE Insert 7 Insert 20 Insert 14 OVERFLOW QUEUE is full Front rear rear rear Front Front Rear is incremented Rear++ 10 9 8 10 9 8 7 10 9 8 7 20

Lets see working of Queue as an array Delete Delete Underflow occurs when QUEUE is empty Rear Front Rear Rear Front Front Front is incremented Front++ 10 9 8 7 20 9 8 7 20 8 7 20

Lets see this using a program Program Code for the Same is Click here to execute program Click here to see program code

struct QUEUE // structure for QUEU { int data; QUEUE *link; }; struct *Front,*Rear; LINKED QUEUE To hold address of First and Last node of the list Front and Rear pointer to holds address of dynamic objects of link stack. As we insert a node Rear element get shifted and new node becomes next node. FIFO implementation every new node added at end. When we Delete Front node is deleted and next node becomes first node.

Lets see working of Linked Queue * Front * Rear * Temp NULL NULL 0x8ffab2e6 A new memory is allocated and address is stored in temp X NULL data link 0x8ffab2e6 Front=Rear = Temp Front and Rear will hold address of First location * Front * Rear 0x8ffab2e6 0x8ffab2e6 Thus, Front and Rear will have this address . Insert operation Initially Front and Rear is assigned NULL Temp holds address of new location

Cont….. *Front * Rear * Temp 0x8ffab2e6 0x8ffab2e6 0x8ffab2e8 Another new memory is allocated to an object X data link 0x8ffab2e6 * Rear 0x8ffab2e8 Y NULL data link 0x8ffab2e8 temp-> link = Rear Rear=temp 0x8ffab2e8 Now Rear is Rear will get shifted Y becomes Last node

Cont….. * Front * Rear * Temp 0x8ffab2e6 0x8ffab2e8 0x8ffab2e6 An object is deleted from Front X data link 0x8ffab2e6 Thus Front will be * Front 0x8ffab2e8 Y NULL data link Temp=Front Front=Front->link 0x8ffab2e8 delete temp (to release memory) 0x8ffab2e8 Front will get shifted Y becomes first node X will be released Delete operation

Lets see this using a program Program Code for the Same is Click here to execute program Click here to see program code

CIRCULAR QUEUE The fundamental operations that can be performed on Circular Queue are Insert and Delete . When overflow occurs though the free cells are available, Rear reaches ends Circular Queue is implemented to avoid this drawback. In Circular Queue as soon as Rear reaches maximum it should reset to 0.

QUEUE The Queue operation can be explained as follows: Queue operation Content of array Insert(a) Front=0 Rear=0 Insert(b) Front=0 Rear=1 Insert( c) Front=0 Rear=2 Delete() Front=1 Rear=2 Insert (d) Front=2 Rear=0 Overflow occurs only when Array is FULL. Rear moves to 0 if array is empty a b a c b a c b c d

Lets see this using a program Program Code for the Same is Click here to execute program Click here to see program code

Do you have any QUESTIONS ?

TEST YOUR KNOWLEDGE What is difference between Stack & Queue? What is Dynamic Allocation? What is the significance of Top? What is the significance of Front & Rear? What is Overflow? What is Underflow? Where Stack is Implemented?

What is difference between Stack & Queue?

What is Dynamic Allocation?

What is the significance of Top?

What is the significance of Front & Rear?

What is Overflow?

What is Underflow?

Where Stack is Implemented?

THANKS NITI ARORA FROM

Add a comment

Related presentations

Related pages

Encoding C++: August 2009

Stacks & Queues By Ms. Niti Arora. View more presentations from kulachihansraj. Posted by NIti Arora at 12:45 AM ...
Read more

Stacks and Queues - Carnegie Mellon School of Computer Science

Stacks and Queues. An array is a random ... The difference between stacks and queues is in removing. In a stack we remove the item the most recently added ...
Read more

Microsoft Web Platform - Composition of the Platform

Web Platform Installer The Server The ... Microsoft's enterprise web solutions are in a unique position to address the most diverse and ...
Read more

Microsoft Azure Stack application deployment - YouTube

... visit http://www.microsoft.com/azure ... Queue Queue. Watch ... __count__/__total__ Find out why Close. Microsoft Azure Stack application ...
Read more

Priority Queues - YouTube

This video discusses basics of priority queues
Read more

Interacting with Message Queues

The MessageQueue class is the primary object for interacting with message queues on local or ... a Message Queues node in the Microsoft® Visual ...
Read more

Message Queuing (MSMQ)

Message Queuing (MSMQ) ... Applications send messages to queues and read messages from queues. ... Microsoft® Visual Basic®, ...
Read more