Role of Stacks and Queues in Problem Solving

Stacks

A Stack is a linear data structure which follows the LIFO or Last-In-First-Out principle. It basically means that the last element which will be inserted in the stack will be the very first one to leave the stack. Stack contains only a single pointer i.e. the top pointer which points to the very top most element of the following stack. Whenever an element is added in the stack, it is added from the top of the stack, and that element can also be deleted only from the very top of the stack. We can also say that a stack can be defined as a bucket in which the processes of insertion and deletion can only be done from the one end which is commonly known as top of the stack.

Standard Stack Operations

Some very common operations which are implemented on the stack are:

• push(): Whenever we add an element in the stack then the operation is known as push operation. If the stack is already full and we try to add an element then the stack overflow occurs.

• pop(): When we delete an element from stack, the operation is known as pop. If the stack is already empty and we try to delete an element, stack underflow occurs.

• isEmpty(): The isEmpty() function is used to check or detemine whether the stack is empty or not.

• isFull(): The isFull() function is used to check or determine whether the stack is full or not.

• peek(): The peek() function is used to return the element at the given position.

• count(): The count() function returns the total number of elements available in the stack.

In a stack of items, items will be like one on top of the other, and we can remove them from the very top only.
The best property of a stack is that we do not need to maintain a table which will contain a record of each and every section of the allocated memory; the only information we need is a single pointer at the top of the stack. To allocate and deallocate, we just have to increment and decrement that top pointer.

Applications of Stacks:

Some of the stack applications include:

1. Infix to Postfix Conversion
2. Parenthesis Matching
3. Many locations, such as editors and photoshop, need redo/undo options provided by stacks.
4. Forward and Backward feature in web browsers.

1. Infix to Postfix Conversion

Infix Expression:

An expression that follows the scheme of <operand><operator><operand> is known as an infix expression. e.g. A + B * C, (A + B) * (C + D), A * B + C * D, etc.

Postfix Expression:

An expression that follows the scheme of <operand><operand><operator> is known as an infix expression. e.g. A B C * +, A B + C D + *, A B * C D * +, etc.

Algorithm:

1. From left-side to right-side, scan the infix expression.
2. If an operand is found, output it.
3. If an operator is found and the precedence of the scanned operator is greater than the precedence of the operator in the stack, push it into the stack. 
4. Otherwise, pop all the operators from the stack that are larger than or equal to the scanned operator in precedence. After that, push the scanned operator into the stack. 
5. If a '(' appears, push it into the stack.
6. If a ‘)’ is encountered, pop the stack and output it until a ‘(‘ is encountered, and discard both the parenthesis.
7. Repeat the steps 2-6 until the whole infix expression is scanned.
8. Print the output.
9. Stacks should be popped and outputted till they are not empty.

Code:

The first step is to create our Stack ADT.

Then, we need to create a createStack() function. It will take the size of the stack as the input.

The isEmpty() function will return 1 if the stack is empty, otherwise it will return 0.

The isFull() function will return 1 if the stack is full, otherwise it will return 0.

The peek() function returns the element at the top of the stack.

If the stack is empty and we try to pop an element, stack underflow occurs. Else, it pops and returns the topmost element from the stack.

If the stack is full and we try to push an element, stack overflow occurs. Else, we increment the top of the stack and push the element into the stack.

If the character encountered is an operand, the isOperand() function will return 1, else it will return 0.

The precedence() function returns 3 if the character encountered is '^', 2 for '*' or '/' and 1 for '+' or '-'. 

Now, we have to create our infixToPostfix() function. Inside this function, we have declared two variables i and k. We have declared an array 'exp' of size 100. We then take the infix expression as an input from the user and store it in exp. Then we create a new stack using the createStack() function.

Then we initialize a 'for' loop and inside that we run an if-else-if ladder.

Now, we pop everything from the stack until the stack gets empty. We then append '/0' to the end of the expression indicating the end of the string. Then, we print the postfix expression.

We have to call the infixToPostfix() function inside the main() function.

Output:

Queues

Queue is the linear data structure which follows the FIFO i.e. First In First Out pattern. It basically means that the first element which will be added will be the first one to leave the queue .Unlike stacks which is open at only one end, a queue is open at both its ends. One end of the queue is always used to add data (enqueue) and the other end is used to delete the data (dequeue). 

Standard Queue Operations

Some common operations implemented on the Queue are:

• enqueue(): It is used to add or insert an item to the queue.

• dequeue(): It is used to remove or delete an item from the queue.

• peek(): It returns the element at the front of the queue without removing the element.

• isFull(): It checks if the queue is already full or not.

• isEmpty(): It checks if the queue is already empty or not.

Applications of Queues:

1. CPU Scheduling, Disk Scheduling
2. Breadth First Search

Algorithm:

First Come First Serve CPU Scheduling:

The simplest scheduling algorithm, which schedules processes according to their arrival times. According to the first-come, first-serve scheduling strategy, the process that asks the CPU first gets allocated the CPU first. The FIFO queue is used to implement it. When a process is added to the ready queue, its PCB is linked to the queue's tail. When the CPU becomes available, it is given to the process at the front of the queue. After that, the currently executing process is removed from the queue. FCFS is a scheduling algorithm that is not preemptive.

Round Robin Scheduling:

The Round Robin scheduling method is one of the most widely used scheduling algorithms, and it can be found in almost all operating systems. The Time Sharing  is the main emphasis of the algorithm. Every process in this algorithm is carried out in a cyclic manner. In the system, a time quantum is defined as a specific time slice. Each process in the ready queue is given a CPU for that time quantum; if the process's execution is completed within that time, the process will be terminated; otherwise, the process will return to the ready queue and wait for the next turn to complete the execution.

References:

1. https://zaid23.medium.com/role-of-stacks-and-queues-in-problem-solving-989d7d68f0d6
2. https://pshenavi2.medium.com/role-of-stacks-and-queues-in-problem-solving-a5bbc22305d9
   
3. https://role-of-stackandqueueinproblemsolving.blogspot.com/?m=1
   
4. https://www.geeksforgeeks.org/stack-set-2-infix-to-postfix/
   
5. https://www.geeksforgeeks.org/difference-between-stack-and-queue-data-structures/