Data Structures and Algorithms: Queue and Stack

Study Notes

Data Structure and Algorithm: Queue and Stack

Data structures and algorithms are fundamental concepts in computer science. They help developers organize and process data efficiently. Two popular data structures are queues and stacks. Both have their unique properties and are used in various applications.

Stack

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. This means that the last element added to the stack is the first one to be removed. Stacks are often used for tasks that require backtracking, such as recursive algorithms or maintaining a history of function calls.

Basic Operations

Push: Add an element to the top of the stack.
Pop: Remove and return the element at the top of the stack.
Peek: Examine the element at the top of the stack without removing it.
IsEmpty: Check if the stack is empty.
IsFull: Check if the stack is full.

Implementation

Stacks can be implemented using arrays or linked lists. Here's a simple example of stack implementation using an array:

class Stack {
    int top;
    int capacity;
    int* stackArray;

    Stack(int size) {
        capacity = size;
        stackArray = new int[capacity];
        top = -1;
    }

    void push(int value) {
        top++;
        stackArray[top] = value;
    }

    int pop() {
        if (top < 0)
            return -1;
        return stackArray[top--];
    }

    int peek() {
        if (top < 0)
            return -1;
        return stackArray[top];
    }

    bool isEmpty() {
        return top < 0;
    }

    bool isFull() {
        return top >= capacity - 1;
    }
}

Queue

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. This means that the first element added to the queue is the first one to be removed. Queues are often used for tasks that involve processing elements in a specific order, such as handling requests or scheduling tasks.

Basic Operations

Enqueue: Add an element to the end of the queue.
Dequeue: Remove and return the element at the front of the queue.
Peek: Examine the element at the front of the queue without removing it.
IsEmpty: Check if the queue is empty.
IsFull: Check if the queue is full.

Implementation

Queues can also be implemented using arrays or linked lists. Here's a simple example of queue implementation using an array:

class Queue {
    int front;
    int rear;
    int capacity;
    int* queueArray;

    Queue(int size) {
        capacity = size;
        queueArray = new int[capacity];
        front = 0;
        rear = 0;
    }

    void enqueue(int value) {
        if (rear == capacity)
            rear = 0;
        queueArray[rear] = value;
        rear++;
    }

    int dequeue() {
        if (front == rear)
            return -1;
        int value = queueArray[front];
        front++;
        if (front == capacity)
            front = 0;
        return value;
    }

    int peek() {
        if (front == rear)
            return -1;
        return queueArray[front];
    }

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

    bool isFull() {
        return (rear == capacity && front == 0) || (front == rear && rear == capacity - 1);
    }
}

In conclusion, both stack and queue are essential data structures in computer science. They have different properties and are used in various applications based on the problem requirements. Understanding their basic operations and implementation can help developers use them effectively in their projects.

Description

Learn about the fundamental concepts of data structures and algorithms, specifically focusing on queues and stacks. Understand their properties, basic operations, and implementation using arrays or linked lists.