SUBJECT : DATA STRUCTURE UNIT : 3 STACK AND QUEUE
This content provides an introduction to the fundamental concepts of stacks and queues in data structures. It covers the definition of a stack, basic operations like push and pop, and algorithms for stack operations. The information is presented in a concise and structured format, making it suitable for students and professionals seeking to enhance their understanding of data structures.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
SUBJECT : DATA STRUCTURE UNIT : 3 STACK AND QUEUE IIMTU, SOCSA RUCHI BHATNAGAR(ASSISTANT PROFESSOR) IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
UNIT 3: STACK IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
INTRODUCTION 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. DEFINITION A stack is a basic data structure that can be logically thought of as a linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack. IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
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. IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
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. IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
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 IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
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 de allocates memory space. 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. IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
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 IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
IMPLEMENTATION OF STACK USING ARRAYS #include <stdio.h> #include <stdlib.h> #define MAX 10 int STACK[MAX],TOP; void display(int []); void PUSH(int [],int); void POP (int []); void main() { int ITEM=0; int choice=0; TOP=-1; while(1) { /*clrscr();*/ printf("Enter Choice (1: display, 2: insert (PUSH), 3: remove(POP)), 4: Exit..:"); scanf("%d",&choice); switch(choice) { case 1: display(STACK); break; case 2: printf("Enter Item to be insert :"); scanf("%d",&ITEM); PUSH(STACK,ITEM); break; case 3: POP(STACK); break; case 4: exit(0); default: printf("\nInvalid choice."); break; } getch(); } end of while(1) } IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
/* function : display(), to display stack elements. */ void display(int stack[]) { int i=0; if(TOP==-1) { printf("Stack is Empty .\n"); return; } printf("%d <-- TOP ",stack[TOP]); for(i=TOP-1;i >=0;i--) { printf("\n%d",stack[i]); } printf("\n\n"); } function : PUSH(), void PUSH(int stack[],int item) { if(TOP==MAX-1) { printf("\nSTACK is FULL CAN't ADD ITEM\n"); return; } TOP++; stack[TOP]=item; } function : POP(), void POP(int stack[]) { int deletedItem; if(TOP==-1) { printf("STACK is EMPTY.\n"); return; } deletedItem=stack[TOP]; TOP--; printf("%d deleted successfully\n",deletedItem); return; } IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
DATA STRUCTUTRE : QUEUE IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
DEFINITION: Queue is an abstract data structure, somewhat similar to stack. In contrast opened at both end. One end is always used to insert data(enqueue) and the remove(dequeue) data. Queue follows First-In-First- Out methodology, i.e., the data item stored first will be accessed first. to stack, queue is other is used to IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
Queue Representation In queue, we access both ends for different reasons, a diagram given below tries to explain queue representation as data structure Same as stack, queue can also be implemented using Array, Linked-list, Pointer and Structures. For the sake of simplicity we shall implement queue using one-dimensional array. IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
Basic Operations Queue operations may involve initializing or defining the queue, utilizing it and then erasing it from memory. Here we shall try to understand basic operations associated with queues enqueue add store an item to the queue. dequeue remove access an item from the queue. Few more functions are required to make above mentioned queue operation efficient. These are peek get the element at front of the queue without removing it. isfull checks if queue is full. isempty checks if queue is empty. In queue, we always dequeue oraccess data, pointed by front pointer and while enqueing or storing data in queue we take help of rear pointer. IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
Enqueue (INSERTION) Operation As queue maintains two data pointers, front and rear, its operations are comparatively more difficult to implement than stack. The following steps should be taken to enqueue insert data into a queue Step 1 Check if queue is full. Step 2 If queue is full, produce overflow error and exit. Step 3 If queue is not full, increment rear pointer to point next empty space. Step 4 Add data element to the queue location, where rear is pointing. Step 5 return success. IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
Algorithm for enqueue operation procedure enqueue(data) STEP 1 : if queue is full return overflow endif STEP 2: rear rear + 1 STEP 3: queue[rear] data STEP4: return true end procedure IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
Dequeue Operation Accessing data from queue is a process of two tasks access the data where front is pointing and remove the data after access. The following steps are taken to perform dequeue operation Step 1 Check if queue is empty. Step 2 If queue is empty, produce underflow error and exit. Step 3 If queue is not empty, access data where front is pointing. Step 3 Increment front pointer to point next available data element. Step 5 return success. IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
Algorithm FOR DEQUEUE OPERATION procedure dequeue() SETP 1: STEP 2: STEP3: STEP4: end procedure if queue is empty return underflow end if data = queue[front] front front - 1 return true IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
REPRESENTATION OF INSERTION AND DELETION OPERATION IN QUEUE IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
DATA STRUCTUTRE : TYPES OF QUEUE IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
THERE ARE 3 TYPES OF QUEUE 1. CIRCULAR QUEUE 2. PRIORITY QUEUE 3. DEQUEUE IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
CIRCULAR QUEUE A circular queue is one in which the insertion of a element is done at the very first location if the last location of the queue is full. In other words, we can say that a Circular Queue is one in which the first element comes just after the last element. IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
CIRCULAR QUEUE Following are the assumption made: Front will always be pointing to the first element If front=rear the queue will be empty Each time a new element is inserted into the queue the rear is incremented by one rear=rear+1 Each time a new element is deleted from the queue the value of front is incremented by one, front=front+1 Example of Circular Queue: Consider a Queue of size 8. Initially the queue is empty. Perform following operations on queue. IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
PRIORITY QUEUE Priority queue is a collection of elements such that each element has been assigned a priority and the order in which elements are deleted and processed comes from following rules: An element of higher priority is processed before any elements of lower priority Two elements with the same priority are processed according to the order in which they were added to the queue. An example of priority queue in computer science occurs in timesharing system in which the processes of higher priority is executed before any process of lower priority. There are two types of priority queue: 1. Ascending priority queue : It is a collection of items in to which items can be inserted arbitrarily and from which only the smallest item can be removed. 2. Descending priority queue : It is similar but allows deletion of only the largest item. IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
Double Ended Queue ( Dequeue) It is also a homogeneous list of elements in which insertion and deletion operations are performed from both the ends. That is, we can insert elements from the rear end or from the front end. Hence, it is called Double-Ended Queue. There are two types of deques. These two types are due to the restrictions put to perform either the insertions or deletions only at one end. 1. Input restricted dequeue : Input restricted deques allows insertions at only one end of the array or list but deletions allows at both ends. 2. Output restricted dequeue : Output restricted deques allows deletions at only one end of the array or list but insertions allow at both ends. IIMTU, SOCSA RUCHI BHATNAGAR (ASSI. PROFF.)
