{"id":99,"date":"2018-07-18T10:07:46","date_gmt":"2018-07-18T10:07:46","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=99"},"modified":"2018-12-12T08:48:45","modified_gmt":"2018-12-12T08:48:45","slug":"stack-adt","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/stack-adt\/","title":{"rendered":"Stack ADT"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n

Welcome to the e-PG Pathshala Lecture Series on Data Structures. In this module we talk about a very important ADT \u2013 that is the Stack ADT.<\/p>\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of the introductory module are as follows:\r\n\r\n \r\n\r\n\u2022\u00a0 To understand the concept of a stack\r\n\r\n\u2022\u00a0 To appreciate the method of defining a Stack ADT\r\n\r\n\u2022\u00a0 To know about the different stack operations\r\n\r\n\u2022\u00a0 To understand some uses of stacks\r\n\r\n \r\n\r\n7.1 Introduction<\/strong>\r\n\r\n \r\n

Before we go further let us look at the use of stacks in everyday life. In general a stack is a pile of objects, typically one that is neatly arranged. Figure 7.1 shows stacks of notes, plates, sarees, chapathis, tyres and books that we see often see in our lives. In this module we will discuss the characteristics of the Stack used in the computing world.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n7.1.1<\/strong>\u00a0 <\/span>What is a stack?<\/strong>\r\n\r\n \r\n\r\nA stack is a sequence of items that are accessible at only one end of the sequence. It is an ordered group of homogeneous items or elements. Elements are added to and removed from a specially designated end called the top of the stack (the most recently added items are at the top of the stack). The last element to be added is the first to be removed (LIFO: Last In, First Out). In other words, a stack is a <\/span>restricted<\/strong> linear list <\/strong>in which all<\/span> additions and deletions are made at one end, the top<\/strong>. If we insert a series of data items into a stack and then remove them, the order of the data is reversed. This <\/span>reversing attribute<\/strong> is why stacks are known as <\/span>last in, first out<\/strong> (LIFO) data structures. <\/strong>Figure 7.2 shows a computer stack which also indicates that an insertion at the Top into this restricted list is called Push and deletion also at the Top is called POP.<\/span>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n

As already stated we assume that all elements of a stack are homogenous that is they are all of the same type. However the elements are unordered and are placed in the stack in the order in which they are inserted. Multiple Occurrences of the same elements is permitted as per the characteristics of the stack. The stack allows unidirectional access (LIFO(Last in First Out) \/ FILO(First In Last Out)) through the current Stack Top Pointer (Stack_Pointer).<\/p>\r\n \r\n\r\n7.1.2 Conceptual View of a Stack<\/strong>\r\n\r\n \r\n

The main operations associated with the stack are the Push (adding an element) and the Pop (removing an element) operations. Figure 7.3 shows the conceptual view of adding an element without going into the details. The blue plate (an object to be added needs to be provided) is to be added to the stack. The old Top pointed to the orange plate that was then at the top, now after the blue plate has been added the new top points to this plate. Please note that the bottom of the stack does not play any part in the addition process.<\/p>\r\n\r\n<\/div>\r\n

\"\"<\/p>\r\n

Figure 7.4 shows the conceptual view of removing an element without going into the details. The blue plate that is on top of the stack is to be removed from the stack. In this case this is the only element that can be removed. While the old Top pointed to the blue plate that was then at the top, now after the blue plate has been removed the new top points to the orange plate that is now on top. Please note that the bottom of the stack does not play any part in the deletion process.<\/span><\/p>\r\n\r\n

\r\n\r\n \r\n\r\n\"\"\r\n\r\n7.2 Uses of Stack ADT<\/strong>\r\n\r\n \r\n

Stacks are used in many situations especially when there is a need to process elements in a reverse order to the order in which they arrive. This is an important requirement for many problems in the computing world such as using stacks when processing algebraic expressions, using stacks to search a flight map. Another important use of stacks is in tackling recursion. Later we will discuss the applications of stacks in detail.<\/p>\r\n \r\n\r\n7.3 Abstract Data Type - Stack<\/strong>\r\n\r\n \r\n

Let us now look at developing an ADT during the design of a solution to a problem. Consider entering text using a keyboard. Now if we make mistakes then use of\u00a0backspace is required. For example if we first type <\/span>abcd<\/em><\/strong>, and then by mistake type <\/span>d <\/em><\/strong>again and then again, there is need to use two backspaces and then continue to type <\/span>efg<\/em><\/strong>, and then <\/span>g<\/em><\/strong> again by mistake, then again we need to use backspace. The sequence will be as seen in Figure 7.5. As you will realize, the letter typed last is the one to be removed by the backspace. We seek a programming solution to read these keystrokes. This is a direct mapping to a stack where also we delete elements entered last.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

abcddd<-<-<\/strong>efgg<-<\/strong><\/p>\r\n

Figure 7.5 Keystrokes using a Keyboard<\/strong><\/p>\r\n \r\n\r\n7.3.1<\/strong>\u00a0\u00a0\u00a0 Stack ADT<\/strong>\r\n\r\n \r\n

The Stack Abstract Data Type (Stack ADT)<\/em><\/strong> is a collection of data together with the operations on that data. We will now formally define the interface<\/em><\/strong> of the collection. The interface of the collection tells us what we need to know in order to interact with it, i.e. how to use the operations associated with the stack. The stack can be specified by the user by defining<\/p>\r\n \r\n

Max_Items <\/em>- Maximum number of items that might be on the stack and<\/p>\r\n

ItemType<\/em>- Data type of the items on the stack.<\/p>\r\n \r\n\r\n7.3.2<\/strong>\u00a0ADT stack operations<\/strong>\r\n\r\n \r\n

The next step in defining the Stack ADT is to list the set of operations associated with the ADT. In this section we will list all the operations generally associated with stacks. However we have to remember that the actual set of operations depend on the application for which the Stack ADT will be used and therefore the operations necessary for that application.<\/p>\r\n \r\n

The first operation associated with any ADT is the creation of an empty ADT. Therefore we will first define the operation of creating an empty Stack. In some cases we may want to destroy the entire stack and hence that is the next operation we will define. A very important operation for many applications of stack is to have an operation to check whether a stack is empty. Then the stack will normally be associated with operations to add and remove elements from it. Finally there may be an operation to retrieve the top element from the stack without removing it. From the ADT perspective a program can use a stack independently of the stack\u2019s implementation.<\/p>\r\n \r\n\r\nNow let us describe in a little more in detail four important operations associated with the stack. They are:\r\n\r\n \r\n