Lab46 Wiki

! queue data structure !!!!

Queue Data Structure

Queue is a specialized data storage structure (Abstract data type). Unlike, arrays access of elements in a Queue is restricted. It has two main operations enqueue and dequeue. Insertion in a queue is done using enqueue function and removal from a queue is done using dequeue function. An item can be inserted at the end (‘rear’) of the queue and removed from the front (‘front’) of the queue. It is therefore, also called First-In-First-Out (FIFO) list. Queue has five properties - capacity stands for the maximum number of elements Queue can hold, size stands for the current size of the Queue, elements is the array of elements, front is the index of first element (the index at which we remove the element) and rear is the index of last element (the index at which we insert the element).

Queue is a data structure that maintain “First In First Out” (FIFO) order. And can be viewed as people queueing up to buy a ticket. In programming, queue is usually used as a data structure for BFS (Breadth First Search). Queue operations

Operations on queue Q are :

1. enqueue - insert item at the back of queue Q 2. dequeue - return (and virtually remove) the front item from queue Q 3. init - intialize queue Q, reset all variables.

List any sites, books, or sources utilized when researching information on this topic. (Remove any filler text).

• Reference 1: http://www.thelearningpoint.net/computer-science/data-structures-queues--with-c-program-source-code
• Reference 2: http://harvestsoft.net/files/queue.pdf
• Reference 3: google.com

stack push operation

The push operation adds a new element to the top of the stack (FILO)First in Last Out. You can also push until the array is full stack overflow, or you can pop until the array is empty stack underflow.

List any sites, books, or sources utilized when researching information on this topic. (Remove any filler text).

* http://www.cplusplus.com/reference/stl/stack/push/

* http://en.wikipedia.org/wiki/Stack_(abstract_data_type)

Demonstration of the indicated keyword.

If you wish to aid your definition with a code sample, you can do so by using a wiki code block, an example follows:

#include<stdio.h> #include<stdlib.h> /* Stack has three properties. capacity stands for the maximum number of elements stack can hold. Size stands for the current size of the stack and elements is the array of elements */ typedef struct Stack { int capacity; int size; int *elements; }Stack; /* crateStack function takes argument the maximum number of elements the stack can hold, creates a stack according to it and returns a pointer to the stack. */ Stack * createStack(int maxElements) { /* Create a Stack */ Stack *S; S = (Stack *)malloc(sizeof(Stack)); /* Initialise its properties */ S→elements = (int *)malloc(sizeof(int)*maxElements); S→size = 0; S→capacity = maxElements; /* Return the pointer */ return S;}void pop(Stack *S){ /* If stack size is zero then it is empty. So we cannot pop */ if(S→size==0) { printf(“Stack is Empty\n”); return; } /* Removing an element is equivalent to reducing its size by one */ else { S→size–; } return; } int top(Stack *S) { if(S→size==0) { printf(“Stack is Empty\n”); exit(0); } /* Return the topmost element */ return S→elements[S→size-1]; } void push(Stack *S,int element) { /* If the stack is full, we cannot push an element into it as there is no space for it.*/ if(S→size == S→capacity) { printf(“Stack is Full\n”); } else { /* Push an element on the top of it and increase its size by one*/ S→elements[S→size++] = element; } return;}int main() { Stack *S = createStack(5); push(S,7); push(S,5); push(S,21); push(S,-1); printf(“Top element is %d\n”,top(S)); pop(S); printf(“Top element is %d\n”,top(S)); pop(S); printf(“Top element is %d\n”,top(S)); pop(S); printf(“Top element is %d\n”,top(S));