(Solved Homework): 2. individual assignments due by Wednesday une T?l17 2.

Data structure is a specialized way or format for organizing and storing data in computers. Data structures provide a way to manage large amount of data efficiently. Data structure is based on the ability of computers to fetch and store data at any place specified by memory address. There are many types of data structure like array, linked list, stack, queue, record etc.

STACK

Stack is an abstract data type with bounded or predefined capacity. An Abstract data type means the data type is defined by it behavior specifically in terms of possible values, possible operations on data of this type and the behavior of these operations. Stack is a linear data structure which follows a particular order in which operations are performed. The operations in stack are performed in the order LIFO which is Last In First Out.

A stack can be represented in the following way. Stack has two main function push() and pop().

Push() – This function is used to insert new element to stack.

Pop() – This function is used to delete an element from stack.

Both functions push() and pop() happens at the end of the stack called TOP.

Real life examples of stack can be deck of cards, pile of plates. Stack is flexible with size , it can either be fixed size or it can be dynamic size.

QUEUE

Similar to stack queue is an abstract data type and a linear data structure. In the queue insertion of new element occurs at the end called “REAR” (also called tail) and deletion of an existing element occurs at the end called “FRONT”(also called head). Queue follows a FIFO (First In First Out) mode of operation. The process of adding element is called enqueue () operation and process of deleting element is called dequeue() operation.

Implementation of stack and queue in Operating system

Stack and Queue as a linear data structure has many applications in computer systems. Some of the major application of stack and queue are listed below:

Stack

Memory management/Program stack – One of the important part of computing system is remembering the variables of methods that is currently in execution. Each method has a collection of variables that it uses while working. This collection of variables is called activation record. Computers store activation record of methods currently in execution on a stack called program stack.

For example if a computer is executing a method A. During the process method A calls method B . Then computer goes through the following steps

1. It store the location of method A in method A’s activation record
2. Pushes the activation record of B on top of stack and initializes the variables of B.
3. Executes the code of method B.

Once method B completes the execution

1. It pop method B’s activation record from top of stack ad places method A’s activation record on top.
2. Continues executing method A from the location it had stored in A’s activation record.

Expression evaluation – stacks play a major role in evaluating arithmetic, Boolean and logical expressions. Stacks are very useful in evaluating post-fix, pre-fix and in-fix expressions.

In-order tree traversal – Stacks is useful in completing the in-order traversal of a binary tree. Stack is used to remember the path of the tree. The stack will hold the nodes that are yet to iterate. Once the stack is empty we will have completed the iteration process.

Queue

Scheduling – Operating system uses queues to schedule jobs, processes and CPU. When there are various jobs or processes that are waiting to be executed, Operating system puts them in a queue and executes them in the FIFO order. There are situations when various processes are requesting for same resource such as CPU. Operating system places the requests in a queue and addresses them in the FIFO order.

Multiprocessing- The ability of a system to run multiple processes simultaneously is called multiprocessing. Operating system places the programs ready for execution in the ready queue. When the user requests the operating system to run a program, the program enters the back of the queue. The operating system always has the computer working on a program, and when the system decides that the current program has run long enough, it sends the program to the back of the queue and removes the next program from the queue to run. Because the operating system rotates through programs every few milliseconds, to our eyes it appears that the programs are running simultaneously.

Network communications- Network routers receives a number of messages that need to be forwarded to other destinations. The router receives all incoming messages and places these messages into a queue in the memory. Router also removes the messages from the queue and sends them to appropriate destinations.

Computing systems – Network has a printer server for each printer, which uses queues to keep track of printing jobs. When the server receives a new printing request it adds the request to the queue. When the server receives the message that the printing has been completed it removes the oldest unprinted job from the queue and send that job to printer.

Both queue and stack has its own benefit and usages. It depends on the situation or context on which we can decide whether we need to use queue or stack. For theory purpose we can say Queue is used more in hardware/software and operating system because FIFO is most suited for scheduling jobs, resources and threads. In short queues are used for all anything which requires real time processes.