Role of Stack and Queue in Problem Solving.

Introduction to Stack and Queue:

Data Structures are tools which are used to store data in a structured way in a computer to use it efficiently. Efficient data structures play a vital role in designing good algorithms. Data structures are considered as key organizing factors in software design in some designing methods and programming languages. Examples: In English dictionaries, we can access any word easily as the data is stored in a sorted way using a particular data structure. Mastering data structures is non-negotiable. Efficient data structures help execute effective programs. Today, many programming roles require great knowledge of data structures. They are also a fundamental part of coding interviews.

Stacks and queues are linear data structures that follow a particular order to add or remove entities. In this article, you will be introduced to stacks and queues. We will highlight their uses, functionalities, and show you how to implement these data structures in Java.

What is a Stack?

In programming, a stack is an abstract, linear data type with a predefined capacity. It follows a particular order for adding or removing elements. Linear data structures organize their components in a straight line, so if we add or remove an element, they will grow or shrink respectively.

Let us conceptualize stacks using a stack of plates placed in a box. The first plate placed in the stack (the plate at the bottom of the stack) will be the last one to be removed, and the plate added last would be the first to be removed.

This is called the Last In First Out (LIFO) or First In Last Out (FILO) ordering.

Stacks are used in a variety of ways when we code. We use stacks to implement functions, parsers, expression evaluation, and some algorithms. Stacks are great for processing nested structures, so they are important for understanding recursion.

Insertion and deletion happen on the same end

A simple real-world application of a stack is reversing a string letter by letter. Another good example of a data stack is the undo and redo function on a computer or text editor. Undo removes your most recent change, and redo builds upon already existing changes.

How do Stacks work?

As an abstract entity, a stack is defined by the following operations-

• Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.
• Pop: Removes an item from the stack. The items are popped in the reversed order in which they are rushed. If the stack is empty, then it is said to be an Underflow condition.
• Peek or Top: Returns top element of stack.
• Is Empty: Returns true if stack is empty, else false.

This Abstract Data Type definition of a stack does not define how a stack is implemented in a computer program, it only defines the operations on a stack. In general, an Abstract Data Type (ADT) consists of a collection of data structures together with a set of operations defined on those data structures. We might be familiar with the structuring methods that C provides, like arrays, structs, and strings. To define an ADT, in addition to defining the basic data structures, we need to define a set of permissible operations on those data structures. In the case of stacks we need to define a structure (probably using struct)) to hold the data, as well as functions for manipulating the data, namely push(), pop() and two functions to check whether a stack is full() or empty().

There are many examples of stacks in everyday situations. Consider a stack of plates on a table, where it’s only possible to add or remove plates to or from the top. Or imagine a stack of books on a desk. The only book whose cover is visible is the one on top. To access the others, we must first remove the ones sitting on top of them.

An ADT for a stack may therefore look like:

A stack, S of type T is a sequence of items of type T on which the following operations are defined:

1. Initialize the stack S to be the empty stack
2. Determine whether or not the stack S is empty()
3. Determine whether or not the stack S is full()
4. push() a new item of type T onto the top of the stack, S
5. If S is not empty, pop() an item from the top of the stack, S.

Demonstration of Stack :

Infix to Postfix ( Expression Conversion Problem) :

The complex arithmetic operations can be converted into polish notation using stacks which then can be executed in two operands and an operator form.

Infix Expression :

It follows the scheme of <operand><operator><operand> i.e. an <operator> is preceded and succeeded by an <operand>. Such an expression is termed infix expression. E.g., A+B

Postfix Expression :

It follows the scheme of <operand><operand><operator> i.e. an <operator> is succeeded by both the <operand>. E.g., AB+

Algorithm :

Let, X is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix expression Y.

1. Push “(“onto Stack, and add “)” to the end of X.

2. Scan X from left to right and repeat Step 3 to 6 for each element of X until the Stack is empty.

3. If an operand is encountered, add it to Y.

4. If a left parenthesis is encountered, push it onto Stack.

5. If an operator is encountered ,then:

a. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) which has the same precedence as or higher precedence than operator.

b. Add operator to Stack.

6. If a right parenthesis is encountered ,then:

a. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a left parenthesis is encountered.

b. Remove the left Parenthesis.

7. END.

What is a Queue?

A queue is a lot like a stack. A Queue is also a linear structure that follows a First In First Out (FIFO) order, but they differ in how elements are removed. Queues are open from both ends: one end for inserting data (enqueue), and the other end for removing data (dequeue). A stack is only open from one end.

Elements are always added to the back and removed from the front. Think of it as a line of people waiting for a bus at the bus stand. The person who will come first will be the first one to enter the bus.

Insertion and deletion happen on different ends

The simplest example of a queue is the typical line that we all participate in from time to time. We wait in a line for a movie, we wait in the check-out line at a grocery store, and we wait in the cafeteria line (so that we can pop the tray stack). Well-behaved lines, or queues, are very restrictive in that they have only one way in and only one way out. There is no jumping in the middle and no leaving before you have waited the necessary amount of time to get to the front.

Types of Queues

There are three common types of queues you can expect to encounter.

1. LINEAR QUEUE: In this queue form, elements are able to join the queue at one end and can exit from the queue at the other end. First In First Out (FIFO).

A real life example of this would be queuing to pay at the supermarket. The first person into the queue is the first person to be served. And if you join the queue last you are going to be served last (no pushing!). However, there is one difference, in a supermarket queue once the first person has been served the rest of the queue shuffles forward, making the previously second person now first, this is possible in a computer but very costly in terms of processing. The linear queue you are about to see ‘crawls’ through memory, devouring everything it comes across.

2. CIRCULAR QUEUE: In a circular queue, the last element is connected to the first element to form a circle. Initially, the front and rear parts of the queue point to the same location, but they move apart as more elements are inserted into the queue. A real-life example of a circular queue is an automated traffic signal system.

Unlike linear queues Circular queues allow for memory to be reused:

Generally, a circular buffer requires three pointers:

• one to the actual buffer in memory
• one to point to the start of valid data
• one to point to the end of valid data

3. PRIORITY QUEUE: In priority queues, elements are sorted based on priority. The most important element appears first, and the least important appears last. Priority queues are used in operating systems for load balancing to determine which programs should be given more priority.

A real world example of this would be an Accident and Emergency Department waiting room, someone who had fallen over, would probably be low priority compared with someone who had cut their head open, and as such even if the head injury patient came in later they would probably jump the queue.

How does Queue work?

A Queue allows for the following operations:

• enqueue(): this method adds an element to the end/rear of the queue
• dequeue(): this method removes an element from the front of the queue
• top(): returns the first element in the queue
• initialize(): creates an empty queue

Queue can be implemented using an Array, Stack or Linked List. The easiest way of implementing a queue is by using an Array.

Initially the head(FRONT) and the tail(REAR) of the queue points at the first index of the array (starting the index of array from 0). As we add elements to the queue, the tail keeps on moving ahead, always pointing to the position where the next element will be inserted, while the head remains at the first index.

When we remove an element from Queue, we can follow two possible approaches (mentioned [A] and [B] in above diagram). In [A] approach, we remove the element at head position, and then one by one shift all the other elements in forward position.

In approach [B] we remove the element from head position and then move head to the next position.

In approach [A] there is an overhead of shifting the elements one position forward every time we remove the first element.

In approach [B] there is no such overhead, but whenever we move head one position ahead, after removal of the first element, the size on Queue is reduced by one space each time.

Demonstration of Queues :

Operating systems often maintain a queue of processes that are ready to execute or that are waiting for a particular event to occur.

Computer systems must often provide a “holding area” for messages between two internal processes or programs, or between two systems over a network. This holding area is usually called a “buffer” and is often implemented as a queue, because we want the message time order to be retained.

Our software queues have counterparts in real world queues. We wait in queues to buy pizza, to enter movie theaters , to drive on a turnpike, and to ride on a roller coaster. Another important application of the queue data structure is to help us simulate and analyze such real world queues.

Algorithm :

First Come First Serve CPU Scheduling:

Simplest scheduling algorithm that schedules according to arrival times of processes. First come first serve scheduling algorithm states that the process that requests the CPU first is allocated the CPU first. It is implemented by using the FIFO queue. When a process enters the ready queue, its PCB is linked onto the tail of the queue. When the CPU is free, it is allocated to the process at the head of the queue. The running process is then removed from the queue. FCFS is a non-preemptive scheduling algorithm.