1 of 72

Stack and Queues�

By

Mr. Abhijit T. Somnathe

2 of 72

Data Structure

3 of 72

What is Linear Data Structure?

  • In linear data structure, data is arranged in linear sequence.
  • Data items can be traversed in a single run.
  • In linear data structure elements are accessed or placed in contiguous (next to each other) memory location.

4 of 72

What is STACK?

  • A stack is called a last-in-first-out (LIFO) collection. This means that the last thing we added (pushed) is the first thing that gets pulled (popped) off.
  • A stack is a sequence of items that are accessible at only one end of the sequence.

5 of 72

Examples of STACK?

6 of 72

Basic Stack Operations

​

  • PUSH

​

​

  • POP

7 of 72

Basic Stack Operations

  • PUSH : It is used to insert items into the stack.
  • POP: It is used to delete items from stack.
  • PEEK/TOP : Peek operation allows the user to see the element on the top of the stack. The stack is not modified in any manner in this operation.

​

8 of 72

Applications of Stack

  • Redo-undo features at many places like editors, Photoshop.
  • Forward and backward feature in web browsers.
  • Evaluating arithmetic expressions like INFIX notation [A+B], PREFIX notation [+AB], POSTFIX notation [AB+].
  • In Memory management any modern computer uses stack as the primary-management for a running String reversal.

9 of 72

Array Implementation

  • An array is one of the simplest containers offering random access to users based on indexes.
  • We can't access any element of the stack at any given time.
  • That’s why we need to set an index as top and then access only the element at index top.

int stack[10]

int top = -1

10 of 72

Array Implementation

  • Here, 10 is a pre-defined capacity of the stack. We can throw a stack overflow error if a user tries to exceed this capacity.
  • The default value for the top is -1, denoting that the stack is empty.
  • We may need to store the capacity of the stack but we don’t need to store the current size. We can know the current size of stack by looking at the value of the top.

11 of 72

Array Implementation

  • Let us wrap this group of data members in a class.

class Stack

{

int arr[]

int capacity

int top

}

12 of 72

Array Implementation

  • Let us also create a constructor which initializes capacity and top.

Stack(int cap)

{

capacity = cap

top = -1

}

  • Now, we need to implement the operations that we generally perform on stacks.

13 of 72

PUSH Operation

What changes are made to the stack when a new element is pushed?

  • A new element is inserted on top.
  • The value of top increases by 1.

​

14 of 72

PUSH Operation

What if the stack is filled to its capacity?

  • We shall check if the stack if full before inserting a new element and throw an error if it is.

15 of 72

PUSH Operation

  • Now, let us implement this simply.

void push(int item)

{

if ( top == capacity - 1 )

print( "Stack overflow!" )

else

{

arr[top+1] = item

top = top + 1

}

}

16 of 72

POP Operation

What changes are made to the stack internally for a pop operation?

  • The top element is removed.
  • The value of top is decreased by 1.

​

17 of 72

POP Operation

  • Let’s try implementing it now

void pop()

{

if ( isEmpty() == True )

print( "Stack is empty!" )

else

top = top - 1

}

18 of 72

Balanced parentheses using Stack

  • One of the most important applications of stacks is to check if the parentheses are balanced in a given expression.

​

  • The compiler generates an error if the parentheses are not matched.

19 of 72

Balanced parentheses using Stack

  • Here are some of the balanced and unbalanced expressions:

​

20 of 72

Balanced parentheses using Stack

  • Consider the above mentioned unbalanced expressions:
  • The first expression ( a + b is unbalanced as there is no closing parenthesis given.
  • The second expression [ ( c - d * e ] is unbalanced as the closed round parenthesis is not given.
  • The third expression { [ ( ] ) } is unbalanced as the nesting of square parenthesis and the round parenthesis are incorrect.

21 of 72

Balanced parentheses using Stack

  • Steps to find whether a given expression is balanced or unbalanced.
  • Input the expression and put it in a character stack.
  • Scan the characters from the expression one by one.
  • If the scanned character is a starting bracket ( ‘ ( ‘ or ‘ { ‘ or ‘ [ ‘), then push it to the stack.

22 of 72

Balanced parentheses using Stack

  • Steps to find whether a given expression is balanced or unbalanced.
  • If the scanned character is a closing bracket ( ‘ ) ’ or ‘ } ’ or ‘ ] ’ ), then pop from the stack and if the popped character is the equivalent starting bracket, then proceed. Else, the expression is unbalanced.
  • After scanning all the characters from the expression, if there is any parenthesis found in the stack or if the stack is not empty, then the expression is unbalanced.

23 of 72

Infix to Postfix Conversion

  • Infix expressions are readable and solvable by humans.
  • We can easily distinguish the order of operators, and also can use the parenthesis to solve that part first during solving mathematical expressions.
  • The computer cannot differentiate the operators and parenthesis easily, that’s why postfix conversion is needed.

24 of 72

Infix to Postfix Conversion

  • To convert infix expression to postfix expression, we will use the stack data structure.
  • By scanning the infix expression from left to right, when we will get any operand, simply add them to the postfix form, and for the operator and parenthesis, add them in the stack maintaining the precedence of them.

25 of 72

Infix to Postfix Conversion

26 of 72

Infix to Postfix Conversion

  • Converting 2+(4-1)*3 into 241-3*+

​

Current Symbol

Action Performed

Stack Status

Postfix Expression

2

PUSH C

C

2

2

​

​

2

+

PUSH +

(+

2

(

PUSH (

(+(

24

4

​

​

24

-

PUSH -

(+(-

241

1

POP

​

241-

27 of 72

Infix to Postfix Conversion

  • Converting 2+(4-1)*3 into 241-3*+

​

Current Symbol

Action Performed

Stack Status

Postfix Expression

)

​

(+

241-

*

PUSH *

(+*

241-

3

​

​

241-3

​

POP *

​

241-3*

​

POP +

​

241-3*+

)

​

​

​

28 of 72

Postfix Expression Evaluation

  • A postfix expression is a collection of operators and operands in which the operator is placed after the operands. That means, in a postfix expression the operator follows the operands.
  • Postfix Expression has following general structure.

​

29 of 72

Postfix Expression Evaluation

  • A postfix expression can be evaluated using the Stack data structure. To evaluate a postfix expression using Stack data structure we can use the following steps.
  • Read all the symbols one by one from left to right in the given Postfix Expression.
  • If the reading symbol is operand, then push it on to the Stack.

​

30 of 72

Postfix Expression Evaluation

  • If the reading symbol is operator (+ , - , * , / etc.,), then perform TWO pop operations and store the two popped oparands in two different variables (operand1 and operand2). Then perform reading symbol operation using operand1 and operand2 and push result back on to the Stack.
  • Finally! perform a pop operation and display the popped value as final result.

31 of 72

Postfix Expression Evaluation

  • Consider the following Expression
  • Infix Expression: (5+3)*(8-2)
  • Postfix Expression: 5 3 + 8 2 - *
  • Above Expression can be evaluated by using Stack Data Structure as follows.

​

32 of 72

Postfix Expression Evaluation

​

​

Reading Symbol

Stack Operation

Evaluated Part of Expression

Initial

Stack is Empty

Nothing

5

Push (5)

Nothing

3

Push (3)

Nothing

+

Value1 = pop()

Value2 = pop()

Result = Value2+Value1

Push(Result)

Value1 = pop(); //3

Value2 = pop(); //5

Result = 5+3; //8

Push(8)

8

Push(8)

(5+3)

2

Push(2)

(5+3)

33 of 72

Postfix Expression Evaluation

​

​

​

​

​

​

​

  • Infix Expression: (5+3) * (8-2) = 48.
  • Postfix Expression: 5 3 + 8 2 - * value is 48.

​

Reading Symbol

Stack Operation

Evaluated Part of Expression

-

Value1 = pop()

Value2 = pop()

Result = Value2 – Value1

Push(Result)

Value1 = pop(); //2

Value2 = pop(); //8

Result = 8 – 2; //6

Push(6)

*

Value1 = pop()

Value2 = pop()

Result = Value2 * Value1

Push(Result)

Value1 = pop();//6

Value2 = pop(); //8

Result = 8*6; //48

Push(48)

$

End of Expression

Result = pop()

Display Result

48

As Final Result

34 of 72

Queue

  • Queue is an Abstract Data Type (ADT) of data structure similar to stack, except that the first item to be inserted is the first one to be removed.
  • This mechanism is called First-In-First-Out (FIFO).
  • Placing an item in a queue is called “insertion or enqueue”, which is done at the end of the queue called “rear”.

35 of 72

Queue

  • Removing an item from a queue is called “deletion or dequeue”, which is done at the other end of the queue called “front”.
  • Some of the applications are : printer queue, keystroke queue, etc.

​

36 of 72

Operations on Queue

  • Queue operations may involve initializing or defining the queue, utilizing it, and then completely erasing it from the memory.
  • Here we shall try to understand the basic operations associated with queues.
  • enqueue() − add (store) an item to the queue.
  • dequeue() − remove (access) an item from the queue.

37 of 72

Operations on Queue

  • Few more functions are required to make the queue operation efficient. They are
  • peek() − Gets the element at the front of the queue without removing it.
  • isfull() − Checks if the queue is full.
  • isempty() − Checks if the queue is empty.
  • In queue, we always dequeue (or access) data, pointed by front pointer and while enqueing (or storing) data in the queue we take help of rear pointer.

38 of 72

Operations on Queue

  • Let's first learn about supportive functions of a queue,
  • peek()
  • This function helps to see the data at the front of the queue.

39 of 72

Operations on Queue

  • isfull()
  • As we are using single dimension array to implement queue, we just check for the rear pointer to reach at MAXSIZE to determine that the queue is full.
  • isempty()
  • If the value of front is less than MIN or 0, it tells that the queue is not yet initialized, hence empty.

40 of 72

Enqueue Operation

  • Queues maintain two data pointers, front and rear. Therefore, its operations are comparatively difficult to implement than that of stacks.
  • The following steps should be taken to enqueue (insert) data into a queue,
  • Step 1 − Check if the queue is full.
  • Step 2 − If the queue is full, produce overflow error and exit.

​

41 of 72

Enqueue Operation

  • Step 3 − If the queue is not full, increment rear pointer to point the next empty space.
  • Step 4 − Add data element to the queue location, where the rear is pointing.
  • Step 5 − return success.
  • Sometimes, we also check to see if a queue is initialized or not, to handle any unforeseen situations.

​

42 of 72

Enqueue Operation

43 of 72

Dequeue Operation

  • Accessing data from the 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 the queue is empty.
  • Step 2 − If the queue is empty, produce underflow error and exit.

44 of 72

Dequeue Operation

  • Step 3 − If the queue is not empty, access the data where front is pointing.
  • Step 4 − Increment front pointer to point to the next available data element.
  • Step 5 − Return success.

45 of 72

Dequeue Operation

46 of 72

Types of Queue

  • Following are the types of queue
  • Simple Queue
  • Circular Queue
  • Priority Queue
  • Double Ended Queue

​

47 of 72

Simple Queue

  • A simple queue is the most basic queue.
  • In this queue, the enqueue operation takes place at the rear, while the dequeue operation takes place at the front.
  • Its applications are process scheduling, disk scheduling, memory management, IO buffer, pipes, call center phone systems, and interrupt handling.

48 of 72

Simple Queue

49 of 72

Circular Queue

  • A circular queue permits better memory utilization than a simple queue when the queue has a fixed size.
  • In this queue, the last node points to the first node and creates a circular connection.
  • Thus, it allows us to insert an item at the first node of the queue when the last node is full and the first node is free.

50 of 72

Circular Queue

  • It’s also called a ring buffer.
  • It’s used to switch on and off the lights of the traffic signal systems.
  • Apart from that, it can be also used in place of a simple queue in all the applications mentioned above.

​

​

51 of 72

Priority Queue

  • A priority queue is a special kind of queue in which each item has a predefined priority of service.
  • In this queue, the enqueue operation takes place at the rear in the order of arrival of the items, while the dequeue operation takes place at the front based on the priority of the items.
  • That is to say that an item with a high priority will be dequeued before an item with a low priority.

52 of 72

Priority Queue

  • In the case, when two or more items have the same priority, then they’ll be dequeued in the order of their arrival.
  • Hence, it may or may not strictly follow the FIFO rule.

​

53 of 72

Double-Ended Queue (Deque)

  • A deque is also a special type of queue.
  • In this queue, the enqueue and dequeue operations take place at both front and rear.
  • That means, we can insert an item at both the ends and can remove an item from both the ends.
  • Thus, it may or may not adhere to the FIFO order.

​

54 of 72

Double-Ended Queue (Deque)

​

​

​

​

  • It’s used to save browsing history, perform undo operations, implement A-Steal job scheduling algorithm, or implement a stack or implement a simple queue.

​

​

55 of 72

Double-Ended Queue (Deque)

  • Further, it has two special cases:
  • Input-Restricted deque, and
  • Output-Restricted deque.
  • In the first case, the enqueue operation takes place only at the rear, but the dequeue operation takes place at both rear and front.

56 of 72

Double-Ended Queue (Deque)

  • An input-restricted queue is useful when we need to remove an item from the rear of the queue.

​

57 of 72

Double-Ended Queue (Deque)

  • In the second case, the enqueue operation takes place at both rear and front, but the dequeue operation takes place only at the front. An output-restricted queue is handy when we need to insert an item at the front of the queue.

​

58 of 72

Round Robin Algorithm

  • The name of this algorithm comes from the round-robin principle, where each person gets an equal share of something in turns. It is the oldest, simplest scheduling algorithm, which is mostly used for multitasking.

​

  • In Round-robin scheduling, each ready task runs turn by turn only in a cyclic queue for a limited time slice. This algorithm also offers starvation free execution of processes.

59 of 72

Characteristics of Round-Robin

  • Round robin is a pre-emptive algorithm
  • The CPU is shifted to the next process after fixed interval time, which is called time quantum/time slice.
  • The process that is preempted is added to the end of the queue.
  • Round robin is a hybrid model which is clock-driven.

60 of 72

Characteristics of Round-Robin

  • Time slice should be minimum, which is assigned for a specific task that needs to be processed.
  • It is a real time algorithm which responds to the event within a specific time limit.
  • Round robin is one of the oldest, fairest, and easiest algorithm.
  • Widely used scheduling method in traditional OS.

61 of 72

Round Robin Algorithm

  • Consider this following three processes.

​

Process Queue

Burst Time

P1

4

P2

3

P3

5

62 of 72

Round Robin Algorithm

  • Step 1: The execution begins with process P1, which has burst time 4. Here, every process executes for 2 seconds. P2 and P3 are still in the waiting queue.

​

63 of 72

Round Robin Algorithm

  • Step 2: At time =2, P1 is added to the end of the Queue and P2 starts executing.

​

64 of 72

Round Robin Algorithm

  • Step 3: At time=4 , P2 is preempted and add at the end of the queue. P3 starts executing.

​

​

65 of 72

Round Robin Algorithm

  • Step 4: At time=6 , P3 is preempted and add at the end of the queue. P1 starts executing.

​

​

66 of 72

Round Robin Algorithm

  • Step 5: At time=8 , P1 has a burst time of 4. It has completed execution. P2 starts execution.

​

​

67 of 72

Round Robin Algorithm

  • Step 6: P2 has a burst time of 3. It has already executed for 2 interval. At time=9, P2 completes execution. Then, P3 starts execution till it completes.

​

​

68 of 72

Advantages of Round-Robin

  • It doesn't face the issues of starvation or convoy effect.
  • All the jobs get a fair allocation of CPU.
  • It deals with all process without any priority
  • If you know the total number of processes on the run queue, then you can also assume the worst-case response time for the same process.
  • This scheduling method does not depend upon burst time. That's why it is easily implementable on the system.

​

69 of 72

Advantages of Round-Robin

  • Once a process is executed for a specific set of the period, the process is preempted, and another process executes for that given time period.
  • Allows OS to use the Context switching method to save states of preempted processes.
  • It gives the best performance in terms of average response time.

​

70 of 72

Disadvantages of Round-Robin

  • If slicing time of OS is low, the processor output will be reduced.
  • This method spends more time on context switching
  • Its performance heavily depends on time quantum.
  • Priorities cannot be set for the processes.
  • Round-robin scheduling doesn't give special priority to more important tasks.

71 of 72

Disadvantages of Round-Robin

  • Decreases comprehension
  • Lower time quantum results in higher the context switching overhead in the system.
  • Finding a correct time quantum is a quite difficult task in this system.

72 of 72

ANY DOUBTS?