Stack

stack
stack is a linear data structure in which elements inserted or removed from only one end, which follows last in first out mechanism. it means the first element inserted is the last one to be removed. figure(1) show examples of such structure :a stack of books and a stack of coins.


figure(1) show example for stack.
stack uses a variable called top which points topmost element in the stack. top is incremented while pushing (inserting) an element in to the stack and decremented while poping (deleting) an element from the stack. figure(2) show push and pop operation on stack

array-based stacks
stack will be maintained by a linear array , a pointer variable top which contains the location of the top element of the stack. when the value of top =-1, will indicate that the stack is empty. because top is assumed to refer to the top element on the stack, push first increments top and then inserts its value into the top position, while pop first removes the top element and then decrements top.

in the figure below, f is physically higher on the page then all the other elements in the stack, so f is the current top element of the stack, if any new elements are added to the stack they are placed on top of f, and if any elements are deletingd, f is the first to be deletingd.

the original idea of the stack is that there is no upper limit on the number of elements that may be kept in a stack. pushing another element onto a stack produces a larger collection of elements. when the stack been implemented in a program, it can be represented as an array, therefore we need to give the maximum size of this stack. so, we need as operation called full (s) (which determines whether a stack is full (overflow) or not to be applied before push operation. on the other hand, if a stack contains a single element and the stack is poped, the resulting stack contains no element and is called an empty stack. therefore, before applying the pop operator to a stack, we must ensure that a stack is not empty. the operation empty (s) determine whether a stack is empty or not.




algorithm 1: push operation ( add element to the stack)
inputs: stack , top (index of the stack), size (the maximum size of the stack), n (the element that will added).
outputs: add n to stack.
begin
if (stack is full) then
write " the stack is overflow"
else
{
top=top+1
stack[top]=n
}
end
algorithm 2: pop operation ( return the top element of the stack)
inputs: stack , top (index of the stack).
outputs: n (the top element of the stack).
begin
if ( stack is empty) then
write " the stack is empty"
else
{
n=stack[top]
top=top-1
}
return n
end

algorithm 3 : print()
begin
if ( stack is empty) then
print ” no element to display”
else
for(i=top i >= 0 i )
print stack[i]
end



ex:
let s, it’s for push item to the stack, and u for pop item from the stack. the set of inputs to the stack are (m, b, y, n, r), what are the outputs from these operations:
a) ssuusususu.
b) sssusuusuu.




ex):
if the set of inputs of a stack are (1,2,3,4,5) .what operations that lead to the output shown below:
a) 2. 4. 5. 3. 1.
b) 4. 2. 3. 1. 5.