SUMMARY STACK AND QUEUE DATA STRUCTURES

SUMMARY STACK AND QUEUE DATA STRUCTURES

Stack is a data structure that stores its elements in an ordered manner, and it follows a particular order in which the operations are performed. The order may be LIFO (Last in First out) or FILO (First in Last out). The following three basic operations are performed in the stack:
  • 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 pushed. If the stack is empty, then it is said to be an Underflow condition.
  • Peek or Top: Returns the top element of the stack.
  • isEmpty: Returns true if the stack is empty, else false.
The applications of the stack are:
// C program for array implementation of stack
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
  
// A structure to represent a stack
struct Stack {
    int top;
    unsigned capacity;
    int* array;
};
  
// function to create a stack of given capacity. It initializes size of
// stack as 0
struct Stack* createStack(unsigned capacity)
{
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
    return stack;
}
  
// Stack is full when top is equal to the last index
int isFull(struct Stack* stack)
{
    return stack->top == stack->capacity - 1;
}
  
// Stack is empty when top is equal to -1
int isEmpty(struct Stack* stack)
{
    return stack->top == -1;
}
  
// Function to add an item to stack.  It increases top by 1
void push(struct Stack* stack, int item)
{
    if (isFull(stack))
        return;
    stack->array[++stack->top] = item;
    printf("%d pushed to stack\n", item);
}
  
// Function to remove an item from stack.  It decreases top by 1
int pop(struct Stack* stack)
{
    if (isEmpty(stack))
        return INT_MIN;
    return stack->array[stack->top--];
}
  
// Function to return the top from stack without removing it
int peek(struct Stack* stack)
{
    if (isEmpty(stack))
        return INT_MIN;
    return stack->array[stack->top];
}
  
// Driver program to test above functions
int main()
{
    struct Stack* stack = createStack(100);
  
    push(stack, 10);
    push(stack, 20);
    push(stack, 30);
  
    printf("%d popped from stack\n", pop(stack));
  
    return 0;
}
Same as stack, queue is a data structure that stores its elements in an ordered manner. The order is FIFO (First in First Out). Mainly the following four basic operations are performed on queue:
  • Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
  • Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
  • Front: Get the front item from the queue.
  • Rear: Get the last item from the queue.
// C program for array implementation of queue
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
  
// A structure to represent a queue
struct Queue
{
    int front, rear, size;
    unsigned capacity;
    int* array;
};
  
// function to create a queue of given capacity. 
// It initializes size of queue as 0
struct Queue* createQueue(unsigned capacity)
{
    struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0; 
    queue->rear = capacity - 1;  // This is important, see the enqueue
    queue->array = (int*) malloc(queue->capacity * sizeof(int));
    return queue;
}
  
// Queue is full when size becomes equal to the capacity 
int isFull(struct Queue* queue)
{  return (queue->size == queue->capacity);  }
  
// Queue is empty when size is 0
int isEmpty(struct Queue* queue)
{  return (queue->size == 0); }
  
// Function to add an item to the queue.  
// It changes rear and size
void enqueue(struct Queue* queue, int item)
{
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1)%queue->capacity;
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;
    printf("%d enqueued to queue\n", item);
}
  
// Function to remove an item from queue. 
// It changes front and size
int dequeue(struct Queue* queue)
{
    if (isEmpty(queue))
        return INT_MIN;
    int item = queue->array[queue->front];
    queue->front = (queue->front + 1)%queue->capacity;
    queue->size = queue->size - 1;
    return item;
}
  
// Function to get front of queue
int front(struct Queue* queue)
{
    if (isEmpty(queue))
        return INT_MIN;
    return queue->array[queue->front];
}
  
// Function to get rear of queue
int rear(struct Queue* queue)
{
    if (isEmpty(queue))
        return INT_MIN;
    return queue->array[queue->rear];
}
  
// Driver program to test above functions./
int main()
{
    struct Queue* queue = createQueue(1000);
  
    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    enqueue(queue, 40);
  
    printf("%d dequeued from queue\n\n", dequeue(queue));
  
    printf("Front item is %d\n", front(queue));
    printf("Rear item is %d\n", rear(queue));
  
    return 0;
}
Reference: https://www.geeksforgeeks.org/queue-set-1introduction-and-array-implementation/
                  https://www.geeksforgeeks.org/stack-data-structure-introduction-program/
                  BINUS MAYA Stack and Queue


Comments

Post a Comment