Stack and Queue......................pptx

it

1. Data Structures and Algorithms Stack and Queue

2. Stack A stack abstract type is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. There are many applications of stacks, including: Space for function parameters and local variables is created internally using a stack. Compiler's syntax check for matching braces is implemented by using stack. Support for recursion. It can act as an auxiliary data structure for other abstract data types.

3. Uses for Stacks and Queues: Programmer’s Tools The array—(linked lists, trees, and so on), are appropriate for the kind of data you might find in a database application. They’re typically used for personnel records, inventories, financial data, and so on—data that corresponds to real-world objects or activities. These structures facilitate access to data: They make it easy to insert, delete, and search for particular items. Stacks and Queues on the other hand, are more often used as programmer’s tools. They’re primarily conceptual aids rather than full-fledged data storage devices. Their lifetime is typically shorter than that of the data base-type structures. They are created and used to carry out a particular task during the operation of a function within a program; when the task is completed, they’re discarded.

4. Stacks and Queues: Restricted Access to Data In an array, any item can be accessed, either immediately—if its index number is known—or by searching through a sequence of cells until it’s found. In stacks and queues, however, access is restricted: Only one item can be read or removed at a given time. The interface of these structures is designed to enforce this restricted access. Access to other items is (in theory) not allowed.

5. Stacks and Queues: More Abstract Stacks and queues are more abstract entities than arrays and many other data storage structures. They’re defined primarily by their interface—the permissible operations that can be carried out on them. The underlying mechanism used to implement them is typically not visible to their users. For example, the underlying mechanism for a stack can be an array, as we will show in this chapter, or it can be a linked list.

6. Understanding Stacks A stack allows access to only one data item: the last item inserted. If you remove this item, you can access the next-to-last item inserted, and so on. This is a useful capability in many programming situations. In this section, we’ll see how a stack can be used to check whether parentheses, braces, and brackets are balanced in a computer program source file. Stacks also play a vital role in parsing ( analyzing ) arithmetic expressions such as 3*(4+5).

7. Stack operations Placing a data item on the top of the stack is called pushing it. Removing it from the top of the stack is called popping it. These are the primary stack operations. A stack is said to be a Last-In-First-Out (LIFO) storage mechanism because the last item inserted is the first one to be removed Push and pop are the two primary stack operations. However, it’s sometimes useful to be able to read the value from the top of the stack without removing it. The peek operation does this.

8. Stack Size Stacks are typically small, temporary data structures

9. Queue The word queue is British for line (the kind you wait in). In Britain, to “queue up” means to get in line. In computer science a queue is a data structure that is similar to a stack, except that in a queue the first item inserted is the first to be removed (FIFO). In a stack, as we’ve seen, the last item inserted is the first to be removed (LIFO).

10. Queue Queue is also an abstract data structure or a linear data structure, in which the first element is inserted from one end called us rear (also called tail), and the deletion of the existing clement takes place from the other end, called as front (also called head). This makes queue as FIFO data structure, which means that element inserted first will also be removed first.

11. Uses of Queues They’re also used to model real world situations such as people waiting in line at a bank, airplanes waiting to take off, or data packets waiting to be transmitted over the Internet. There are various queues quietly doing their job in your computer’s (or the network’s) operating system. There’s a printer queue where print jobs wait for the printer to be available. A queue also stores keystroke data as you type at the keyboard. Using a queue guarantees the keystrokes stay in order until they can be processed.

12. Queue The terms for insertion and removal in a stack are fairly standard; everyone says push and pop. Standardization hasn’t progressed this far with queues. Insert is also called put or add or enque , whereas remove might be called delete or get or de-que. The rear of the queue, where items are inserted, is also called the back or tail or end. The front, where items are removed, might also be called the head.

13. Priority Queues: The priority queue abstract data type is designed for systems that maintain a collection of prioritized elements, where elements are removed from the collection in order of their priority. Priority queues turn up in various applications, for example, processing jobs, where we process each job based on how urgent it is. Operating systems often use a priority queue for the ready queue of processes to run on the CPU.