{"id":117,"date":"2018-07-18T10:25:02","date_gmt":"2018-07-18T10:25:02","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=117"},"modified":"2018-12-12T08:55:43","modified_gmt":"2018-12-12T08:55:43","slug":"implementation-of-stack-adt","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/implementation-of-stack-adt\/","title":{"rendered":"Implementation of Stack ADT"},"content":{"raw":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/WPNDEFz6xgQ\" target=\"_blank\" rel=\"noopener\"><img src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a>\r\n<\/span><\/div>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Welcome to the e-PG Pathshala Lecture Series on Data Structures.In this module we will talk about the implementation of the Stack ADT.<\/p>\r\n&nbsp;\r\n\r\n<strong>Learning Objectives<\/strong>\r\n\r\n&nbsp;\r\n\r\nThe learning objectives of the introductory module are as follows:\r\n\r\n&nbsp;\r\n\r\n\u2022 To discuss the different implementations of Stack ADT\r\n\r\n\u2022 To explain the array based implementation of stack including growable arrays &amp; multiple stacks\r\n\r\n\u2022 To outline the linked list implementation of Stack\r\n\r\n\u2022 To discuss the implementation of Stack ADT using ADT list\r\n\r\n&nbsp;\r\n\r\n<strong>8.1 Implementation of Stack ADT<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Any list implementation such as arrays could be used to implement a stack as was discussed in the previous module. When using arrays the implementation is <strong>static<\/strong>and thesize of stack is to be fixed and given initially. Another implementation of stacks is linked lists where the stack is dynamicand in general cannever become full. We will then explore the use of ADT list to implement stacks.<\/p>\r\n<img class=\"alignnone size-full wp-image-120 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-33.png\" alt=\"\" width=\"366\" height=\"221\" \/>\r\n\r\n<strong>8.2 Array Implementation of Stack ADT<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">First let us see how to use an array to implement a stack <em>Stack<\/em>. First of all since the implementation is static we need to declare the array size ahead of time. The following are two of the attributes associated with the Stack:<\/p>\r\n\r\n<ul>\r\n \t<li>MaxSize: This is the maximum size of the stack and is the size of the array.<\/li>\r\n \t<li><span style=\"text-align: justify;font-size: 1em\">Top: This is the index of the top element of stack Stack which is the array which stores elements of stack<\/span><\/li>\r\n<\/ul>\r\n<\/div>\r\n<div>\r\n\r\n\u00a0 \u00a0 \u00a0The following are the operations associated with the stack:\r\n<ul>\r\n \t<li>IsEmpty: This returns true if stack is empty, else false<\/li>\r\n \t<li style=\"text-align: justify\">IsFull: This returns true if stack is full, else false.This operation is only defined for Stack ADT when the\u00a0 \u00a0ADT is represented using an array and hence is implementation dependent.<\/li>\r\n \t<li>Top: This returns the element at the top of stack without removing it from the stack<\/li>\r\n \t<li>Push: This adds an element to the top of stack<\/li>\r\n \t<li>Pop: This deletes the element at the top of stack<\/li>\r\n \t<li>DisplayStack: This prints all the data in the stack<\/li>\r\n<\/ul>\r\n<p style=\"text-align: justify\">Now let us see in detail how the above operations are carried out when the stack is represented using an array <strong><em>Stack<\/em><\/strong>. Figure 8.2 shows an array Stack [0,1,\u2026..MaxStack-1] where MaxStack is the maximum size of the stack. The array Stack contains k+1 items of type StackItem Type. The value of Top or index to access the stack in this case is k.<\/p>\r\n<img class=\"alignnone wp-image-121 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-34.png\" alt=\"\" width=\"520\" height=\"171\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>8.2.1 Create Stack<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">For the creation of the Stack the first step is the allocation of a stack array S of size size = Maxsize. Initially we set Top to -1. Thisindicates that the stack is empty.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"alignnone wp-image-122 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-35.png\" alt=\"\" width=\"238\" height=\"73\" \/>\r\n\r\n&nbsp;\r\n\r\nWhen the stack is full, Top will have its maximum value, i.e. Maxsize \u2013 1\r\n\r\n<img class=\"alignnone wp-image-123 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-36.png\" alt=\"\" width=\"252\" height=\"80\" \/>\r\n\r\n<strong>8.2.2 Size of the Stack<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Initially when the stack is empty, Top has a value = -1. In general we add elements from left to right (Figure 8.3). Size of the stack is one more than the value of Top<\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"alignnone size-full wp-image-124 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-37.png\" alt=\"\" width=\"547\" height=\"244\" \/>\r\n\r\n<strong>8.2.3\u00a0\u00a0 Push Stack<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">As we have already discussed, this operation will Pushan element onto the stack by incrementing Top. If the stack is full, it will print the error information Now let us consider an example shown in Figure 8.4.<\/p>\r\n&nbsp;\r\n\r\nThe steps to be followed are as follows:\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>Step 1: <\/strong>The array storing the stack elements may become full.If Stack is full that is if<strong> <em>isFull <\/em><\/strong>is true that is<strong><em> Top=Maxsize -1 <\/em><\/strong>then we signal an error and give an error that the stack is Full or signal a <strong><em>FullStack Exception.<\/em><\/strong> This is a limitation of the array-based implementation since the stack full condition has to be checked explicitly.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>Step 2: <\/strong>Now if isFull is false then we set<strong> <em>Top<\/em> <\/strong><strong><em>\u00de<\/em><\/strong><strong><em>Top+1<\/em><\/strong>. In our example the Top now becomes (2+1) that is 3.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>Step 3: <\/strong>Now we set<strong> <em>S[Top]<\/em> <\/strong>to be the item to be inserted. In our example 77 is pushed and the value at current Top of the stack is 77.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-125 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-38.png\" alt=\"\" width=\"565\" height=\"357\" \/>\r\n\r\n<strong>8.2.4<\/strong>\u00a0<strong>Pop Stack<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">As we have already discussed, this operation will Pop and return the element at the top of the stack. If the stack is empty, it will print the error information. (In this case,\u00a0<span style=\"font-size: 1em;text-align: initial\">the return value is useless). In case the stack is not empty we return the value at the top of the stack and decrement Top. Now let us consider an example shown in Figure 8.5.<\/span><\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n\u00a0 \u00a0 The steps to be followed are as follows:\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>Step 1: <\/strong>If Stack is empty that is if<strong> <em>isEmpty<\/em> <\/strong>is true that is<strong> <em>Top= -1<\/em> <\/strong>then we signal an error and indocate<strong><em>EmptyStackException<\/em><\/strong><\/p>\r\n&nbsp;\r\n\r\n<strong>Step 2: <\/strong>Now if isEmpty is false then we set<strong> <em>Top<\/em> <\/strong><strong><em>\u00de<\/em><\/strong><strong><em>Top -1<\/em><\/strong>. In our example the Top now becomes (2-1) that is 1.\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>Step 3: <\/strong>return<strong> <em>S[Top+1]<\/em> <\/strong>. In our example 86 is returned and the value at current Top of the stack is 75. Here the current Top is pointing to the element 75. However we are returning the element at the location <strong>Top+1<\/strong> which is pointing at the element 86 just deleted from the stack.<\/p>\r\n<img class=\"alignnone size-full wp-image-126 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-39.png\" alt=\"\" width=\"575\" height=\"367\" \/>\r\n\r\n<strong>8.2.5<\/strong>\u00a0 <strong>Stack Top<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">This operation just returns the top element of the stack. Unlike Pop, this function does not remove the top element that is the stack remains unchanged.<\/p>\r\n&nbsp;\r\n\r\n<strong>8.3 Performance and Limitations<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Let us now see the performance of the Stack ADT implemented using arrays. Let <strong><em>n<\/em><\/strong> be the number of elements in the stack then the space used for storing the elements is <strong><em>O<\/em><\/strong>(<strong><em>n<\/em><\/strong>). Each operation runs in time <strong><em>O<\/em><\/strong>(1) and is therefore efficient. As already discussed one limitation is that the maximum size of the stack must be defined a priori and cannot be changed. Trying to push a new element into a full stack causes an implementation-specific exception.<\/p>\r\n&nbsp;\r\n\r\n<strong>8.4 Growable Array<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The case where the array is full is not an exception defined in the Abstract Stack. If the array is filled then we have five options. The first option is to throw an exception.\u00a0<span style=\"font-size: 1em;text-align: initial\">Another way is to ignore the element that is to be pushed or replace the item at the current top of the stack, Yet another method is to put the pushing process to \u201csleep\u201d until something else creates a vacancy. However If dynamic memory is available, the best option is to increase the array capacity.<\/span><\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<strong>\u00a0 \u00a0<\/strong>\r\n\r\n<strong> 8.4.1 Array Capacity<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Now let us consider the case of dynamic memory being available.The problem is that arrays cannot be resized. You can only copy over elements to a new array. In other words, any time we push onto a full stack there is a requirement of <em>n<\/em> copies and the run time is O(<em>n<\/em>). In other words, push is usually O(1)except when new memory is required.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">In a push operation, when the array is full, instead of throwing an exception, we can replace the array with a larger one. An important question in that case is how large should the new array be. How much do we increase the capacity - incremental strategy: increase the size by a constant <em>c<\/em>that isarray_capacity= original capacity +c; or by a multiplethat is array_capacity= original capacity * c. Generally a doubling strategy is common where we double the size of the array.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">Figure 8.6 shows an example where doubling strategy has been used. During the push operation when the array S (size 5) storing the stack elements becomes full that is if <strong><em>isFull<\/em><\/strong> is true that is <strong><em>Top=Maxsize -1,<\/em><\/strong> instead of signaling a stack full condition, a new array A of size 10 (double original size) is created. Now we need to copy the elements from orginal array S to the new array A. This is done as follows:<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong><em>For i<\/em><\/strong><strong><em>\u00ac<\/em><\/strong><strong><em> 0 to Top do A[i] <\/em><\/strong><strong><em>\u00ac<\/em><\/strong><strong><em> S[i] <\/em><\/strong>and now we reassign reference S to the new array A. Then we set Top to Top+1 and insert the new element to S which is now a new array. This array replacement strategy is known as <strong><em>growable array<\/em><\/strong>, since the process can be seen as growing or extending the end of the underlying array in order to accomodate moreelements.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-127 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-40.png\" alt=\"\" width=\"569\" height=\"377\" \/>\r\n\r\n<strong style=\"text-align: initial;font-size: 1em\">8.4.2 Comparison of the Strategies<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"text-align: justify;font-size: 1em\">When we view the incremental strategy from a single operation viewpoint it may seem time consuming since we need to copy all the elements of the original array into the newly created array when a stack overflow occurs. Therefore we need to compare these growable array strategies we analyze the total time <\/span><strong style=\"text-align: justify;font-size: 1em\"><em>T<\/em><\/strong><span style=\"text-align: justify;font-size: 1em\">(<\/span><strong style=\"text-align: justify;font-size: 1em\"><em>n<\/em><\/strong><span style=\"text-align: justify;font-size: 1em\">) needed to perform a series of <\/span><strong style=\"text-align: justify;font-size: 1em\"><em>n<\/em><\/strong><span style=\"text-align: justify;font-size: 1em\"> push operations. Let us assume initially that the empty stack is represented by an array of size 1. The amortized time of a push operation which is the average time taken by a push over the series of operations is <\/span><strong style=\"text-align: justify;font-size: 1em\"><em>T<\/em><\/strong><span style=\"text-align: justify;font-size: 1em\">(<\/span><strong style=\"text-align: justify;font-size: 1em\"><em>n<\/em><\/strong><span style=\"text-align: justify;font-size: 1em\">)\/<\/span><strong style=\"text-align: justify;font-size: 1em\"><em>n.<\/em><\/strong><span style=\"text-align: justify;font-size: 1em\"> To define the average run time, we will introduce the concept of amortized time. If <\/span><em style=\"text-align: justify;font-size: 1em\">n<\/em><span style=\"text-align: justify;font-size: 1em\"> operations requires O(f(<\/span><em style=\"text-align: justify;font-size: 1em\">n<\/em><span style=\"text-align: justify;font-size: 1em\">)), we will say that an individual operation has an amortized run time of O(f(<\/span><em style=\"text-align: justify;font-size: 1em\">n<\/em><span style=\"text-align: justify;font-size: 1em\">)\/<\/span><em style=\"text-align: justify;font-size: 1em\">n<\/em><span style=\"text-align: justify;font-size: 1em\">). Therefore, if inserting <\/span><em style=\"text-align: justify;font-size: 1em\">n<\/em><span style=\"text-align: justify;font-size: 1em\"> objects requires:O(<\/span><em style=\"text-align: justify;font-size: 1em\">n<\/em><span style=\"text-align: justify;font-size: 1em\">2) copies, the amortized time is O(<\/span><em style=\"text-align: justify;font-size: 1em\">n<\/em><span style=\"text-align: justify;font-size: 1em\">) and for ncopies, the amortized time is Q(1). Let us see how we carry out amortized for the incremental and doubling strategy.<\/span><\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n&nbsp;\r\n\r\n<strong>8.4.2.1 Incremental Strategy Analysis<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In the case of incremental strategy let us assume we replace the array<em>k = n<\/em>\/<em>c<\/em> times. Then The total time <em>T<\/em>(<em>n<\/em>) of a series of <em>n<\/em> push operations is proportional to<\/p>\r\n&nbsp;\r\n\r\n<em>T (n) = n + c + <\/em>2<em>c <\/em>+ 3<em>c <\/em>+ 4<em>c <\/em>+<em> \u2026 <\/em>+<em> kc<\/em>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>(<\/strong>the first term n corresponds to n push operations without expansion, the other terms correspond ton\/c or k expansions, where each term needs an additional c operations)<\/p>\r\n&nbsp;\r\n\r\n<em>Rearranging the terms we get<\/em>\r\n\r\n&nbsp;\r\n\r\n<em>T(n) =n + c<\/em>(1 + 2 + 3 + \u2026 +<em> k<\/em>) - factoring out c<em> =n + ck<\/em>(<em>k <\/em>+ 1)\/2 - rewriting 1+2+\u2026+k as<em> k<\/em>(<em>k <\/em>+ 1)\/2\r\n\r\nSince <em>c<\/em> is a constant, <em>T<\/em>(<em>n<\/em>) is <em>O<\/em>(<em>n +k<\/em><sup>2<\/sup>)= <em>O<\/em>(<em>n<\/em>+(<em>n\/c)<\/em><sup>2<\/sup>) that is <em>O<\/em>(<em>n<\/em><sup>2<\/sup>).\r\n<p style=\"text-align: justify\">Therefore the amortized time of 1 push operation is <em>O<\/em>(<em>n<\/em>).<\/p>\r\n&nbsp;\r\n\r\n<strong>8.4.2.2 Doubling Strategy Analysis<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">In the case of doublingstrategy let us assume we replace the array <em>k =<\/em> log2 <em>n<\/em> times Then the total time <em>T<\/em>(<em>n<\/em>) of a series of <em>n<\/em> push operations (Figure 8.7) is proportional to<\/p>\r\n<em>T(n) = <\/em>n+ 1 + 2 + 4 + 8 + \u2026+ 2<sup>k<\/sup>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>(<\/strong>the first term n corresponds to n push operations without expansion<em>and<\/em> the other terms correspond toagain k expansions)<\/p>\r\n<p style=\"text-align: justify\"><em>Rearranging the terms we get<\/em><\/p>\r\n<em>T(n) = <strong>n<\/strong><\/em>+ 2<strong><em>\u00d7<\/em><\/strong>(2<sup><strong><em>k<\/em><\/strong> + 1<\/sup> -1)<em> = 3<strong>n<\/strong> <\/em>-2 =<em> <strong>O<\/strong><\/em>(<strong><em>n<\/em><\/strong>) (geometric series reduces to n \u2013 refer to Figure\r\n\r\n)\r\n\r\n<em>T<\/em>(<em>n<\/em>) is<em> O<\/em>(<em>n<\/em>)\r\n\r\n&nbsp;\r\n\r\nTherefore the amortized time of a push operation is <em>O<\/em>(1)\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"alignnone size-full wp-image-128 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-41.png\" alt=\"\" width=\"237\" height=\"337\" \/>\r\n\r\nNote the difference in worst-case amortized scenarios for various cases (Figure 8.8)\r\n\r\n<img class=\"alignnone size-full wp-image-129 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-42.png\" alt=\"\" width=\"617\" height=\"288\" \/>\r\n\r\n<strong>8.5 Multiple Stacks<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">We can represent two stacks using a single array m (Figure 8.9). When we need more than two stacks, we can:<\/p>\r\n\r\n<ul>\r\n \t<li>Use a fixed partition for each stack.<\/li>\r\n \t<li>Use a variable partition for each stack. When stack is full<\/li>\r\n<\/ul>\r\n<ol>\r\n \t<li>Find a larger, free space.<\/li>\r\n \t<li>Move the related stacks around.<\/li>\r\n<\/ol>\r\n<p style=\"text-align: justify\">When an array represents two stacks, the bottoms of the two stacks start from two ends of the array and grow towards each other. The first stack Stack1 starts from m[0] and grows in the direction of m[n-1] while the second stack Stack2 starts from m[n-1] and grows in the direction of m[0].<\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<strong>m[0], m[1],<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026..<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>m[n-2],m[n-1]<\/strong>\r\n\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-130 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-43.png\" alt=\"\" width=\"648\" height=\"481\" \/>\r\n\r\n&nbsp;\r\n\r\nInitially, boundary[i]=top[i].\r\n\r\n<\/div>\r\n<img class=\"alignnone size-full wp-image-131 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-44.png\" alt=\"\" width=\"649\" height=\"250\" \/>\r\n<div>\r\n<p style=\"text-align: justify\">The same concept can be extended to more than two stacks. Let us assume we want to represent n stacks. The memory is divided into n equal segments (Figure 8.10). We define boundary to pointtothepositionimmediately totheleftofthebottomelement while top points tothetopelement.<\/p>\r\n&nbsp;\r\n\r\nAll stacks are empty and divided into roughly equal segments.\r\n\r\ninitially\r\n\r\n<em>boundary<\/em>[<em> i<\/em>]=<em> top <\/em>[<em> i<\/em>]=<em> m <\/em>\/<em> n<\/em>*<em>i<\/em>-1\r\n\r\n<\/div>\r\n<span style=\"text-align: initial;font-size: 1em\">\u00a0 \u00a0If<\/span><em style=\"text-align: initial;font-size: 1em\">i-<\/em><span style=\"text-align: initial;font-size: 1em\"> thstackisemptythen<\/span><em style=\"text-align: initial;font-size: 1em\">top<\/em><span style=\"text-align: initial;font-size: 1em\"> [ <\/span><em style=\"text-align: initial;font-size: 1em\">i<\/em><span style=\"text-align: initial;font-size: 1em\">] = <\/span><em style=\"text-align: initial;font-size: 1em\">boundary<\/em><span style=\"text-align: initial;font-size: 1em\"> [ <\/span><em style=\"text-align: initial;font-size: 1em\">i<\/em><span style=\"text-align: initial;font-size: 1em\">]<\/span>\r\n\r\n<span style=\"text-align: initial;font-size: 1em\"> If<\/span><em style=\"text-align: initial;font-size: 1em\">i<\/em><span style=\"text-align: initial;font-size: 1em\">\u2013thstackisfullthen<\/span><em style=\"text-align: initial;font-size: 1em\">top<\/em><span style=\"text-align: initial;font-size: 1em\"> [ <\/span><em style=\"text-align: initial;font-size: 1em\">i<\/em><span style=\"text-align: initial;font-size: 1em\">] = <\/span><em style=\"text-align: initial;font-size: 1em\">boundary<\/em><span style=\"text-align: initial;font-size: 1em\"> [ <\/span><em style=\"text-align: initial;font-size: 1em\">i<\/em><span style=\"text-align: initial;font-size: 1em\">+1]<\/span>\r\n<div>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Now let us consider a Push operation into one of the n stacks say ith stack. Now a Stack full condition will be signaled when the memory allocated to the ith stack is filled. This condition happens when stack i meets stack i+1 which will be signaled when top of ith stack t[i] = bottom of stack i+I that is b[i+1] (Figure 8.11)<\/p>\r\n<img class=\"alignnone size-full wp-image-132 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-45.png\" alt=\"\" width=\"562\" height=\"260\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>Stack Full Condition<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">When the stack full condition of ith stack is signaled in this way there may be space available in the array which can be used to grow the segment allocated to the ith stack. In other words, if there is space available (in memory), it should shift the stacks so that space is allocated to the full stack. For this to take place we<\/p>\r\n\r\n<ul>\r\n \t<li style=\"text-align: justify\">Determine the least, j, i&lt; j &lt; n, such that there is free space between stacks j and j+1. If there is such a j, then move stacks i+1, i+2, \u2026, j one position to the right.<\/li>\r\n \t<li style=\"text-align: justify\">If there is no such j, then look to the left of stack i. Find the largest j such that 0 \u00a3 j &lt;i and there is space between stacks j and j+1. If there is such a j, then move stacks j+1, j+2, \u2026,i one position to the left.<\/li>\r\n<\/ul>\r\n<strong>\u00a0 \u00a0 Find j, i&lt; j &lt; nor, 0 <\/strong>\u00a3<strong> j &lt;i<\/strong>\r\n\r\n<strong>such that top[j] &lt; boundary[j+1]<\/strong>\r\n\r\n&nbsp;\r\n\r\nIn the worst case, the function, stack_full, has a time complexity of O(Size of Array).\r\n\r\n&nbsp;\r\n\r\n<strong>8.6 Linked List Strategy<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The Stack ADT can be represented using Linked List or Pointer implementation as shown in Figure 8.12. This essentially means that though the elements of the stack are logically stored adjacent to each other, they are physically stored in locations that may be far apart but are linked together through the use of pointers.<\/p>\r\n\r\n<\/div>\r\n<div>\r\n\r\n<img class=\"alignnone size-full wp-image-133 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-46.png\" alt=\"\" width=\"442\" height=\"279\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">A Pointer-Based Implementation of the ADT Stack is required when the stack needs to grow and shrink dynamically. In this case Top is a reference to the head of a linked list of items and free nodes need to supplied during Push operation and to return free nodes during Pop operation. Now let us discuss the linked list implementation of various operations of Stack ADT.<\/p>\r\n&nbsp;\r\n\r\n<strong>8.6.1Create Stack<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The various steps in the creation of a stack using linked list representation is shown in Figure 8.13. The first step in the creation of stack is the allocation of memory for the Stack head. Here pnew is the pointer to the Stack head and the variable Count is set to 0 while the variable Top is set to Null, Now we return Stack Head pnew as the newly created Stack.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-134 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-47.png\" alt=\"\" width=\"413\" height=\"233\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>8.6.2 Push Operation<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The push operation is explained with an example (Push(Stack 45)) and illustrated in Figure 8.14. Let us assume that the Stack originally has 4 elements with the <strong><em>Top<\/em><\/strong> pointing to element <strong><em>34<\/em><\/strong>. The first step for the Push operation is the allocation of a node <strong><em>pnew<\/em><\/strong> with two components <strong><em>Data<\/em><\/strong> and <strong><em>Link<\/em><\/strong>. The next step is setting the <strong><em>Data<\/em><\/strong> component of the new node as <strong><em>45<\/em><\/strong>, the element to be inserted. Now set the <strong><em>Link<\/em><\/strong> component of the node to the value of <strong><em>Top.<\/em><\/strong> Now what is left is to change the value of <strong><em>Top <\/em><\/strong>to the new node<strong><em> pnew<\/em><\/strong>and to increment<strong><em> Count<\/em><\/strong>to 5.<\/p>\r\n\r\n<\/div>\r\n<img class=\"alignnone size-full wp-image-135 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-48.png\" alt=\"\" width=\"614\" height=\"275\" \/>\r\n<div>\r\n\r\n<strong>\u00a0 \u00a0 8.6.3 Pop Operation<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The pop operation is explained with an example (Pop(Stack)) and illustrated in Figure 8.15. Let us assume that the Stack originally has 4 elements with the <strong><em>Top<\/em><\/strong> pointing to element <strong><em>45<\/em><\/strong>. The first step for the Pop operation is checking if the Stack is empty in which case the Pop operation signals a false value indicating that the operation is notpossible. Now we set <strong><em>Dataout<\/em><\/strong>to the <strong><em>Data<\/em><\/strong>component of the<strong><em>Top<\/em><\/strong>.<\/p>\r\n&nbsp;\r\n\r\n<img class=\"alignnone size-full wp-image-136 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-49.png\" alt=\"\" width=\"529\" height=\"348\" \/>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Now we modify Top to point to the element that <strong><em>Top<\/em><\/strong> pointed to <strong><em>(Top.Link)<\/em><\/strong>The next and final step is decrementing the value of <strong><em>Count<\/em><\/strong> to 3.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong style=\"text-align: initial;font-size: 1em\">\u00a08.6.4 Other Operations<\/strong><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">There are other operations (Figure 8.16) that are associated with the Stack. These operations could be<\/span><\/p>\r\n\r\n<\/div>\r\n<div>\r\n<ul>\r\n \t<li style=\"text-align: justify\">Checking whether the Stack is empty where we need to just check whether Count is 0.<\/li>\r\n \t<li style=\"text-align: justify\">Retrieving the top element of the stack where we need to check whether the Stack is empty else\u00a0 \u00a0 \u00a0 StackTop is Top.Data.<\/li>\r\n \t<li style=\"text-align: justify\">StackCount just returns Stack.Count.<\/li>\r\n \t<li style=\"text-align: justify\">DestoryStack will Pop Top Node until Stack is empty and then we delete Stack Head.<\/li>\r\n \t<li style=\"text-align: justify\">Finally we can check if the stack is full \u2013 which will be signalled when we run out of memory although this operation is not normally specified for Linked List implementation of Stack ADT.<\/li>\r\n<\/ul>\r\n<img class=\"alignnone size-full wp-image-137 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-50.png\" alt=\"\" width=\"511\" height=\"341\" \/>\r\n\r\n&nbsp;\r\n\r\n<strong>8.7 Using List ADT<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Another important implementation of the Stack ADT is using another ADT \u2013 the List ADT. This implementation is also important since this is an example of the usage of the List ADT. Now if we assume that the item in position 1 is the top of the Stack. In this case Figure 8.18. Here instead of assuming that stack grows from 1 to n we assume that it grows towards n. Therefore the adtlist used here is doing insertions and deletions at the front only.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: center\"><strong>List aList; \/\/ list of stack items<\/strong><\/p>\r\n<p style=\"text-align: center\"><strong>isEmpty(Stack)<\/strong><\/p>\r\n<p style=\"text-align: center\"><strong>returnaList.isEmpty();<\/strong><\/p>\r\n<p style=\"text-align: center\"><strong>push(Stack,newItem)<\/strong><\/p>\r\n<p style=\"text-align: center\"><strong>returnaList.insert(1,newItem)<\/strong><\/p>\r\n<p style=\"text-align: center\"><strong>pop(Stack)<\/strong><\/p>\r\n<p style=\"text-align: center\"><strong>if (aList.retrieve(1,stackTop) return aList.remove(1); Else return <\/strong>false<strong>;<\/strong><\/p>\r\n<p style=\"text-align: center\"><strong>Figure 8.18 (a) Stack ADT using List ADT<\/strong><\/p>\r\n\r\n<\/div>\r\n<img class=\"alignnone size-full wp-image-138 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-51.png\" alt=\"\" width=\"381\" height=\"312\" \/>\r\n\r\n<strong>8.8 Comparing Implementations<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">An array-based implementationneeds the size of the stack to be fixed and therefore the push operation cannot add an item to the stack if the stack\u2019s size limit has been reached. On the hand, the size of the stack is dynamic in a pointer-based implementationwhere wedo not put a limit on the size of the stack. Another implementation is the use of the ADT list implemented say for example using pointers.Th ADT list approach reuses an already implemented class. This is much simpler to write and saves time.<\/p>\r\n&nbsp;\r\n\r\n<strong>Summary<\/strong>\r\n<ul>\r\n \t<li>Explained the three different implementations of Stack ADT<\/li>\r\n \t<li>Discussed array implementation of stack<\/li>\r\n \t<li>Explained the linked list implementation of stacks<\/li>\r\n \t<li>Outlined the ADT list based implementation of stacks<\/li>\r\n<\/ul>\r\n<table>\r\n<tbody>\r\n<tr>\r\n<td><strong>you can view video on Implementation of Stack ADT<\/strong><\/td>\r\n<td><a href=\"https:\/\/youtu.be\/WPNDEFz6xgQ\" target=\"_blank\" rel=\"noopener\"><img class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\r\n<\/tr>\r\n<\/tbody>\r\n<\/table>\r\n\r\n<img class=\" wp-image-140 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-53.png\" alt=\"\" width=\"802\" height=\"630\" \/>","rendered":"<div><span style=\"float: right\"><a href=\"https:\/\/youtu.be\/WPNDEFz6xgQ\" target=\"_blank\" rel=\"noopener\"><img decoding=\"async\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"epgp books\" width=\"75px\" height=\"75px;\" \/><\/a><br \/>\n<\/span><\/div>\n<div>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Welcome to the e-PG Pathshala Lecture Series on Data Structures.In this module we will talk about the implementation of the Stack ADT.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Learning Objectives<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>The learning objectives of the introductory module are as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>\u2022 To discuss the different implementations of Stack ADT<\/p>\n<p>\u2022 To explain the array based implementation of stack including growable arrays &amp; multiple stacks<\/p>\n<p>\u2022 To outline the linked list implementation of Stack<\/p>\n<p>\u2022 To discuss the implementation of Stack ADT using ADT list<\/p>\n<p>&nbsp;<\/p>\n<p><strong>8.1 Implementation of Stack ADT<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Any list implementation such as arrays could be used to implement a stack as was discussed in the previous module. When using arrays the implementation is <strong>static<\/strong>and thesize of stack is to be fixed and given initially. Another implementation of stacks is linked lists where the stack is dynamicand in general cannever become full. We will then explore the use of ADT list to implement stacks.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-120 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-33.png\" alt=\"\" width=\"366\" height=\"221\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-33.png 366w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-33-300x181.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-33-65x39.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-33-225x136.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-33-350x211.png 350w\" sizes=\"auto, (max-width: 366px) 100vw, 366px\" \/><\/p>\n<p><strong>8.2 Array Implementation of Stack ADT<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">First let us see how to use an array to implement a stack <em>Stack<\/em>. First of all since the implementation is static we need to declare the array size ahead of time. The following are two of the attributes associated with the Stack:<\/p>\n<ul>\n<li>MaxSize: This is the maximum size of the stack and is the size of the array.<\/li>\n<li><span style=\"text-align: justify;font-size: 1em\">Top: This is the index of the top element of stack Stack which is the array which stores elements of stack<\/span><\/li>\n<\/ul>\n<\/div>\n<div>\n<p>\u00a0 \u00a0 \u00a0The following are the operations associated with the stack:<\/p>\n<ul>\n<li>IsEmpty: This returns true if stack is empty, else false<\/li>\n<li style=\"text-align: justify\">IsFull: This returns true if stack is full, else false.This operation is only defined for Stack ADT when the\u00a0 \u00a0ADT is represented using an array and hence is implementation dependent.<\/li>\n<li>Top: This returns the element at the top of stack without removing it from the stack<\/li>\n<li>Push: This adds an element to the top of stack<\/li>\n<li>Pop: This deletes the element at the top of stack<\/li>\n<li>DisplayStack: This prints all the data in the stack<\/li>\n<\/ul>\n<p style=\"text-align: justify\">Now let us see in detail how the above operations are carried out when the stack is represented using an array <strong><em>Stack<\/em><\/strong>. Figure 8.2 shows an array Stack [0,1,\u2026..MaxStack-1] where MaxStack is the maximum size of the stack. The array Stack contains k+1 items of type StackItem Type. The value of Top or index to access the stack in this case is k.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-121 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-34.png\" alt=\"\" width=\"520\" height=\"171\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-34.png 477w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-34-300x99.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-34-65x21.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-34-225x74.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-34-350x115.png 350w\" sizes=\"auto, (max-width: 520px) 100vw, 520px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>8.2.1 Create Stack<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">For the creation of the Stack the first step is the allocation of a stack array S of size size = Maxsize. Initially we set Top to -1. Thisindicates that the stack is empty.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-122 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-35.png\" alt=\"\" width=\"238\" height=\"73\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-35.png 189w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-35-65x20.png 65w\" sizes=\"auto, (max-width: 238px) 100vw, 238px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>When the stack is full, Top will have its maximum value, i.e. Maxsize \u2013 1<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-123 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-36.png\" alt=\"\" width=\"252\" height=\"80\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-36.png 217w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-36-65x21.png 65w\" sizes=\"auto, (max-width: 252px) 100vw, 252px\" \/><\/p>\n<p><strong>8.2.2 Size of the Stack<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Initially when the stack is empty, Top has a value = -1. In general we add elements from left to right (Figure 8.3). Size of the stack is one more than the value of Top<\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-124 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-37.png\" alt=\"\" width=\"547\" height=\"244\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-37.png 547w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-37-300x134.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-37-65x29.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-37-225x100.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-37-350x156.png 350w\" sizes=\"auto, (max-width: 547px) 100vw, 547px\" \/><\/p>\n<p><strong>8.2.3\u00a0\u00a0 Push Stack<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">As we have already discussed, this operation will Pushan element onto the stack by incrementing Top. If the stack is full, it will print the error information Now let us consider an example shown in Figure 8.4.<\/p>\n<p>&nbsp;<\/p>\n<p>The steps to be followed are as follows:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>Step 1: <\/strong>The array storing the stack elements may become full.If Stack is full that is if<strong> <em>isFull <\/em><\/strong>is true that is<strong><em> Top=Maxsize -1 <\/em><\/strong>then we signal an error and give an error that the stack is Full or signal a <strong><em>FullStack Exception.<\/em><\/strong> This is a limitation of the array-based implementation since the stack full condition has to be checked explicitly.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>Step 2: <\/strong>Now if isFull is false then we set<strong> <em>Top<\/em> <\/strong><strong><em>\u00de<\/em><\/strong><strong><em>Top+1<\/em><\/strong>. In our example the Top now becomes (2+1) that is 3.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>Step 3: <\/strong>Now we set<strong> <em>S[Top]<\/em> <\/strong>to be the item to be inserted. In our example 77 is pushed and the value at current Top of the stack is 77.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-125 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-38.png\" alt=\"\" width=\"565\" height=\"357\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-38.png 565w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-38-300x190.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-38-65x41.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-38-225x142.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-38-350x221.png 350w\" sizes=\"auto, (max-width: 565px) 100vw, 565px\" \/><\/p>\n<p><strong>8.2.4<\/strong>\u00a0<strong>Pop Stack<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">As we have already discussed, this operation will Pop and return the element at the top of the stack. If the stack is empty, it will print the error information. (In this case,\u00a0<span style=\"font-size: 1em;text-align: initial\">the return value is useless). In case the stack is not empty we return the value at the top of the stack and decrement Top. Now let us consider an example shown in Figure 8.5.<\/span><\/p>\n<\/div>\n<div>\n<p>\u00a0 \u00a0 The steps to be followed are as follows:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>Step 1: <\/strong>If Stack is empty that is if<strong> <em>isEmpty<\/em> <\/strong>is true that is<strong> <em>Top= -1<\/em> <\/strong>then we signal an error and indocate<strong><em>EmptyStackException<\/em><\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Step 2: <\/strong>Now if isEmpty is false then we set<strong> <em>Top<\/em> <\/strong><strong><em>\u00de<\/em><\/strong><strong><em>Top -1<\/em><\/strong>. In our example the Top now becomes (2-1) that is 1.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>Step 3: <\/strong>return<strong> <em>S[Top+1]<\/em> <\/strong>. In our example 86 is returned and the value at current Top of the stack is 75. Here the current Top is pointing to the element 75. However we are returning the element at the location <strong>Top+1<\/strong> which is pointing at the element 86 just deleted from the stack.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-126 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-39.png\" alt=\"\" width=\"575\" height=\"367\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-39.png 575w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-39-300x191.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-39-65x41.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-39-225x144.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-39-350x223.png 350w\" sizes=\"auto, (max-width: 575px) 100vw, 575px\" \/><\/p>\n<p><strong>8.2.5<\/strong>\u00a0 <strong>Stack Top<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">This operation just returns the top element of the stack. Unlike Pop, this function does not remove the top element that is the stack remains unchanged.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>8.3 Performance and Limitations<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Let us now see the performance of the Stack ADT implemented using arrays. Let <strong><em>n<\/em><\/strong> be the number of elements in the stack then the space used for storing the elements is <strong><em>O<\/em><\/strong>(<strong><em>n<\/em><\/strong>). Each operation runs in time <strong><em>O<\/em><\/strong>(1) and is therefore efficient. As already discussed one limitation is that the maximum size of the stack must be defined a priori and cannot be changed. Trying to push a new element into a full stack causes an implementation-specific exception.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>8.4 Growable Array<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The case where the array is full is not an exception defined in the Abstract Stack. If the array is filled then we have five options. The first option is to throw an exception.\u00a0<span style=\"font-size: 1em;text-align: initial\">Another way is to ignore the element that is to be pushed or replace the item at the current top of the stack, Yet another method is to put the pushing process to \u201csleep\u201d until something else creates a vacancy. However If dynamic memory is available, the best option is to increase the array capacity.<\/span><\/p>\n<\/div>\n<div>\n<p><strong>\u00a0 \u00a0<\/strong><\/p>\n<p><strong> 8.4.1 Array Capacity<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Now let us consider the case of dynamic memory being available.The problem is that arrays cannot be resized. You can only copy over elements to a new array. In other words, any time we push onto a full stack there is a requirement of <em>n<\/em> copies and the run time is O(<em>n<\/em>). In other words, push is usually O(1)except when new memory is required.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In a push operation, when the array is full, instead of throwing an exception, we can replace the array with a larger one. An important question in that case is how large should the new array be. How much do we increase the capacity &#8211; incremental strategy: increase the size by a constant <em>c<\/em>that isarray_capacity= original capacity +c; or by a multiplethat is array_capacity= original capacity * c. Generally a doubling strategy is common where we double the size of the array.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Figure 8.6 shows an example where doubling strategy has been used. During the push operation when the array S (size 5) storing the stack elements becomes full that is if <strong><em>isFull<\/em><\/strong> is true that is <strong><em>Top=Maxsize -1,<\/em><\/strong> instead of signaling a stack full condition, a new array A of size 10 (double original size) is created. Now we need to copy the elements from orginal array S to the new array A. This is done as follows:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong><em>For i<\/em><\/strong><strong><em>\u00ac<\/em><\/strong><strong><em> 0 to Top do A[i] <\/em><\/strong><strong><em>\u00ac<\/em><\/strong><strong><em> S[i] <\/em><\/strong>and now we reassign reference S to the new array A. Then we set Top to Top+1 and insert the new element to S which is now a new array. This array replacement strategy is known as <strong><em>growable array<\/em><\/strong>, since the process can be seen as growing or extending the end of the underlying array in order to accomodate moreelements.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-127 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-40.png\" alt=\"\" width=\"569\" height=\"377\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-40.png 569w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-40-300x199.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-40-65x43.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-40-225x149.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-40-350x232.png 350w\" sizes=\"auto, (max-width: 569px) 100vw, 569px\" \/><\/p>\n<p><strong style=\"text-align: initial;font-size: 1em\">8.4.2 Comparison of the Strategies<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"text-align: justify;font-size: 1em\">When we view the incremental strategy from a single operation viewpoint it may seem time consuming since we need to copy all the elements of the original array into the newly created array when a stack overflow occurs. Therefore we need to compare these growable array strategies we analyze the total time <\/span><strong style=\"text-align: justify;font-size: 1em\"><em>T<\/em><\/strong><span style=\"text-align: justify;font-size: 1em\">(<\/span><strong style=\"text-align: justify;font-size: 1em\"><em>n<\/em><\/strong><span style=\"text-align: justify;font-size: 1em\">) needed to perform a series of <\/span><strong style=\"text-align: justify;font-size: 1em\"><em>n<\/em><\/strong><span style=\"text-align: justify;font-size: 1em\"> push operations. Let us assume initially that the empty stack is represented by an array of size 1. The amortized time of a push operation which is the average time taken by a push over the series of operations is <\/span><strong style=\"text-align: justify;font-size: 1em\"><em>T<\/em><\/strong><span style=\"text-align: justify;font-size: 1em\">(<\/span><strong style=\"text-align: justify;font-size: 1em\"><em>n<\/em><\/strong><span style=\"text-align: justify;font-size: 1em\">)\/<\/span><strong style=\"text-align: justify;font-size: 1em\"><em>n.<\/em><\/strong><span style=\"text-align: justify;font-size: 1em\"> To define the average run time, we will introduce the concept of amortized time. If <\/span><em style=\"text-align: justify;font-size: 1em\">n<\/em><span style=\"text-align: justify;font-size: 1em\"> operations requires O(f(<\/span><em style=\"text-align: justify;font-size: 1em\">n<\/em><span style=\"text-align: justify;font-size: 1em\">)), we will say that an individual operation has an amortized run time of O(f(<\/span><em style=\"text-align: justify;font-size: 1em\">n<\/em><span style=\"text-align: justify;font-size: 1em\">)\/<\/span><em style=\"text-align: justify;font-size: 1em\">n<\/em><span style=\"text-align: justify;font-size: 1em\">). Therefore, if inserting <\/span><em style=\"text-align: justify;font-size: 1em\">n<\/em><span style=\"text-align: justify;font-size: 1em\"> objects requires:O(<\/span><em style=\"text-align: justify;font-size: 1em\">n<\/em><span style=\"text-align: justify;font-size: 1em\">2) copies, the amortized time is O(<\/span><em style=\"text-align: justify;font-size: 1em\">n<\/em><span style=\"text-align: justify;font-size: 1em\">) and for ncopies, the amortized time is Q(1). Let us see how we carry out amortized for the incremental and doubling strategy.<\/span><\/p>\n<\/div>\n<div>\n<p>&nbsp;<\/p>\n<p><strong>8.4.2.1 Incremental Strategy Analysis<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In the case of incremental strategy let us assume we replace the array<em>k = n<\/em>\/<em>c<\/em> times. Then The total time <em>T<\/em>(<em>n<\/em>) of a series of <em>n<\/em> push operations is proportional to<\/p>\n<p>&nbsp;<\/p>\n<p><em>T (n) = n + c + <\/em>2<em>c <\/em>+ 3<em>c <\/em>+ 4<em>c <\/em>+<em> \u2026 <\/em>+<em> kc<\/em><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>(<\/strong>the first term n corresponds to n push operations without expansion, the other terms correspond ton\/c or k expansions, where each term needs an additional c operations)<\/p>\n<p>&nbsp;<\/p>\n<p><em>Rearranging the terms we get<\/em><\/p>\n<p>&nbsp;<\/p>\n<p><em>T(n) =n + c<\/em>(1 + 2 + 3 + \u2026 +<em> k<\/em>) &#8211; factoring out c<em> =n + ck<\/em>(<em>k <\/em>+ 1)\/2 &#8211; rewriting 1+2+\u2026+k as<em> k<\/em>(<em>k <\/em>+ 1)\/2<\/p>\n<p>Since <em>c<\/em> is a constant, <em>T<\/em>(<em>n<\/em>) is <em>O<\/em>(<em>n +k<\/em><sup>2<\/sup>)= <em>O<\/em>(<em>n<\/em>+(<em>n\/c)<\/em><sup>2<\/sup>) that is <em>O<\/em>(<em>n<\/em><sup>2<\/sup>).<\/p>\n<p style=\"text-align: justify\">Therefore the amortized time of 1 push operation is <em>O<\/em>(<em>n<\/em>).<\/p>\n<p>&nbsp;<\/p>\n<p><strong>8.4.2.2 Doubling Strategy Analysis<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">In the case of doublingstrategy let us assume we replace the array <em>k =<\/em> log2 <em>n<\/em> times Then the total time <em>T<\/em>(<em>n<\/em>) of a series of <em>n<\/em> push operations (Figure 8.7) is proportional to<\/p>\n<p><em>T(n) = <\/em>n+ 1 + 2 + 4 + 8 + \u2026+ 2<sup>k<\/sup><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>(<\/strong>the first term n corresponds to n push operations without expansion<em>and<\/em> the other terms correspond toagain k expansions)<\/p>\n<p style=\"text-align: justify\"><em>Rearranging the terms we get<\/em><\/p>\n<p><em>T(n) = <strong>n<\/strong><\/em>+ 2<strong><em>\u00d7<\/em><\/strong>(2<sup><strong><em>k<\/em><\/strong> + 1<\/sup> -1)<em> = 3<strong>n<\/strong> <\/em>-2 =<em> <strong>O<\/strong><\/em>(<strong><em>n<\/em><\/strong>) (geometric series reduces to n \u2013 refer to Figure<\/p>\n<p>)<\/p>\n<p><em>T<\/em>(<em>n<\/em>) is<em> O<\/em>(<em>n<\/em>)<\/p>\n<p>&nbsp;<\/p>\n<p>Therefore the amortized time of a push operation is <em>O<\/em>(1)<\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-128 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-41.png\" alt=\"\" width=\"237\" height=\"337\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-41.png 237w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-41-211x300.png 211w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-41-65x92.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-41-225x320.png 225w\" sizes=\"auto, (max-width: 237px) 100vw, 237px\" \/><\/p>\n<p>Note the difference in worst-case amortized scenarios for various cases (Figure 8.8)<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-129 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-42.png\" alt=\"\" width=\"617\" height=\"288\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-42.png 617w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-42-300x140.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-42-65x30.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-42-225x105.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-42-350x163.png 350w\" sizes=\"auto, (max-width: 617px) 100vw, 617px\" \/><\/p>\n<p><strong>8.5 Multiple Stacks<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">We can represent two stacks using a single array m (Figure 8.9). When we need more than two stacks, we can:<\/p>\n<ul>\n<li>Use a fixed partition for each stack.<\/li>\n<li>Use a variable partition for each stack. When stack is full<\/li>\n<\/ul>\n<ol>\n<li>Find a larger, free space.<\/li>\n<li>Move the related stacks around.<\/li>\n<\/ol>\n<p style=\"text-align: justify\">When an array represents two stacks, the bottoms of the two stacks start from two ends of the array and grow towards each other. The first stack Stack1 starts from m[0] and grows in the direction of m[n-1] while the second stack Stack2 starts from m[n-1] and grows in the direction of m[0].<\/p>\n<\/div>\n<div>\n<p><strong>m[0], m[1],<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026\u2026..<\/strong>\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong>m[n-2],m[n-1]<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-130 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-43.png\" alt=\"\" width=\"648\" height=\"481\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-43.png 648w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-43-300x223.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-43-65x48.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-43-225x167.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-43-350x260.png 350w\" sizes=\"auto, (max-width: 648px) 100vw, 648px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>Initially, boundary[i]=top[i].<\/p>\n<\/div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-131 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-44.png\" alt=\"\" width=\"649\" height=\"250\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-44.png 649w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-44-300x116.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-44-65x25.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-44-225x87.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-44-350x135.png 350w\" sizes=\"auto, (max-width: 649px) 100vw, 649px\" \/><\/p>\n<div>\n<p style=\"text-align: justify\">The same concept can be extended to more than two stacks. Let us assume we want to represent n stacks. The memory is divided into n equal segments (Figure 8.10). We define boundary to pointtothepositionimmediately totheleftofthebottomelement while top points tothetopelement.<\/p>\n<p>&nbsp;<\/p>\n<p>All stacks are empty and divided into roughly equal segments.<\/p>\n<p>initially<\/p>\n<p><em>boundary<\/em>[<em> i<\/em>]=<em> top <\/em>[<em> i<\/em>]=<em> m <\/em>\/<em> n<\/em>*<em>i<\/em>-1<\/p>\n<\/div>\n<p><span style=\"text-align: initial;font-size: 1em\">\u00a0 \u00a0If<\/span><em style=\"text-align: initial;font-size: 1em\">i-<\/em><span style=\"text-align: initial;font-size: 1em\"> thstackisemptythen<\/span><em style=\"text-align: initial;font-size: 1em\">top<\/em><span style=\"text-align: initial;font-size: 1em\"> [ <\/span><em style=\"text-align: initial;font-size: 1em\">i<\/em><span style=\"text-align: initial;font-size: 1em\">] = <\/span><em style=\"text-align: initial;font-size: 1em\">boundary<\/em><span style=\"text-align: initial;font-size: 1em\"> [ <\/span><em style=\"text-align: initial;font-size: 1em\">i<\/em><span style=\"text-align: initial;font-size: 1em\">]<\/span><\/p>\n<p><span style=\"text-align: initial;font-size: 1em\"> If<\/span><em style=\"text-align: initial;font-size: 1em\">i<\/em><span style=\"text-align: initial;font-size: 1em\">\u2013thstackisfullthen<\/span><em style=\"text-align: initial;font-size: 1em\">top<\/em><span style=\"text-align: initial;font-size: 1em\"> [ <\/span><em style=\"text-align: initial;font-size: 1em\">i<\/em><span style=\"text-align: initial;font-size: 1em\">] = <\/span><em style=\"text-align: initial;font-size: 1em\">boundary<\/em><span style=\"text-align: initial;font-size: 1em\"> [ <\/span><em style=\"text-align: initial;font-size: 1em\">i<\/em><span style=\"text-align: initial;font-size: 1em\">+1]<\/span><\/p>\n<div>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Now let us consider a Push operation into one of the n stacks say ith stack. Now a Stack full condition will be signaled when the memory allocated to the ith stack is filled. This condition happens when stack i meets stack i+1 which will be signaled when top of ith stack t[i] = bottom of stack i+I that is b[i+1] (Figure 8.11)<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-132 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-45.png\" alt=\"\" width=\"562\" height=\"260\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-45.png 562w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-45-300x139.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-45-65x30.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-45-225x104.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-45-350x162.png 350w\" sizes=\"auto, (max-width: 562px) 100vw, 562px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Stack Full Condition<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">When the stack full condition of ith stack is signaled in this way there may be space available in the array which can be used to grow the segment allocated to the ith stack. In other words, if there is space available (in memory), it should shift the stacks so that space is allocated to the full stack. For this to take place we<\/p>\n<ul>\n<li style=\"text-align: justify\">Determine the least, j, i&lt; j &lt; n, such that there is free space between stacks j and j+1. If there is such a j, then move stacks i+1, i+2, \u2026, j one position to the right.<\/li>\n<li style=\"text-align: justify\">If there is no such j, then look to the left of stack i. Find the largest j such that 0 \u00a3 j &lt;i and there is space between stacks j and j+1. If there is such a j, then move stacks j+1, j+2, \u2026,i one position to the left.<\/li>\n<\/ul>\n<p><strong>\u00a0 \u00a0 Find j, i&lt; j &lt; nor, 0 <\/strong>\u00a3<strong> j &lt;i<\/strong><\/p>\n<p><strong>such that top[j] &lt; boundary[j+1]<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>In the worst case, the function, stack_full, has a time complexity of O(Size of Array).<\/p>\n<p>&nbsp;<\/p>\n<p><strong>8.6 Linked List Strategy<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The Stack ADT can be represented using Linked List or Pointer implementation as shown in Figure 8.12. This essentially means that though the elements of the stack are logically stored adjacent to each other, they are physically stored in locations that may be far apart but are linked together through the use of pointers.<\/p>\n<\/div>\n<div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-133 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-46.png\" alt=\"\" width=\"442\" height=\"279\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-46.png 442w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-46-300x189.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-46-65x41.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-46-225x142.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-46-350x221.png 350w\" sizes=\"auto, (max-width: 442px) 100vw, 442px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">A Pointer-Based Implementation of the ADT Stack is required when the stack needs to grow and shrink dynamically. In this case Top is a reference to the head of a linked list of items and free nodes need to supplied during Push operation and to return free nodes during Pop operation. Now let us discuss the linked list implementation of various operations of Stack ADT.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>8.6.1Create Stack<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The various steps in the creation of a stack using linked list representation is shown in Figure 8.13. The first step in the creation of stack is the allocation of memory for the Stack head. Here pnew is the pointer to the Stack head and the variable Count is set to 0 while the variable Top is set to Null, Now we return Stack Head pnew as the newly created Stack.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-134 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-47.png\" alt=\"\" width=\"413\" height=\"233\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-47.png 413w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-47-300x169.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-47-65x37.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-47-225x127.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-47-350x197.png 350w\" sizes=\"auto, (max-width: 413px) 100vw, 413px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>8.6.2 Push Operation<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The push operation is explained with an example (Push(Stack 45)) and illustrated in Figure 8.14. Let us assume that the Stack originally has 4 elements with the <strong><em>Top<\/em><\/strong> pointing to element <strong><em>34<\/em><\/strong>. The first step for the Push operation is the allocation of a node <strong><em>pnew<\/em><\/strong> with two components <strong><em>Data<\/em><\/strong> and <strong><em>Link<\/em><\/strong>. The next step is setting the <strong><em>Data<\/em><\/strong> component of the new node as <strong><em>45<\/em><\/strong>, the element to be inserted. Now set the <strong><em>Link<\/em><\/strong> component of the node to the value of <strong><em>Top.<\/em><\/strong> Now what is left is to change the value of <strong><em>Top <\/em><\/strong>to the new node<strong><em> pnew<\/em><\/strong>and to increment<strong><em> Count<\/em><\/strong>to 5.<\/p>\n<\/div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-135 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-48.png\" alt=\"\" width=\"614\" height=\"275\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-48.png 614w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-48-300x134.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-48-65x29.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-48-225x101.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-48-350x157.png 350w\" sizes=\"auto, (max-width: 614px) 100vw, 614px\" \/><\/p>\n<div>\n<p><strong>\u00a0 \u00a0 8.6.3 Pop Operation<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The pop operation is explained with an example (Pop(Stack)) and illustrated in Figure 8.15. Let us assume that the Stack originally has 4 elements with the <strong><em>Top<\/em><\/strong> pointing to element <strong><em>45<\/em><\/strong>. The first step for the Pop operation is checking if the Stack is empty in which case the Pop operation signals a false value indicating that the operation is notpossible. Now we set <strong><em>Dataout<\/em><\/strong>to the <strong><em>Data<\/em><\/strong>component of the<strong><em>Top<\/em><\/strong>.<\/p>\n<p>&nbsp;<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-136 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-49.png\" alt=\"\" width=\"529\" height=\"348\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-49.png 529w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-49-300x197.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-49-65x43.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-49-225x148.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-49-350x230.png 350w\" sizes=\"auto, (max-width: 529px) 100vw, 529px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Now we modify Top to point to the element that <strong><em>Top<\/em><\/strong> pointed to <strong><em>(Top.Link)<\/em><\/strong>The next and final step is decrementing the value of <strong><em>Count<\/em><\/strong> to 3.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong style=\"text-align: initial;font-size: 1em\">\u00a08.6.4 Other Operations<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><span style=\"font-size: 1em\">There are other operations (Figure 8.16) that are associated with the Stack. These operations could be<\/span><\/p>\n<\/div>\n<div>\n<ul>\n<li style=\"text-align: justify\">Checking whether the Stack is empty where we need to just check whether Count is 0.<\/li>\n<li style=\"text-align: justify\">Retrieving the top element of the stack where we need to check whether the Stack is empty else\u00a0 \u00a0 \u00a0 StackTop is Top.Data.<\/li>\n<li style=\"text-align: justify\">StackCount just returns Stack.Count.<\/li>\n<li style=\"text-align: justify\">DestoryStack will Pop Top Node until Stack is empty and then we delete Stack Head.<\/li>\n<li style=\"text-align: justify\">Finally we can check if the stack is full \u2013 which will be signalled when we run out of memory although this operation is not normally specified for Linked List implementation of Stack ADT.<\/li>\n<\/ul>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-137 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-50.png\" alt=\"\" width=\"511\" height=\"341\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-50.png 511w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-50-300x200.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-50-65x43.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-50-225x150.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-50-350x234.png 350w\" sizes=\"auto, (max-width: 511px) 100vw, 511px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><strong>8.7 Using List ADT<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Another important implementation of the Stack ADT is using another ADT \u2013 the List ADT. This implementation is also important since this is an example of the usage of the List ADT. Now if we assume that the item in position 1 is the top of the Stack. In this case Figure 8.18. Here instead of assuming that stack grows from 1 to n we assume that it grows towards n. Therefore the adtlist used here is doing insertions and deletions at the front only.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><strong>List aList; \/\/ list of stack items<\/strong><\/p>\n<p style=\"text-align: center\"><strong>isEmpty(Stack)<\/strong><\/p>\n<p style=\"text-align: center\"><strong>returnaList.isEmpty();<\/strong><\/p>\n<p style=\"text-align: center\"><strong>push(Stack,newItem)<\/strong><\/p>\n<p style=\"text-align: center\"><strong>returnaList.insert(1,newItem)<\/strong><\/p>\n<p style=\"text-align: center\"><strong>pop(Stack)<\/strong><\/p>\n<p style=\"text-align: center\"><strong>if (aList.retrieve(1,stackTop) return aList.remove(1); Else return <\/strong>false<strong>;<\/strong><\/p>\n<p style=\"text-align: center\"><strong>Figure 8.18 (a) Stack ADT using List ADT<\/strong><\/p>\n<\/div>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-138 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-51.png\" alt=\"\" width=\"381\" height=\"312\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-51.png 381w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-51-300x246.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-51-65x53.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-51-225x184.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-51-350x287.png 350w\" sizes=\"auto, (max-width: 381px) 100vw, 381px\" \/><\/p>\n<p><strong>8.8 Comparing Implementations<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">An array-based implementationneeds the size of the stack to be fixed and therefore the push operation cannot add an item to the stack if the stack\u2019s size limit has been reached. On the hand, the size of the stack is dynamic in a pointer-based implementationwhere wedo not put a limit on the size of the stack. Another implementation is the use of the ADT list implemented say for example using pointers.Th ADT list approach reuses an already implemented class. This is much simpler to write and saves time.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Summary<\/strong><\/p>\n<ul>\n<li>Explained the three different implementations of Stack ADT<\/li>\n<li>Discussed array implementation of stack<\/li>\n<li>Explained the linked list implementation of stacks<\/li>\n<li>Outlined the ADT list based implementation of stacks<\/li>\n<\/ul>\n<table>\n<tbody>\n<tr>\n<td><strong>you can view video on Implementation of Stack ADT<\/strong><\/td>\n<td><a href=\"https:\/\/youtu.be\/WPNDEFz6xgQ\" target=\"_blank\" rel=\"noopener\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-120\" src=\"http:\/\/epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/2018\/11\/download.png\" alt=\"\" width=\"36\" height=\"36\" \/><\/a><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-140 aligncenter\" src=\"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/45\/2018\/07\/1-53.png\" alt=\"\" width=\"802\" height=\"630\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-53.png 713w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-53-300x236.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-53-65x51.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-53-225x177.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-content\/uploads\/sites\/45\/2018\/07\/1-53-350x275.png 350w\" sizes=\"auto, (max-width: 802px) 100vw, 802px\" \/><\/p>\n","protected":false},"author":3,"menu_order":8,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-t-v-geetha"],"pb_section_license":""},"chapter-type":[],"contributor":[59],"license":[],"class_list":["post-117","chapter","type-chapter","status-publish","hentry","contributor-dr-t-v-geetha"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/117","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/users\/3"}],"version-history":[{"count":9,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/117\/revisions"}],"predecessor-version":[{"id":913,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/117\/revisions\/913"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapters\/117\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/media?parent=117"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/pressbooks\/v2\/chapter-type?post=117"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/contributor?post=117"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/wp-json\/wp\/v2\/license?post=117"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}