To do: queue implemented as an array: circular and fixed-sized

A stack is a basic data structure that can be logically thought of as a linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack. The basic concept can be illustrated by thinking of your data set as a stack of plates or books where you can only take the top item of the stack in order to remove things from it. This structure is used all throughout programming.

The basic implementation of a stack is also called a LIFO (Last In First Out) to demonstrate the way it accesses data, since as we will see there are various variations of stack implementations.

There are basically three operations that can be performed on stacks. They are1) inserting an item into a stack (push).2) deleting an item from the stack (pop).3) displaying the contents of the stack (peek or top).

Note: Depending on the language and implementation the data structure may share the name with an abstract data type that support all of the data structure characteristics.

Below are some of operations astack data type normally supports:

The basic linked list implementation is one of the easiest stack implementations you can do. Structurally it is a linked list.

type Stack<item_type>  data list:Singly Linked List<item_type>"stack follows the LIFO (last in first out) operation""queue follows the FIFO (first in first out) operation"  constructor()    list := new Singly-Linked-List()  end constructor

Most operations are implemented by passing them through to the underlying linked list.When you want topush something onto the list, you simply add it to the front of the linked list. The previous top is then "next" from the item being added and the list's front pointer points to the new item.

  method push(new_item:item_type)    list.prepend(new_item)  end method

To look at thetop item, you just examine the first item in the linked list.

  method top():item_type    return list.get-begin().get-value()  end method

When you want topop something off the list, simply remove the first item from the linked list.

  method pop()    list.remove-first()  end method

A check for emptiness is easy. Just check if the list is empty.

  method is-empty():Boolean    return list.is-empty()  end method

A check for full is simple. Linked lists are considered to be limitless in size.

  method is-full():Boolean    return False  end method

A check for the size is again passed through to the list.

  method get-size():Integer    return list.get-size()  end methodend type

A real Stack implementation in a published library would probably re-implement the linked list in order to squeeze the last bit of performance out of the implementation by leaving out unneeded functionality. The above implementation gives you the ideas involved, and any optimization you need can be accomplished by inlining the linked list code.

In a linked list, accessing the first element is an${\displaystyle O(1)}$ operation.The list contains a pointer that checks for empty/fullness as done here are also${\displaystyle O(1)}$(depending on what time/space tradeoff is made). Most of the time, users of a Stack do not use thegetSize() operation, and so a bit of space can be saved by not optimizing it.

Since all operations are at the top of the stack, the array implementation is now much, much better.

  public class StackArray implements Stack  {      protected int top;      protected Object[] data;     ...  }

The array implementation keeps the bottom of the stack at the beginning of the array. It grows toward the end of the array. The only problem is if you attempt to push an element when the array is full. If so

   Assert.pre(!isFull(),"Stack is not full.");

will fail, raising an exception. Thus it makes more sense to implement with Vector (see StackVector) to allow unbounded growth (at cost of occasional O(n) delays).

Complexity:

All operations are O(1) with exception of occasional push and clear, which should replace all entries by null in order to let them be garbage-collected. Array implementation does not replace null entries. The Vector implementation does...

Using stacks, we can solve many applications, some of which are listed below.

The logic for transforming a decimal number into a binary number is as follows:

    * Read a number    * Iteration (while number is greater than zero)              1. Find out the remainder after dividing the number by 2              2. Print the remainder              3. Divide the number by 2    * End the iteration

However, there is a problem with this logic. Suppose the number whose binary form we want to find is 23. Using this logic, we get the result as 11101, instead of getting 10111.

To solve this problem, we use a stack. We make use of theLIFO property of the stack. Initially wepush the binary digit formed into the stack, instead of printing it directly. After the entire digit has been converted into the binary form, wepop one digit at a time from the stack and print it. Therefore we get the decimal number is converted into its proper binary form.

Algorithm:

   1. Create a stack   2. Enter a decimal number which has to be converted into its equivalent binary form.   3. iteration1 (while number > 0)         3.1 digit = number % 2         3.2 Pushdigit into the stack         3.3 If the stack is full              3.3.1 Print an error              3.3.2 Stop the algorithm         3.4 End theif condition         3.5 Divide the number by 2   4. Enditeration1      5. iteration2 (while stack is not empty)         5.1 Popdigit from the stack         5.2 Print thedigit   6. End iteration2   7. STOP

One of the most interesting applications of stacks can be found in solving a puzzle called Tower of Hanoi. According to an old Brahmin story, the existence of the universe is calculated in terms of the time taken by a number of monks, who are working all the time, to move 64 disks from one pole to another. But there are some rules about how this should be done, which are:

1. You can move only one disk at a time.
2. For temporary storage, a third pole may be used.
3. You cannot place a disk of larger diameter on a disk of smaller diameter.^[1]

Here we assume that A is first tower, B is second tower & C is third tower.

Output : (when there are 3 disks)

Let1 be the smallest disk,2 be the disk of medium size and3 be the largest disk.

Output : (when there are 4 disks)

The C++ code for this solution can be implemented in two ways:

Here we assume that A is first tower, B is second tower & C is third tower. (B is the intermediate)

voidTowersofHanoi(intn,inta,intb,intc){//Move top n disks from tower a to tower b, use tower c for intermediate storage.if(n>0){TowersofHanoi(n-1,a,c,b);//recursioncout<<" Move top disk from tower "<<a<<" to tower "<<b<<endl;//Move n-1 disks from intermediate(b) to the source(a) backTowersofHanoi(n-1,c,b,a);//recursion}}

^[2]

// Global variable, tower [1:3] are three towersarrayStack<int>tower[4];voidTowerofHanoi(intn){// Preprocessor for moveAndShow.for(intd=n;d>0;d--)//initializetower[1].push(d);//add disk d to tower 1moveAndShow(n,1,2,3);/*move n disks from tower 1 to tower 3 using                                       tower 2 as intermediate tower*/}voidmoveAndShow(intn,inta,intb,intc){// Move the top n disks from tower a to tower b showing states.// Use tower c for intermediate storage.if(n>0){moveAndShow(n-1,a,c,b);//recursionintd=tower[a].top();//move a disc from top of tower a to top oftower[a].pop();//tower btower[b].push(d);showState();//show state of 3 towersmoveAndShow(n-1,c,b,a);//recursion}}

However complexity for above written implementations is O(${\displaystyle 2^n}$). So it's obvious that problem can only be solved for small values of n (generally n <= 30). In case of the monks, the number of turns taken to transfer 64 disks, by following the above rules, will be 18,446,744,073,709,551,615; which will surely take a lot of time!!

^[1]

^[2]

Calculators employingreverse Polish notation use a stack structure to hold values. Expressions can be represented in prefix, postfix or infix notations. Conversion from one form of the expression to another form may be accomplished using a stack. Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code. Most of the programming languages arecontext-free languages allowing them to be parsed with stack based machines.

Input: (((2 * 5) - (1 * 2)) / (9 - 7))

Output: 4

Analysis: Five types of input characters

  * Opening bracket  * Numbers  * Operators  * Closing bracket  * New line character

Data structure requirement: A character stack

Algorithm

  1. Read one input character  2. Actions at end of each input     Opening brackets              (2.1)Push into stack and then Go to step (1)     Number                        (2.2)Push into stack and then Go to step (1)     Operator                      (2.3)Push into stack and then Go to step (1)     Closing brackets              (2.4)Pop it from character stack                                   (2.4.1) if it is opening bracket, then discard it, Go to step (1)                                   (2.4.2)Pop is used three times                                           The first popped element is assigned to op2                                           The second popped element is assigned to op                                           The third popped element is assigned to op1                                           Evaluate op1 op op2                                           Convert the result into character andpush into the stack                                           Go to step (2.4)    New line character            (2.5)Pop from stack and print the answerSTOP

Result: The evaluation of the fully parenthesized infix expression is printed on the monitor as follows:

Input String: (((2 * 5) - (1 * 2)) / (9 - 7))

C Program

intmain(intargc,charstructch*charactop;structinteger*integertop;charrd,op;inti=0,op1,op2;charactop=cclearstack();integertop=iclearstack();while(1){rd=argv[1][i++];switch(rd){case'+':case'-':case'/':case'*':case'(':charactop=cpush(charactop,rd);break;case')':integertop=ipop(integertop,&op2);integertop=ipop(integertop,&op1);charactop=cpop(charactop,&op);while(op!='('){integertop=ipush(integertop,eval(op,op1,op2));charactop=cpop(charactop,&op);if(op!='('){integertop=ipop(integertop,&op2);integertop=ipop(integertop,&op1);}}break;case'\0':while(!cemptystack(charactop)){charactop=cpop(charactop,&op);integertop=ipop(integertop,&op2);integertop=ipop(integertop,&op1);integertop=ipush(integertop,eval(op,op1,op2));}integertop=ipop(integertop,&op1);printf("\n The final solution is: %d\n",op1);return0;default:integertop=ipush(integertop,rd-'0');}}}inteval(charop,intop1,intop2){switch(op){case'+':returnop1+op2;case'-':returnop1-op2;case'/':returnop1/op2;case'*':returnop1*op2;}}

Output of the program:

Input entered at the command line: (((2 * 5) - (1 * 2)) / (9 - 7))^[3]

Input: (2 * 5 - 1 * 2) / (11 - 9)

Output: 4

Analysis: There are five types of input characters which are:

               * Opening brackets               * Numbers               * Operators               * Closing brackets               * New line character (\n)

We do not know what to do if an operator is read as an input character.By implementing the priority rule for operators, we have a solution to this problem.

ThePriority rule we should perform comparative priority check if an operator is read, and then push it. If the stacktop contains an operator of prioirty higher than or equal to the priority of the input operator, then wepop it and print it. We keep on perforrming the priority check until thetop of stack either contains an operator of lower priority or if it does not contain an operator.

Data Structure Requirement for this problem: A character stack and an integer stack

Algorithm:

   1. Read an input character   2. Actions that will be performed at the end of each input      Opening brackets              (2.1)Push it into stack and then Go to step (1)        Digit                         (2.2)Push into stack, Go to step (1)      Operator                      (2.3)  Do the comparative priority check                                    (2.3.1) if the character stack'stop contains an operator with equal                                             or higher priority, thenpop it into opPop a number from integer stack into op2Pop another number from integer stack into op1                                           Calculate op1 op op2 andpush the result into the integer                                           stack     Closing brackets              (2.4)Pop from the character stack                                   (2.4.1) if it is an opening bracket, then discard it and Go to                                           step (1)                                   (2.4.2) To op, assign the popped elementPop a number from integer stack and assign it op2Pop another number from integer stack and assign it                                           to op1                                           Calculateop1opop2 and push the result into the integer                                           stack                                           Convert into character andpush into stack                                           Go to the step (2.4)    New line character            (2.5)  Print the result after popping from the stackSTOP

Result: The evaluation of an infix expression that is not fully parenthesized is printed as follows:

Input String: (2 * 5 - 1 * 2) / (11 - 9)

C Program

intmain(intargc,char*argv[]){structch*charactop;structinteger*integertop;charrd,op;inti=0,op1,op2;charactop=cclearstack();integertop=iclearstack();while(1){rd=argv[1][i++];switch(rd){case'+':case'-':case'/':case'*':while((charactop->data!='(')&&(!cemptystack(charactop))){if(priority(rd)>(priority(charactop->data))break;else{charactop=cpop(charactop,&op);integertop=ipop(integertop,&op2);integertop=ipop(integertop,&op1);integertop=ipush(integertop,eval(op,op1,op2);}}charactop=cpush(charactop,rd);break;case'(':charactop=cpush(charactop,rd);break;case')':integertop=ipop(integertop,&op2);integertop=ipop(integertop,&op1);charactop=cpop(charactop,&op);while(op!='('){integertop=ipush(integertop,eval(op,op1,op2);charactop=cpop(charactop,&op);if(op!='('){integertop=ipop(integertop,&op2);integertop=ipop(integertop,&op1);}}break;case'\0':while(!=cemptystack(charactop)){charactop=cpop(charactop,&op);integertop=ipop(integertop,&op2);integertop=ipop(integertop,&op1);integertop=ipush(integertop,eval(op,op1,op2);}integertop=ipop(integertop,&op1);printf("\n The final solution is: %d",op1);return0;default:integertop=ipush(integertop,rd-'0');}}}inteval(charop,intop1,intop2){switch(op){case'+':returnop1+op2;case'-':returnop1-op2;case'/':returnop1/op2;case'*':returnop1*op2;}}intpriority(charop){switch(op){case'^':case'$':return3;case'*':case'/':return2;case'+':case'-':return1;}}

Output of the program:

Input entered at the command line: (2 * 5 - 1 * 2) / (11 - 9)

Output: 4^[3]

Input: x + 6 * ( y + z ) ^ 3

Output:' 4

Analysis: There are three types of input characters

               * Numbers               * Operators               * New line character (\n)

Data structure requirement: A character stack and an integer stack

Algorithm:

   1. Read one character input at a time and keep pushing it into the character stack until the new      line character is reached   2. Performpop from the character stack. If the stack is empty, go to step (3)      Number                        (2.1)Push in to the integer stack and then go to step (1)       Operator                      (2.2)  Assign the operator to opPop a number from  integer stack and assign it to op1Pop another number from integer stack                                           and assign it to op2                                                                          Calculate op1 op op2 and push the output into the integer                                           stack. Go to step (2)                                          3.Pop the result from the integer stack and display the result

Result: The evaluation of prefix expression is printed as follows:

Input String: / - * 2 5 * 1 2 - 11 9

C Program

intmain(intargc,char*argv[]){structch*charactop=NULL;structinteger*integertop=NULL;charrd,op;inti=0,op1,op2;charactop=cclearstack();integertop=iclearstack();rd=argv[1][i];while(rd!='\0'){charactop=cpush(charactop,rd);rd=argv[1][i++];}while(!emptystack(charactop)){charactop=cpop(charactop,rd);switch(rd){case'+':case'-':case'/':case'*':op=rd;integertop=ipop(integertop,&op2);integertop=ipop(integertop,&op1);integertop=ipush(integertop,eval(op,op1,op2));break;default:integertop=ipush(integertop,rd-'0');}}}inteval(charop,intop1,intop2){switch(op){case'+':returnop1+op2;case'-':returnop1-op2;case'/':returnop1/op2;case'*':returnop1*op2;}}intpriority(charop){switch(op){case'^':case'$':return3;case'*':case'/':return2;case'+':case'-':return1;}}

Output of the program:

Input entered at the command line: / - * 2 5 * 1 2 - 11 9

Output: 4^[3]

Input: (((8 + 1) - (7 - 4)) / (11 - 9))

Output: 8 1 + 7 4 - - 11 9 - /

Analysis: There are five types of input characters which are:

               * Opening brackets               * Numbers               * Operators               * Closing brackets               * New line character (\n)

Requirement: A character stack

Algorithm:

   1. Read an character input   2. Actions to be performed at end of each input     Opening brackets              (2.1)Push into stack and then Go to step (1)     Number                        (2.2)  Print and then Go to step (1)     Operator                      (2.3)Push into stack and then Go to step (1)     Closing brackets              (2.4)Pop it from the stack                                   (2.4.1) If it is an operator, print it, Go to step (1)                                   (2.4.2) If the popped element is an opening bracket,                                           discard it and go to step (1)                New line character            (2.5)STOP

Therefore, the final output after conversion of an infix expression to a postfix expression is as follows:

It's a very nice application of stacks. Consider that a freight train hasn railroad cars, each to be left at a different station. They're numbered 1 through n and a freight train visits these stations in order n through 1. Obviously, the railroad cars are labeled by their destination.To facilitate removal of the cars from the train, we must rearrange them in ascending order of their number (i.e., 1 through n). When cars are in this order, they can be detached at each station. We rearrange cars at a shunting yard that hasinput track,output track &k holding tracks between the input & output tracks (i.e.,holding track).

To rearrange cars, we examine the cars on the input from front to back. If the car being examined is the next one in the output arrangement, we move it directly tooutput track. If not, we move it to theholding track and leave it there until it's time to place it to theoutput track. The holding tracks operate in a LIFO manner as the cars enter and leave these tracks from the top. When rearranging cars, only the following moves are permitted:

• A car may be moved from the front (i.e., right end) of the input track to the top of one of theholding tracks or to the left end of the output track.
• A car may be moved from the top of theholding track to the left end of theoutput track.

The figure shows a shunting yard withk = 3, holding tracksH1,H2 andH3, andn = 9. Then cars of the freight train begin in the input track and are to end up in the output track in order 1 throughn from right to left. The cars initially are in the order 5, 8, 1, 7, 4, 2, 9, 6, 3 from back to front. Later cars are rearranged in the desired order.

• Consider the input arrangement from the figure, here we note that car 3 is at the front, so it can't be output yet, as it is to be preceded by cars 1 and 2. So car 3 is detached and moved to holding trackH1.
• The next car 6 can't be output and it is moved to holding trackH2. Because we have to output car 3 before car 6 and this will not be possible if we move car 6 to holding trackH1.
• Now it's obvious that we move car 9 toH3.

The requirement of rearrangement of cars on any holding track is that the cars should be preferred to arrange in ascending order from top to bottom.

• So car 2 is now moved to holding track H1 so that it satisfies the previous statement. If we move car 2 to H2 or H3, then we've no place to move cars 4, 5, 7, or 8.The least restrictions on future car placement arise when the new car λ is moved to the holding track that has a car at its top with smallest label Ψ such that λ < Ψ. We may call it an assignment rule to decide whether a particular car belongs to a specific holding track.
• When car 4 is considered, there are three places to move the car: H1, H2, and H3. The top of these tracks are 2, 6, and 9.So using the aforementioned Assignment rule, we move car 4 to H2.
• Car 7 is moved to H3.
• The next car 1 has the lowest label, so it's moved to the output track.
• Now it's time for cars 2 and 3 to output which are from H1 (in short, all the cars from H1 are appended to car 1 on the output track).

Car 4 is moved to the output track. No other cars can be moved to the output track at this time.

• The next car, car 8, is moved to holding track H1.
• Car 5 is output from the input track. Car 6 is moved to the output track from H2, so is car 7 from H3, car 8 from H1, and car 9 from H3.

Sorting means arranging a group of elements in a particular order. Be it ascending or descending, by cardinality or alphabetical order or variations thereof. The resulting ordering possibilities will only be limited by the type of the source elements.

Quicksort is an algorithm of thedivide and conquer type. In this method, to sort a set of numbers, we reduce it to two smaller sets, and then sort these smaller sets.

This can be explained with the help of the following example:

SupposeA is a list of the following numbers:

In the reduction step, we find the final position of one of the numbers. In this case, let us assume that we have to find the final position of 48, which is the first number in the list.

To accomplish this, we adopt the following method. Begin with the last number, and move from right to left. Compare each number with 48. If the number is smaller than 48, we stop at that number and swap it with 48.

In our case, the number is 24. Hence, we swap 24 and 48.

The numbers 96 and 72 to the right of 48, are greater than 48. Now beginning with 24, scan the numbers in the opposite direction, that is from left to right. Compare every number with 48 until you find a number that is greater than 48.

In this case, it is 60. Therefore we swap 48 and 60.

Note that the numbers 12, 24 and 36 to the left of 48 are all smaller than 48. Now, start scanning numbers from 60, in the right to left direction. As soon as you find lesser number, swap it with 48.

In this case, it is 44. Swap it with 48. The final result is:

Now, beginning with 44, scan the list from left to right, until you find a number greater than 48.

Such a number is 84. Swap it with 48. The final result is:

Now, beginning with 84, traverse the list from right to left, until you reach a number lesser than 48. We do not find such a number before reaching 48. This means that all the numbers in the list have been scanned and compared with 48. Also, we notice that all numbers less than 48 are to the left of it, and all numbers greater than 48, are to its right.

The final partitions look as follows:

Therefore, 48 has been placed in its proper position and now our task is reduced to sorting the two partitions.This above step of creating partitions can be repeated with every partition containing 2 or more elements. As we can process only a single partition at a time, we should be able to keep track of the other partitions, for future processing.

This is done by using twostacks called LOWERBOUND and UPPERBOUND, to temporarily store these partitions. The addresses of the first and last elements of the partitions are pushed into the LOWERBOUND and UPPERBOUND stacks respectively. Now, the above reduction step is applied to the partitions only after its boundary values arepopped from the stack.

We can understand this from the following example:

Take the above list A with 12 elements. The algorithm starts by pushing the boundary values of A, that is 1 and 12 into the LOWERBOUND and UPPERBOUND stacks respectively. Therefore the stacks look as follows:

    LOWERBOUND:  1                   UPPERBOUND:  12

To perform the reduction step, the values of the stack top are popped from the stack. Therefore, both the stacks become empty.

    LOWERBOUND:  {empty}                UPPERBOUND: {empty}

Now, the reduction step causes 48 to be fixed to the 5th position and creates two partitions, one from position 1 to 4 and the other from position 6 to 12. Hence, the values 1 and 6 are pushed into the LOWERBOUND stack and 4 and 12 are pushed into the UPPERBOUND stack.

    LOWERBOUND:  1, 6                   UPPERBOUND: 4, 12

For applying the reduction step again, the values at the stack top are popped. Therefore, the values 6 and 12 are popped. Therefore the stacks look like:

    LOWERBOUND:  1                      UPPERBOUND: 4

The reduction step is now applied to the second partition, that is from the 6th to 12th element.

After the reduction step, 98 is fixed in the 11th position. So, the second partition has only one element. Therefore, we push the upper and lower boundary values of the first partition onto the stack. So, the stacks are as follows:

    LOWERBOUND:  1, 6                   UPPERBOUND:  4, 10

The processing proceeds in the following way and ends when the stacks do not contain any upper and lower bounds of the partition to be processed, and the list gets sorted.

In the stock span problem, we will solve a financial problem with the help of stacks.

Suppose, for a stock, we have a series ofn daily price quotes, thespan of the stock's price on a particular day is defined as the maximum number of consecutive days for which the price of the stock on the current day is less than or equal to its price on that day.

Input: An arrayP withn elements

Output: An arrayS ofn elements such that S[i] is the largest integer k such that k <= i + 1 and P[j] <= P[i] for j = i - k + 1,.....,i

Algorithm:

       1. Initialize an array P which contains the daily prices of the stocks       2. Initialize an array S which will store the span of the stock       3.for i = 0 to i = n - 1               3.1 Initialize k to zero               3.2 Done with afalse condition               3.3repeat                     3.3.1 if (P[i - k] <= P[i]) then                               Increment k by 1                     3.3.2 else                               Done withtrue condition               3.4 Till (k > i) or done with processing                     Assign value of k to S[i] to get the span of the stock       4. Return array S

Now, analyzing this algorithm for running time, we observe:

• We have initialized the array S at the beginning and returned it at the end. This is a constant time operation, hence takesO(n) time
• Therepeat loop is nested within thefor loop. Thefor loop, whose counter isi is executed n times. The statements which are not in the repeat loop, but in the for loop are executedn times. Therefore these statements and the incrementing and condition testing of i takeO(n) time.
• In repetition of i for the outer for loop, the body of the innerrepeat loop is executed maximum i + 1 times. In the worst case, element S[i] is greater than all the previous elements. So, testing for the if condition, the statement after that, as well as testing the until condition, will be performed i + 1 times during iteration i for the outer for loop. Hence, the total time taken by the inner loop isO(n(n + 1)/2), which isO(${\displaystyle n^2}$)

The running time of all these steps is calculated by adding the time taken by all these three steps. The first two terms areO(${\displaystyle n}$) while the last term isO(${\displaystyle n^2}$). Therefore the total running time of the algorithm isO(${\displaystyle n^2}$).

In order to calculate the span more efficiently, we see that the span on a particular day can be easily calculated if we know the closest day beforei, such that the price of the stocks on that day was higher than the price of the stocks on the present day. If there exists such a day, we can represent it by h(i) and initialize h(i) to be -1.

Therefore the span of a particular day is given by the formula,s = i - h(i).

To implement this logic, we use a stack as an abstract data type to store the days i, h(i), h(h(i)) and so on. When we go from day i-1 to i, we pop the days when the price of the stock was less than or equal to p(i) and then push the value of dayi back into the stack.

Here, we assume that the stack is implemented by operations that takeO(1) that is constant time. The algorithm is as follows:

Input: An array P withn elements and an empty stack N

Output: An arrayS ofn elements such that P[i] is the largest integer k such that k <= i + 1 and P[y] <= P[i] for j = i - k + 1,.....,i

Algorithm:

       1. Initialize an array P which contains the daily prices of the stocks       2. Initialize an array S which will store the span of the stock       3.for i = 0 to i = n - 1               3.1 Initialize k to zero               3.2 Done with afalse condition               3.3while not (Stack N is empty or done with processing)                     3.3.1 if ( P[i] >= P[N.top())] then                               Pop a value from stack N                     3.3.2 else                               Done withtrue condition               3.4 if Stack N is empty                        3.4.1 Initialize h to -1               3.5 else                        3.5.1 Initialize stack top to h                        3.5.2 Put the value of h - i in S[i]                        3.5.3 Push the value of i in N        4. Return array S

Now, analyzing this algorithm for running time, we observe:

• We have initialized the array S at the beginning and returned it at the end. This is a constant time operation, hence takesO(n) time
• Thewhile loop is nested within thefor loop. Thefor loop, whose counter isi is executed n times. The statements which are not in the repeat loop, but in the for loop are executedn times. Therefore these statements and the incrementing and condition testing of i takeO(n) time.
• Now, observe the inner while loop duringi repetitions of the for loop. The statementdone with a true condition is done at most once, since it causes an exit from the loop. Let us say that t(i) is the number of times statementPop a value from stack N is executed. So it becomes clear thatwhile not (Stack N is empty or done with processing) is tested maximum t(i) + 1 times.
• Adding the running time of all the operations in the while loop, we get:

${\displaystyle \sum _{i=0}^{n-1}t(i)+1}$

• An element once popped from the stack N is never pushed back into it. Therefore,

${\displaystyle \sum _{i=1}^{n-1}t(i)}$

So, the running time of all the statements in the while loop isO(${\displaystyle n}$)

The running time of all the steps in the algorithm is calculated by adding the time taken by all these steps. The run time of each step isO(${\displaystyle n}$). Hence the running time complexity of this algorithm isO(${\displaystyle n}$).

• Stack (Wikipedia)

A queue is a basic data structure that is used throughout programming. You can think of it as a line in a grocery store. The first one in the line is the first one to be served.Just like a queue.

A queue is also called a FIFO (First In First Out) to demonstrate the way it accesses data.

The basic linked list implementation uses a singly-linked list with a tail pointer to keep track of the back of the queue.

type Queue<item_type>  data list:Singly Linked List<item_type>  data tail:List Iterator<item_type>  constructor()    list := new Singly-Linked-List()    tail := list.get-begin() # null  end constructor

When you want toenqueue something, you simply add it to the back of the item pointed to by the tail pointer. So the previous tail is considered next compared to the item being added and the tail pointer points to the new item. If the list was empty, this doesn't work, since the tail iterator doesn't refer to anything

 method enqueue(new_item:item_type)   if is-empty()     list.prepend(new_item)     tail := list.get-begin()   else     list.insert_after(new_item, tail)     tail.move-next()   end if end method

Thefront item on the queue is just the one referred to by the linked list's head pointer

  method front():item_type    return list.get-begin().get-value()  end method

When you want todequeue something off the list, simply point the head pointer to the previous from head item. The old head item is the one you removed of the list. If the list is now empty, we have to fix the tail iterator.

  method dequeue()    list.remove-first()    if is-empty()      tail := list.get-begin()    end if  end method

A check for emptiness is easy. Just check if the list is empty.

  method is-empty():Boolean    return list.is-empty()  end method

A check for full is simple. Linked lists are considered to be limitless in size.

  method is-full():Boolean    return False  end method

A check for the size is again passed through to the list.

  method get-size():Integer    return list.get-size()  end methodend type

In a linked list, accessing the first element is an${\displaystyle O(1)}$ operation because the list contains a pointer directly to it. Therefore, enqueue, front, and dequeue are a quick${\displaystyle O(1)}$ operations.

The checks for empty/fullness as done here are also${\displaystyle O(1)}$.

The performance ofgetSize() depends on the performance of the corresponding operation in the linked list implementation. It could be either${\displaystyle O(n)}$, or${\displaystyle O(1)}$, depending on what time/space tradeoff is made. Most of the time, users of a Queue do not use thegetSize() operation, and so a bit of space can be saved by not optimizing it.

To do: Discuss priority queues and implementations including sorted lists and various heaps.

• Queue (Wikipedia)

A Deque is a homogeneous list of elements in which insertions and deletion operations are performed on both the ends.
Because of this property it is known as double ended queue i.e. Deque
Deque has two types:

1. Input restricted queue: It allows insertion at only one end
2. Output restricted queue: It allows deletion at only one end

• Deque (Double-Ended QUEue)

• Book:Data Structures

• Wikibooks pages with to-do lists