Tip:
Highlight text to annotate it
X
In our previous lesson we introduced you to stack data structure.
We talked about stack as abstract data type
or ADT has been often we define data structure as abstract data type.
We define it as a mathematical or logical model.
We define only the features or operations available with the data
structure
and do not bother about implementation. Now in this lesson we will see how we
can
implement stack data structure. We will first
discuss possible implementations of stack and
then we will go ahead and write some code. Okay so let's get started
as we had seen a stack is a list
or collection with this restriction, with this constraint
that insertion and deletion that we call
push and pop operations in a stack must be performed
one element at a time and only from one
end, that we call the top of stack.So if you see
if we can add only this one extra property only this one
extra constraint to any implementation of a list
that insertion and deletion must be performed
only from one end then we can get a stack.
There are two popular ways of creating lists
we have talked about them alot in our previous lessons we can use
any of them to create a stack.We can
implement stacks using a) arrays
and b) linked lists both these implementations are pretty intuitive.
Let's first discuss array based implementation.
Let's say I want to create a stack of integers,
so what I can do is I can first create an array of integers.
I am creating an array of 10 integers here, i'm naming this array
'A'. Now I'm going to use this array to store
a stack, what I'm going to say is that at
any point some part of this array starting
index 'zero' till an index marked as
'top' will be my stack. We can create
a variable named 'top' to store the index of top of stack.
For an empty stack top is set
as -1, right now in this figure
top is pointing to an imaginary -1 index in the array.
An insertion or push operation
will be something like this. I will write a function named
'Push' that will take an integer 'x' as argument.
In 'Push' function we will first increment top
and then we can fill in integer 'x'
at top index. Here we are assuming that
'A' and 'top' will be accessible to 'Push' function
even when they're not passed as arguments. In 'C' we can declare them as
global variables
or in an object-oriented implementation all these entities
can be members of a class. I'm only writing pseudo code to explain the
implementation logic.
Okay, so for this example array that I'm showing here,
right now top is set as -1
so my stack is empty. Let's insert something onto the stack.
I will have to make call to 'Push' function. Let's say I want to insert
number 'two' onto the stack,
in a call to 'Push' first 'top' will be incremented
and then the integer passed as argument will be written at
top index, so two will be written at index 'zero'.
Let's push one more number, let's say
i want to push number 'ten' this time. Once again 'top' will be incremented
'ten' will now go at index 'one', with each push the stack will expand
towards higher indices in the array. To pop an element from the stack,
i am writing a function here for pop operation. All I need to do is
decrement 'top' by 'one' with
a call to 'pop'. Let's say i am making a call to 'pop' function here,
top will simply be decremented.
Whatever cells are in yellow in this figure are part of my stack.
We do not need to reset this value before
popping, if a cell is not part of stack anymore we do not care what garbage lies
there.
Next time when we will push we will modify it anyway.
So let's say after this pop operation I want to perform
a push, i want to insert number seven onto the stack.
So top once again will be incremented and value at index 'two' will be
overwritten, the new value will be 7.
These two functions 'push' and 'pop' that i have written here
will take constant time. we have simple operation in these two functions
and execution time will not depend upon size of stack.
While defining stack ADT we had said that all the operations
must take constant time or in other words the time complexity
should be O(1) .
In our implementation here both push and pop operations are
O(1). One important thing here
we can push onto the stack only till
array is not exhausted, only till some space is left in the array.
We can have a situation where stack would consume the whole
array so top will be equal to highest index
in the array.A further push will not be possible because
it will result in an overflow. This is one limitation with array based
implementation.
To avoid an overflow we can always create a large enough array,
for that we will have to be reasonably sure that stack will not grow
beyond a certain limit. In most practical cases
large enough array works but irrespective of that
we must handle overflow in our implementation.
There are couple of things that we can do in case of an overflow,
'push' function can check whether array is exhausted or not
and it can throw an error in case of an overflow.
So push operation will not succeed, this will not be a really good behavior.
We can do another thing, we can use the concept of
dynamic array. We have talked about dynamic array in initial lessons in this
series.
What we can do is in case of an overflow
we can create a new larger array.
We can copy the content of stack from older filled up array into
new array if possible we can delete this smaller array.
The cost of copy will be O(n)
or in simple words time taken to copy elements from smaller
array to larger array will be proportional
to number of elements in stack or the size of the smaller array
because anyway stack will occupy the whole array.
There must be some strategy to decide the size of larger array.
Optimal strategy is that we should create
an array twice the size of smaller array.
There can be two scenarios in a push operation.
In a normal push we will take constant time,
in case of an overflow we will first create a larger array twice the size of smaller
array. Copy all elements in time proportional to size of the smaller array
and then we will take constant time to insert the new element.
The time complexity of push with this strategy
will be O(1) in best-case
and O(n) in worst case, in case of an overflow time complexity will be
O(n)
but we will still be O(1) in
average case. If we will calculate the time taken for
n pushes then it will be proportional to n,
remember n is the number of elements in stack.
O(n) is basically saying that
time taken will be very close to
some constant times n, in simple words time taken will be proportional to n.
If we are taking c into n time for n pushes,
to find out average we will divide by n. Average time taken for each push will be
a constant hence O(1) in
average case. I will not go in to all the mathematics of why it's O(n)
for n pushes, to know about it you can check the description of this video
for some resources. Okay so this pretty much is core of our implementation.
We have talked about two more operations in definition of stack
ADT, top operation simply returns
the element at top of stack so 'top' function will look something like this.
We will simply return the element at top index.
To verify whether stack is empty or not this is another operation that we have
defined.
We can simply check the value of top if it is equal to -1,
we can say the stack is empty we can return true
else we can return false. Sometimes pop
and top operations are combined together in that case pop will not just
remove an element from top of stack it will also return that element.
Language libraries in a lot of programming languages give us
implementation of stack. Signature of functions in these implementations can
vary
slightly. Okay now I will quickly show you a basic implementation of stack
in C. In my C code here I'm going to write a simple
array based implementation to create a stack of
integers. The first thing that I'm going to do is I'm going to create an array of
integers
as global variable and the size of this array is 'MAX_SIZE' where
'MAX_SIZE' is defined by this macro as
101. I will declare another global variable
named top and set it as -1 initially,
remember top equals -1 means an empty stack.
When a variable is not declared inside any function
it's a global variable, it can be accessed
anywhere so you do not have to pass it as argument
to functions and now I will write all the operations.
This is my 'push' function, I'm first incrementing top
and then setting the value at top as x.
x is the integer to be inserted passed as argument.
Instead of writing these two statements
i can write one statement like this
and I will be good. I am using pre increment operators so
increment will happen before assignment. I also want to handle
overflow. We will have an overflow when top index will be equal to
MAX_SIZE-1, highest index
available in the array. In case of an
overflow I simply want to print an error message
something like this and return.
So in this implementation I'm not using a dynamic array,
in case of overflow push will not succeed.
Okay now this is my 'Pop' function
i am simply decrementing top. Here also we must handle one
error condition if stack is already empty
we cannot pop, so I'm writing these statements here if
top is equal to -1 we cannot
pop. I will print this error message that there is no element to pop
and simply return. Now let's write
top operation, top operation will simply
return the integer at top index. So now my basic operations are all
written here. I have already written Push
pop and top. In main function i will make some calls to 'push' and 'pop'
and I want to write one more function named print and this is
something that I'm going to write only to verify that 'push' and 'pop' are
happening properly.
I will simply print all the elements in the stack
in my main function after each push or pop operation
i will make a call to print. I am writing multiple function calls, two function
calls
on same line here because I'm short of space.
Remember print function is not a typical operation available with stack,
i am writing it only to test my implementation.
So this pretty much is my code, let's now run this program and see what happens.
This is what I'm getting as output we are pushing
three integers 2,5 and 10 and then we are performing
a pop so 10 gets removed from the stack
and then we are pushing 12. So this
is a basic implementation of stack in C.
This is not an ideal implementation, an ideal implementation should be something
like
we should have a datatype called stack and
we should be able to create instances of it.
We can easily do it in an object-oriented implementation,
we can do it in 'C' also using structures.
Check the description of this video for link to
source code of this implementation as well as of
an object-oriented implementation. In our next lesson we will discuss
linked list implementation of stack this is it for this lesson.
Thanks for watching.