Data structures and algorithms

(Third Part — Stacks and Queues)

After covering arrays and sorting, today we will delve into three data storage structures: the stack, the queue, and the priority queue. We will start by discussing the distinctions between these structures and arrays. Subsequently, we will explore each structure individually. In the final section, we will focus on an operation in which the stack plays a pivotal role: parsing arithmetic expressions.

The article will be structured as follows:

A Different Kind of Structure?

Stack

Queue

priority queue

A Different Kind of Structure?

Exploring data structures is crucial as it guides us in understanding which data structure is needed for our work. This knowledge is necessary to proceed effectively.

Programmer’s Tools

There are various types of data structures available. These structures help in managing data by simplifying tasks like insertion, deletion, and searching of items. Programmers have a wide range of options to choose from.

Restricted Access

Using data structures makes a difference in how we access and manage information. With restricted access, we have more control over how we use and manipulate data. Sometimes, we can’t access all the items. These structures have an interface that is created to enforce this limited access. This means that we are (in theory) not allowed to access certain items.

More Abstract

Stacks, queues, and priority queues are more abstract compared to arrays and many other ways of storing data. When we describe these structures as more abstract, we mean that they are defined by certain behaviors or rules that guide how they are used, rather than being directly managed at a basic level like arrays.

Stacks

A stack is a fundamental data structure that follows the Last-In-First-Out (LIFO) principle. It can be visualized as a collection of elements arranged in a linear order, where elements can be inserted and removed only from one end, known as the “top.” Stacks are used in various applications, such as function call management, expression evaluation, and backtracking algorithms.

Here’s an overview of stack operations and algorithms associated with it:

Stack Operations:

• Push: This operation adds an element to the top of the stack.
• Pop: This operation removes the element from the top of the stack.
• Peek (or Top): This operation retrieves the element from the top of the stack without removing it.
• isEmpty: This operation checks if the stack is empty.
• Size: This operation returns the number of elements in the stack.

Stack Algorithms:

Parentheses Matching:

In this algorithm, a stack is used to check whether a given string of parentheses (and sometimes other symbols) is balanced or not. For example, “{[()]}”” is balanced, while “{[(])}” is not. The stack helps in maintaining the proper order of opening and closing symbols.

Queues

A queue is another fundamental data structure that follows the First-In-First-Out (FIFO) principle. It can be visualized as a linear collection of elements, where elements are inserted at the rear (end) and removed from the front (beginning). Queues are used in scenarios where tasks or elements need to be processed in the order they arrive, similar to people waiting in a line.

Here’s an overview of queue operations and algorithms associated with it:

Queue Operations:

• Add (or Offer): This operation adds an element to the rear of the queue.
• Remove (or Poll): This operation removes the element from the front of the queue.
• Peek (or Front): This operation retrieves the element from the front of the queue without removing it.
• isEmpty: This operation checks if the queue is empty.
• Size: This operation returns the number of elements in the queue.

Queue Algorithms:

A printer:

In scenarios where multiple tasks (print jobs) need to be processed by a resource (printer), a queue is used to manage the order of processing. The task that arrives first is processed first.

A circular queue

A circular queue is a variation of a regular queue that has a fixed size and treats the underlying array as circular, meaning that when the end of the array is reached, the next element is placed at the beginning. This circular arrangement allows for efficient space utilization and avoids the problem of running out of space at the end of the array. Circular queues are particularly useful in scenarios where resources need to be reused cyclically, such as in systems with limited buffer space or in cases where processing loops back to the beginning after reaching the end. Circular queues maintain the FIFO property of a regular queue while offering enhanced efficiency in terms of space and memory management.

Priority Queues

A priority queue is another essential data structure that extends the concept of a regular queue by introducing the notion of priority for each element. While a standard queue follows the First-In-First-Out (FIFO) principle, where elements are processed in the order they are added, a priority queue processes elements based on their priority level.

Here’s an overview of priority queue operations and associated concepts:

Priority Queue Operations:

• Insert (or Enqueue): This operation adds an element to the priority queue while considering its priority value. The element is placed in a position that maintains the priority order.
• Extract Maximum (or Dequeue): This operation removes and returns the element with the highest priority from the priority queue.
• Peek (or Front): This operation retrieves the element with the highest priority from the priority queue without removing it.
• isEmpty: This operation checks if the priority queue is empty. Size: This operation returns the number of elements in the priority queue.

Priority Queue Algorithms:

Task Scheduling with Deadlines:

In scenarios where tasks have different deadlines or urgency levels, a priority queue can be used to schedule tasks in a way that optimizes meeting deadlines and utilizing resources efficiently.

In conclusion, stacks, queues, and priority queues are fundamental data structures that play crucial roles in various computing scenarios. Each of these structures serves specific purposes and offers unique characteristics that make them valuable tools for organizing and manipulating data.