Stack and Queue

Stack:A stack is a linear list of elements for which all insertions and deletions(usually accesses) are made at only one end of the list.

They are also called as LIFO lists(Last Input First Output).
The operations supported are :

1)IsEmpty(S): returns whether the stack is empty or not.

2)IsFull(S): return whether the stack is full or not.

3)Push(Element X,S): pushes element X on to the top of the stack.

4)Pop(S) : pops an element from the top of the stack on to the output(printing on to the output console isn't necessary though in which case we can define another function Top(S) which gives the top element of the stack).

All the above mentioned operations are of O(1) complexity.



Queue: Queue is a linear list for which all insertions are made at one end and deletions(accesses as well)
are made at the other end of the list and the lists are also called as FIFO lists(First Input First Output ).

The operations supported are

1)IsEmpty(Q):returns whether the queue is empty or not.

2)IsFull(Q): return whether the queue is full or not.

3)Enqueue(Element X,Q): inserts an element X on the rear side of the queue.

4)Dequeue(Q): removes the element pointed to by the front end of the queue.

Similar to a stack ,the operations of the queue are also of O(1) complexity.




Dequeue (double ended queue):A Dequeue is a linear list for which insertions and deletions(accesses as well) occur at the ends.
Analogous to the operations defined for stack and Queue,we can also define some operations for Dequeue.
A simple observation reveals the fact that we can simulate both stack and queue from Dequeue by input and output restrictions.

Having dwelt at such a length on these linear lists,we shall also see some interesting questions based on the simple properties of these linear lists.




Questions

1)How do you implement 2 stacks using only one array.Your stack routines should not indicate an overflow unless every slot in the array is used?


Solution:given an Array,start the first stack S1 from left end and other stack S2 from the right end.while S1 gets grows towards right ,S2 grows towards left.



2)Propose a data structure which supports the stack Push and Pop operations and a third operation FindMin,which returns the smallest element in the data strucuture all in O(1) worst case time.
Solution:Use 2 stacks S1 in to which the elements are pushed and S2 in to which only the current minimum is pushed.
When one needs to insert an element E ,we first push E on to S1 and then access the top element T of S2 which is the minimum before E has been inserted.If only E is less than T , we push E on to S2 .
When one needs to pop an element ,pop the top element of S1 and if this element is also equal to the one on top of S2, then pop it off S2 as well.

Hence the current minimum will always be on top of S2 .Hence along with other normal stack operations, access of minimum element is also possible in O(1).



3)Show how to implement 3 stacks in a single array efficiently?(debated question)

Solution: It is still up for debate ,as we haven't yet figured out the exact solution.We will soon put the best solution for this problem.


4)Consider a empty stack of integers.Let the numbers 1,2,3,4,5,6 be pushed on to this stack only in the order they appeared from left to right.Let S indicates a push and X indicate a pop operation.Can they be permuted in to the order 325641(output) and order 154623?(if a permutation is possible give the order string of operations.
(Hint: SSSSSSXXXXXX outputs 654321)


Solution: SSSXXSSXSXXX outputs 325641.
154623 cannot be output as 2 is pushed much before 3 so can appear only after 3 is output.


5)Given a string containing N S's and N X's where S indicates a push operation and X indicates a pop operation, and with the stack initially empty,Formulate a rule to check whether a given string S of operations is admissible or not (Hint: A string S of operations should always abide by the properties of the stack which in this case only means you never pop an element from an empty stack)


Solution:Given a string of length 2N, we wish to check whether the given string of operations is permissible or not with respect to its functioning on a stack.
The only restricted operation is pop whose prior requirement is that the stack should not be empty.So while traversing the string from left to right,prior to any pop the stack shouldn't be empty which means the no of S's is always greater than or equal to that of X's.
Hence the condition is at any stage on processing of the string,
no of S's > no of X's




6)Find a simple formula for An, the number of permutations the can be printed on an input of n distinct characters to a stack (similar to question 4)


Solution:The numbers are input in the order 1,2,3,...,N.
So the problem amounts to the number of strings each of N pushes(denoted by S) and N pops(denoted by X).
The only criteria to select a string is at any stage of its processing character by character we should have no of S's > no of X's .

This problem is no different from parenthesis problem where N needs to give the no of possible permutations of N parenthesis , which if given by Nth catalan number Cn=(2n)!/((n+1)! n!).
For more insite into catalan number refer this link.
en.wikipedia.org/wiki/Catalan_number





7)Show that it is possible to obtain the permutation P1P2.........Pn from 1,2,.........n using a stack
if and only if there are no indices i < j < k such that Pj < Pk < Pi.



Solution:The solution can be arrived simply by veirfying that among the 6 possible
orders of Pi,Pj,Pk the rest 5 are possible and the ordering in question i.e is Pi,Pj,Pk is not possible.

We leave it to the reader the verification of possibility of the 5 orderings and deal only with proving that the order Pi,Pj,Pk is not possible.

Suppose say that the order Pi,Pj,Pk is possible.
As Pi is the largest and printed first (i < j < k) followed by Pj and Pk,just before the popping of Pi the ordering of these 3 on the stack shall be Pi,Pk followed by Pj(from top).But as j<k ,Pj is printed prior to Pk contradicting the ordering on the stack. Hence this ordering is not possible.



Please Post Your answers to these Questions in the comments section.Your valuable comment might invoke a good discussion and learning process.

More questions to follow on this topic soon!!