Basic concept of stacks & queues

Introduction

Stacks and queues are fundamental data structures in computer science and are widely used in various applications. In this topic, we will explore the basic concepts of stacks and queues, their array and linked representations, operations on stacks and queues, multiple stacks, and their real-world applications.

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 have two main operations: push (insertion) and pop (deletion).

Array Representation of Stacks

In the array representation of stacks, a fixed-size array is used to store the elements. The top of the stack is represented by a variable that keeps track of the index of the topmost element.

Creating a Stack

To create a stack, we need to initialize an empty array and set the top variable to -1, indicating an empty stack.

stack = []
top = -1

Push Operation

The push operation is used to insert an element into the stack. It involves incrementing the top variable and adding the element to the array at the top index.

def push(element):
    global top
    top += 1
    stack.append(element)

Pop Operation

The pop operation is used to remove the topmost element from the stack. It involves decrementing the top variable and returning the element at the top index.

def pop():
    global top
    if top == -1:
        return 'Stack is empty'
    else:
        element = stack[top]
        top -= 1
        return element

Get Top Element Operation

The get top element operation returns the topmost element of the stack without removing it.

def get_top():
    if top == -1:
        return 'Stack is empty'
    else:
        return stack[top]

Check if Stack is Empty Operation

The empty operation checks if the stack is empty by checking the value of the top variable.

def empty():
    return top == -1

Linked Representation of Stacks

In the linked representation of stacks, a linked list is used to store the elements. Each node of the linked list contains the element and a pointer to the next node.

Creating a Stack using Linked List

To create a stack using a linked list, we need to initialize an empty linked list and set the top variable to None, indicating an empty stack.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None

stack = Stack()

Push Operation

The push operation is used to insert an element into the stack. It involves creating a new node with the element and updating the next pointer to point to the previous top node.

def push(element):
    new_node = Node(element)
    new_node.next = stack.top
    stack.top = new_node

Pop Operation

The pop operation is used to remove the topmost element from the stack. It involves updating the top pointer to point to the next node and returning the element of the previous top node.

def pop():
    if stack.top is None:
        return 'Stack is empty'
    else:
        element = stack.top.data
        stack.top = stack.top.next
        return element

Get Top Element Operation

The get top element operation returns the topmost element of the stack without removing it.

def get_top():
    if stack.top is None:
        return 'Stack is empty'
    else:
        return stack.top.data

Check if Stack is Empty Operation

The empty operation checks if the stack is empty by checking the value of the top pointer.

def empty():
    return stack.top is None

Multiple Stacks

Multiple stacks are used when we need to implement multiple independent stacks in a single array or linked list. Each stack has its own top variable or top pointer.

Definition and Use Cases

Multiple stacks refer to the implementation of two or more independent stacks in a single data structure. They are useful in scenarios where we need to manage multiple collections of elements separately.

Implementation using Arrays or Linked Lists

To implement multiple stacks using arrays, we divide the array into multiple segments and allocate each segment to a separate stack. Each stack has its own top variable to keep track of the topmost element.

To implement multiple stacks using linked lists, we create multiple linked lists and allocate each linked list to a separate stack. Each stack has its own top pointer to keep track of the topmost element.

Queues

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. It means that the element inserted first is the first one to be removed. Queues have two main operations: enqueue (insertion) and dequeue (deletion).

Array Representation of Queues

In the array representation of queues, a fixed-size array is used to store the elements. The front and rear variables are used to keep track of the indices of the front and rear elements, respectively.

Creating a Queue

To create a queue, we need to initialize an empty array, set the front and rear variables to -1, indicating an empty queue.

queue = []
front = -1
rear = -1

Enqueue Operation

The enqueue operation is used to insert an element into the queue. It involves incrementing the rear variable, adding the element to the array at the rear index, and updating the rear variable.

def enqueue(element):
    global rear
    if rear == -1:
        front = 0
    rear += 1
    queue.append(element)

Dequeue Operation

The dequeue operation is used to remove the front element from the queue. It involves incrementing the front variable and returning the element at the front index.

def dequeue():
    global front
    if front == -1 or front > rear:
        return 'Queue is empty'
    else:
        element = queue[front]
        front += 1
        return element

Get Front Element Operation

The get front element operation returns the front element of the queue without removing it.

def get_front():
    if front == -1 or front > rear:
        return 'Queue is empty'
    else:
        return queue[front]

Get Rear Element Operation

The get rear element operation returns the rear element of the queue without removing it.

def get_rear():
    if front == -1 or front > rear:
        return 'Queue is empty'
    else:
        return queue[rear]

Check if Queue is Empty Operation

The empty operation checks if the queue is empty by checking the values of the front and rear variables.

 def empty():
    return front == -1 or front > rear

Linked Representation of Queues

In the linked representation of queues, a linked list is used to store the elements. Each node of the linked list contains the element and a pointer to the next node.

Creating a Queue using Linked List

To create a queue using a linked list, we need to initialize an empty linked list and set the front and rear pointers to None, indicating an empty queue.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

queue = Queue()

Enqueue Operation

The enqueue operation is used to insert an element into the queue. It involves creating a new node with the element and updating the next pointer of the rear node to point to the new node. If the queue is empty, both the front and rear pointers are updated to point to the new node.

 def enqueue(element):
    new_node = Node(element)
    if queue.front is None:
        queue.front = new_node
        queue.rear = new_node
    else:
        queue.rear.next = new_node
        queue.rear = new_node

Dequeue Operation

The dequeue operation is used to remove the front element from the queue. It involves updating the front pointer to point to the next node and returning the element of the previous front node. If the queue becomes empty after dequeue, both the front and rear pointers are set to None.

 def dequeue():
    if queue.front is None:
        return 'Queue is empty'
    else:
        element = queue.front.data
        queue.front = queue.front.next
        if queue.front is None:
            queue.rear = None
        return element

Get Front Element Operation

The get front element operation returns the front element of the queue without removing it.

 def get_front():
    if queue.front is None:
        return 'Queue is empty'
    else:
        return queue.front.data

Get Rear Element Operation

The get rear element operation returns the rear element of the queue without removing it.

 def get_rear():
    if queue.rear is None:
        return 'Queue is empty'
    else:
        return queue.rear.data

Check if Queue is Empty Operation

The empty operation checks if the queue is empty by checking the values of the front and rear pointers.

 def empty():
    return queue.front is None

Application of Stacks - Conversion: infix, prefix, postfix and evaluation of arithmetic expressions

Stacks are widely used in the conversion and evaluation of arithmetic expressions. They provide an efficient way to handle the order of operations and parentheses.

Infix to Postfix Conversion

Infix to postfix conversion is the process of converting an infix expression to a postfix expression. It involves using a stack to handle the order of operations and parentheses.

Algorithm and Steps

1. Create an empty stack and an empty output string.
2. Scan the infix expression from left to right.
3. If the scanned character is an operand, append it to the output string.
4. If the scanned character is an operator, pop operators from the stack and append them to the output string until an operator with lower precedence is encountered or the stack is empty. Then push the scanned operator to the stack.
5. If the scanned character is an opening parenthesis, push it to the stack.
6. If the scanned character is a closing parenthesis, pop operators from the stack and append them to the output string until an opening parenthesis is encountered. Pop and discard the opening parenthesis.
7. Repeat steps 3-6 until all characters have been scanned.
8. Pop any remaining operators from the stack and append them to the output string.
9. The output string is the postfix expression.

Example

Infix expression: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 Postfix expression: 3 4 2 * 1 5 - 2 3 ^ ^ / +

Infix to Prefix Conversion

Infix to prefix conversion is the process of converting an infix expression to a prefix expression. It involves using a stack to handle the order of operations and parentheses.

Algorithm and Steps

1. Reverse the infix expression.
2. Replace opening parentheses with closing parentheses and vice versa.
3. Apply the infix to postfix conversion algorithm on the modified infix expression.
4. Reverse the postfix expression to get the prefix expression.

Example

Infix expression: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3 Prefix expression: + 3 / * 4 2 ^ - 1 5 ^ 2 3

Postfix Evaluation

Postfix evaluation is the process of evaluating a postfix expression. It involves using a stack to store the operands and perform the operations.

Algorithm and Steps

1. Create an empty stack.
2. Scan the postfix expression from left to right.
3. If the scanned character is an operand, push it to the stack.
4. If the scanned character is an operator, pop two operands from the stack, perform the operation, and push the result back to the stack.
5. Repeat steps 3-4 until all characters have been scanned.
6. The result is the top element of the stack.

Example

Postfix expression: 3 4 2 * 1 5 - 2 3 ^ ^ / + Result: 3

Prefix Evaluation

Prefix evaluation is the process of evaluating a prefix expression. It involves using a stack to store the operands and perform the operations.

Algorithm and Steps

1. Reverse the prefix expression.
2. Scan the reversed prefix expression from left to right.
3. If the scanned character is an operand, push it to the stack.
4. If the scanned character is an operator, pop two operands from the stack, perform the operation, and push the result back to the stack.
5. Repeat steps 3-4 until all characters have been scanned.
6. The result is the top element of the stack.

Example

Prefix expression: + 3 / * 4 2 ^ - 1 5 ^ 2 3 Result: 3

Real-world Applications and Examples

Stacks and queues have various real-world applications in computer science and everyday life.

Undo/Redo Functionality in Text Editors

Text editors often use stacks to implement the undo and redo functionality. Each change made to the text is stored as a command in a stack. When the user performs the undo operation, the last command is popped from the undo stack and applied in reverse. The popped command is then pushed to the redo stack. The redo operation pops a command from the redo stack and applies it.

Function Call Stack in Programming Languages

Programming languages use stacks to manage function calls. When a function is called, its local variables and return address are pushed onto the stack. When the function completes execution, the local variables and return address are popped from the stack, and control returns to the calling function.

Backtracking Algorithms

Backtracking algorithms, such as depth-first search and recursive algorithms, often use stacks to keep track of the current state and backtrack when necessary. The stack stores the path or choices made so far, allowing the algorithm to explore different paths and backtrack when a dead end is reached.

Advantages and Disadvantages of Stacks and Queues

Advantages

1. Efficient Insertion and Deletion Operations: Stacks and queues provide efficient insertion and deletion operations with a time complexity of O(1).
2. Easy Implementation and Understanding: Stacks and queues are simple data structures that are easy to implement and understand.
3. Useful in Solving Various Problems: Stacks and queues are versatile data structures that can be used to solve a wide range of problems, such as expression evaluation, backtracking, and managing function calls.

Disadvantages

1. Limited Capacity in Array Representation: The array representation of stacks and queues has a limited capacity, which can lead to overflow or underflow if the capacity is exceeded.
2. Inefficient for Searching and Accessing Elements in Queues: In the array representation of queues, searching and accessing elements in the middle of the queue is inefficient as it requires shifting all the elements.

Conclusion

In conclusion, stacks and queues are fundamental data structures that play a crucial role in computer science. They provide efficient insertion and deletion operations, are easy to implement and understand, and have various real-world applications. Understanding and implementing stacks and queues are essential for mastering data structures and algorithms.

Summary

Stacks and queues are fundamental data structures in computer science. Stacks follow the Last-In-First-Out (LIFO) principle, while queues follow the First-In-First-Out (FIFO) principle. Stacks can be represented using arrays or linked lists, and they support operations like push, pop, get top element, and check if empty. Queues can also be represented using arrays or linked lists, and they support operations like enqueue, dequeue, get front element, get rear element, and check if empty. Stacks and queues have various real-world applications and advantages, but they also have limitations. Understanding and implementing stacks and queues are essential for mastering data structures and algorithms.

Analogy

An analogy to understand stacks and queues is a stack of plates and a queue of people waiting in line. In a stack of plates, the last plate placed on top is the first one to be removed (LIFO). In a queue of people waiting in line, the person who arrived first is the first one to be served (FIFO).