FOUNDATION OF COMPUTER SCIENCE (MTCS101)
Unit -1
1.List in data structure
The List Data Structure is a unique set of ordered elements where the same value can occur
multiple times and its characteristics include flexibility that allows individual access and edits
of elements based on the position or index. In many programming languages, the index of a list
starts from zero.
2.What is a list in data type?
List is a collection data type. It allows multiple values to be stored within the same field. In
Table Design, you must configure the List data type with all the values that the field stores.
These values will be available for the field in table Datasheet view and in DataPages.
3.When to use list data structure?
You want to access items quickly because arrays store them in a specific order. Use Lists when:
-You have different types of items to store, and you want flexibility. -You need to add or remove
items easily, like changing your mind about a hobby.
4.What is a linked list in data structure notes?
A linked list is a non primitive type of data structure in which each element is dynamically
allocated and in which elements point to each other to define a linear relationship. Elements of
linked list are called nodes where each node contains two things, data and pointer to next node.
5. What is a stack data structure? What are the applications of stack?
A stack is a data structure that is used to represent the state of an application at a particular
point in time. The stack consists of a series of items that are added to the top of the stack and
then removed from the top. It is a linear data structure that follows a particular order in which
operations are performed. LIFO (Last In First Out) or FILO (First In Last Out) are two possible
orders. A stack consists of a sequence of items. The element that's added last will come out
first, a real-life example might be a stack of clothes on top of each other. When we remove the
cloth that was previously on top, we can say that the cloth that was added last comes out first.
Following are some applications for stack data structure:
• It acts as temporary storage during recursive operations
• Redo and Undo operations in doc editors
• Reversing a string
• Parenthesis matching
• Postfix to Infix Expressions
• Function calls order
6.What are different operations available in stack data structure?
Some of the main operations provided in the stack data structure are:
• push: This adds an item to the top of the stack. The overflow condition occurs if the
stack is full.
• pop: This removes the top item of the stack. Underflow condition occurs if the stack
is empty.
• top: This returns the top item from the stack.
• isEmpty: This returns true if the stack is empty else false.
• size: This returns the size of the stack.
7. What is a queue data structure? What are the applications of queue?
A queue is a linear data structure that allows users to store items in a list in a
systematic manner. The items are added to the queue at the rear end until they are full,
at which point they are removed from the queue from the front. Queues are commonly
used in situations where the users want to hold items for a long period of time, such
as during a checkout process. A good example of a queue is any queue of customers
for a resource where the first consumer is served first.
Following are some applications of queue data structure:
• Breadth-first search algorithm in graphs
• Operating system: job scheduling operations, Disk scheduling, CPU scheduling etc.
• Call management in call centres
8. What are different operations available in queue data structure?
• enqueue: This adds an element to the rear end of the queue. Overflow conditions
occur if the queue is full.
• dequeue: This removes an element from the front end of the queue. Underflow
conditions occur if the queue is empty.
• isEmpty: This returns true if the queue is empty or else false.
• rear: This returns the rear end element without removing it.
• front: This returns the front-end element without removing it.
• size: This returns the size of the queue.
11. Differentiate between stack and queue data structure.
Stack Queue
Stack is a linear data structure where data Queue is a linear data structure where data is ended
is added and removed from the top. at the rear end and removed from the front.
Stack is based on LIFO(Last In First Out) Queue is based on FIFO(First In First Out)
principle principle
Insertion operation in Stack is known as
Insertion operation in Queue is known as eneque.
push.
Delete operation in Stack is known as pop. Delete operation in Queue is known as dequeue.
Only one pointer is available for both Two pointers are available for addition and
addition and deletion: top() deletion: front() and rear()
Stack Queue
Used in solving recursion problems Used in solving sequential processing problems
09. How to implement a queue using stack?
A queue can be implemented using two stacks. Let q be the queue andstack1 and stack2 be the
2 stacks for implementing q. We know that stack supports push, pop, and peek operations and
using these operations, we need to emulate the operations of the queue - enqueue and dequeue.
Hence, queue q can be implemented in two methods (Both the methods use auxillary space
complexity of O(n)):
. By making enqueue operation costly:
• Here, the oldest element is always at the top of stack1 which ensures dequeue operation
occurs in O(1) time complexity.
• To place the element at top of stack1, stack2 is used.
• Pseudocode:
Enqueue: Here time complexity will be O(n)
enqueue(q, data):
While stack1 is not empty:
Push everything from stack1 to stack2.
Push data to stack1
Push everything back to stack1.
Dequeue: Here time complexity will be O(1)
deQueue(q):
If stack1 is empty then error else
Pop an item from stack1 and return it
2. By making the dequeue operation costly:
• Here, for enqueue operation, the new element is pushed at the top of stack1. Here, the
enqueue operation time complexity is O(1).
• In dequeue, if stack2 is empty, all elements from stack1 are moved to stack2 and top
of stack2 is the result. Basically, reversing the list by pushing to a stack and returning
the first enqueued element. This operation of pushing all elements to a new stack takes
O(n) complexity.
• Pseudocode:
Enqueue: Time complexity: O(1)
enqueue(q, data):
Push data to stack1
Dequeue: Time complexity: O(n)
dequeue(q):
If both stacks are empty then raise error.
If stack2 is empty:
While stack1 is not empty:
push everything from stack1 to stack2.
Pop the element from stack2 and return it.