Stacks & Queues: CSU1051 - Shoolini U

Stacks and Queues Representations, Implementations & Applications

1. Introduction to Stacks and Queues

Stacks and queues are linear data structures that are widely used in computer science and programming for various applications. They are used to organize and store data in a specific order, allowing for efficient data access and manipulation. In this article, we will explore the concepts, representations, implementation, and applications of stacks and queues in data structures and algorithms. The article is designed to cover information suitable for readers at different levels, from beginners to advanced computer science students.

1.1 Stacks

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. It means that the element inserted last is the first one to be removed. Stacks are commonly used for various purposes such as memory allocation, parsing, and other algorithmic applications. The primary operations performed on stacks are push, pop, and peek.

1.2 Queues

A queue is another linear data structure that follows the First In, First Out (FIFO) principle. In a queue, the element inserted first is the first one to be removed. Queues are used in various applications like scheduling processes, handling requests, and many more. The primary operations performed on queues are enqueue, dequeue, and front.

2. Representations of Stacks and Queues

Stacks and queues can be represented using various data structures, such as arrays, linked lists, and dynamic arrays. Each representation has its advantages and disadvantages depending on the specific use case and requirements.

2.1 Array Representation

Arrays are a simple and efficient way to represent stacks and queues. They have a fixed size, which can be a limitation if the size of the stack or queue exceeds the allocated size. In this representation, elements are stored in contiguous memory locations, and the index of the array is used to access the elements. For a stack, the top element is maintained at the end of the array, while for a queue, the front and rear pointers are used to manage the elements.

2.2 Linked List Representation

Linked lists are a more dynamic representation for stacks and queues. They allow for the size of the data structure to be changed during runtime, which can be an advantage in certain applications. In this representation, elements are stored in nodes, and each node contains a pointer to the next node. For a stack, the top element is maintained at the head of the linked list, while for a queue, the front and rear pointers are used to manage the elements.

2.3 Dynamic Array Representation

Dynamic arrays are a hybrid representation of stacks and queues that combine the advantages of both arrays and linked lists. They have a dynamic size that can be changed during runtime, and they store elements in contiguous memory locations. In this representation, a dynamic array is used to store the elements, and the size of the array is increased or decreased as required. The top of the stack and the front and rear of the queue are maintained using indices.

3. Implementation of Stacks and Queues

In this section, we will discuss the implementation of stacks and queues using C++ programming language. We will explore the implementation using arrays, linked lists, and dynamic arrays.

3.1 Implementation of Stacks

3.1.1 Array-based Stack Implementation

Array-based stack implementation is simple and efficient. Here, we define the maximum size of the stack and use an array to store the elements. The top of the stack is maintained using an integer variable.

// Array-based stack implementation in C++
#include <iostream>
const int MAX_SIZE = 100;

class Stack {
private:
int arr[MAX_SIZE];
int top;

public:
Stack() { top = -1; }
void push(int x) {
    Node* newNode = new Node();
    newNode->data = x;
    newNode->next = top;
    top = newNode;
}

int pop() {
    if (isEmpty()) {
        std::cout << "Stack underflow!" << std::endl;
        return -1;
    }
    Node* temp = top;
    int popped = temp->data;
    top = top->next;
    delete temp;
    return popped;
}

int peek() {
    if (isEmpty()) {
        std::cout << "Stack is empty!" << std::endl;
        return -1;
    }
    return top->data;
}

bool isEmpty() {
    return (top == nullptr);
}};

3.2 Implementation of Queues

3.2.1 Array-based Queue Implementation

Array-based queue implementation uses an array to store the elements. Front and rear pointers are used to maintain the first and last elements in the queue.

// Array-based queue implementation in C++
#include <iostream>
const int MAX_SIZE = 100;

class Queue {
private:
  int arr[MAX_SIZE];
  int front, rear;

public:
  Queue() {
    front = -1;
    rear = -1;
  }
  void enqueue(int x) {
    if ((rear + 1) % MAX_SIZE == front) {
        std::cout << "Queue overflow!" << std::endl;
        return;
    }
    if (isEmpty()) {
        front = rear = 0;
    } else {
        rear = (rear + 1) % MAX_SIZE;
    }
    arr[rear] = x;
}

int dequeue() {
    if (isEmpty()) {
        std::cout << "Queue underflow!" << std::endl;
        return -1;
    }
    int dequeued = arr[front];
    if (front == rear) {
        front = rear = -1;
    } else {
        front = (front + 1) % MAX_SIZE;
    }
    return dequeued;
}

int frontElement() {
    if (isEmpty()) {
        std::cout << "Queue is empty!" << std::endl;
        return -1;
    }
    return arr[front];
}

bool isEmpty() {
    return (front == -1 && rear == -1);
}
};
3.2.2 Linked List-based Queue Implementation

In the linked list-based queue implementation, we use a singly linked list to store the elements. The front and rear pointers are used to maintain the first and last elements in the queue.

// Linked list-based queue implementation in C++
#include <iostream>
class Node {
public:
  int data;
  Node* next;
};

class Queue {
  private:
    Node* front;
    Node* rear;

  public:
    Queue() {
      front = nullptr;
      rear = nullptr;
    }
    void enqueue(int x) {
      Node* newNode = new Node();
      newNode->data = x;
      newNode->next = nullptr;

      if (isEmpty()) {
          front = rear = newNode;
      } else {
          rear->next = newNode;
          rear = newNode;
      }
  }

  int dequeue() {
      if (isEmpty()) {
          std::cout << "Queue underflow!" << std::endl;
          return -1;
      }
      Node* temp = front;
      int dequeued = temp->data;
      front = front->next;
      if (front == nullptr) {
          rear = nullptr;
      }
      delete temp;
      return dequeued;
  }

  int frontElement() {
      if (isEmpty()) {
          std::cout << "Queue is empty!" << std::endl;
          return -1;
      }
      return front->data;
  }

  bool isEmpty() {
      return (front == nullptr && rear == nullptr);
  }
};

4. Applications of Stacks and Queues in Data Structures and Algorithms

Stacks and queues are fundamental data structures that have numerous applications in various domains of computer science, including parsing, memory management, and algorithm design. In this section, we will discuss some of the most common applications of stacks and queues in data structures and algorithms.

4.1 Applications of Stacks

4.1.1 Function Call and Return Mechanism

Stacks are used in the function call and return mechanism of programming languages. When a function is called, the return address and local variables are pushed onto the stack, and when the function returns, these values are popped from the stack, restoring the previous state of the program.

4.1.2 Expression Evaluation and Syntax Parsing

Stacks are used in the evaluation of arithmetic expressions and the parsing of programming language syntax. They can be used to convert infix expressions to postfix or prefix notation, evaluate postfix or prefix expressions, and check for balanced parentheses or brackets in a given expression.

4.1.3 Depth-First Search (DFS) Algorithm

In graph theory, the depth-first search (DFS) algorithm is an efficient method for traversing or searching a graph. DFS uses a stack data structure to store the vertices during the traversal process. This helps the algorithm to backtrack and explore alternative paths in the graph when a dead-end is reached.

4.2 Applications of Queues

4.2.1 Scheduling Processes in Operating Systems

Queues are used in operating systems for scheduling processes and managing the execution order of tasks. Processes waiting to be executed are stored in a queue, and the scheduler selects the next process based on predefined criteria, such as priority or arrival time.

4.2.2 Breadth-First Search (BFS) Algorithm

In graph theory, the breadth-first search (BFS) algorithm is another efficient method for traversing or searching a graph. BFS uses a queue data structure to store the vertices during the traversal process. This ensures that the vertices are explored in the order they are discovered, resulting in a level-by-level traversal of the graph.

4.2.3 Buffering Data in Communication Networks

Queues are used in communication networks as buffers to store data packets before they are transmitted or processed. This can help manage the flow of data in a network, prevent packet loss, and ensure that data is transmitted in the correct order.

5. Advanced Topics and Research Directions

Stacks and queues are widely studied in computer science, and there are numerous advanced topics and research directions related to these data structures. In this section, we will briefly discuss some of these advanced topics that may be of interest to computer science students and researchers.

5.1 Double-ended Queues (Deque)

A double-ended queue, or deque, is a more general form of a queue that allows elements to be added or removed from both ends. Deques are useful in various applications where elements need to be accessed or removed from both ends of the data structure, such as certain types of scheduling algorithms or sliding window problems.

5.2 Priority Queues and Heap Data Structure

A priority queue is a specialized data structure that supports efficiently accessing the element with the highest priority, usually based on a user-defined comparator function. Priority queues are used in various algorithms, such as Dijkstra's shortest path algorithm, A* search algorithm, and Huffman coding. One of the most common implementations of a priority queue is the heap data structure, which can be either a min-heap or a max-heap depending on the priority criteria.

5.3 Lock-free and Wait-free Stacks and Queues

Lock-free and wait-free stacks and queues are concurrent data structures designed for multi-threaded environments where multiple threads can access and modify the data structure simultaneously without blocking or waiting for locks. These data structures are an active area of research in parallel and distributed computing, and they can significantly improve the performance and scalability of parallel algorithms and applications.

5.4 Persistent and Confluently Persistent Stacks and Queues

Persistent and confluently persistent stacks and queues are data structures that maintain their history across operations, allowing previous versions of the data structure to be accessed and modified. These data structures have applications in various domains, such as functional programming, version control systems, and undo/redo functionality in software applications. Research in this area focuses on developing efficient algorithms and data structures for maintaining and querying persistent and confluently persistent stacks and queues.

5.5 Applications in Machine Learning and Artificial Intelligence

Stacks and queues have various applications in machine learning and artificial intelligence, such as modeling and simulating recursive or iterative processes, implementing search algorithms, and developing data structures for reinforcement learning and optimization problems. Research in this area focuses on leveraging the properties of stacks and queues to develop efficient algorithms and data structures for machine learning and artificial intelligence tasks.

6. Final Thoughts

This article provides a comprehensive overview of stacks and queues in data structures and algorithms, from basic concepts and implementations to advanced topics and research directions. Understanding stacks and queues is crucial for computer scientists, programmers, and researchers, as these data structures underlie many algorithms, applications, and research areas. By mastering stacks and queues, one can develop a strong foundation in computer science and be better prepared to tackle complex problems and challenges in the field.

7. Further Reading and Resources

For readers interested in exploring stacks, queues, and related data structures and algorithms in greater depth, we recommend the following resources:

7.1 Books

7.2 Online Courses and Tutorials

7.3 Research Papers and Journals

For readers interested in the latest research on stacks, queues, and related data structures and algorithms, we recommend exploring the following research journals and conferences:

8. Conclusion

Stacks and queues are fundamental data structures that play an essential role in various applications and research areas in computer science. We explored the fundamental concepts, representations, implementation, and applications of stacks and queues in data structures and algorithms. We discussed array-based, linked list-based, and dynamic array-based representations for stacks and queues, and provided C++ code examples for their implementation. We also covered various applications of stacks and queues in computer science, such as function call and return mechanisms, expression evaluation, graph traversal algorithms, process scheduling, and buffering data in communication networks. By understanding the concepts, implementations, and advanced topics related to stacks and queues, one can develop a strong foundation in computer science and be better prepared to tackle complex problems and challenges in the field. We hope this article serves as a valuable resource for readers interested in learning more about stacks, queues, and their applications in data structures and algorithms.