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 are1)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 stackif 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.
