Data
Structures
Stack
Stack
• Stack is a linear data
structure
• Known as: LIFO (Last In First
Out)
• Uses:
• Balanced or Unbalanced
Parenthesis
• Undo actions.
Operation of Stack
• Insert: Push()
• Delete: Pop()
• To access the top value: Peek()
Uses: Balanced/Unbalanced
Parenthesis
• Stack is used to check
either parenthesis in a
code are balanced or
not
• For example: the
following code
Simulate
the code
Simulate
the code
Simulate
the code
Simulate the code
• Now isEmpty() function will
check either stack is empty
or not.
• In this example isEmpty()
function will return False,
because the stack is not
empty.
• So, parenthesis are not
balanced.
• This will produce an error for
closing parenthesis.
Uses: Undo
the actions
• It is easy to use stack to track
the actions done by the user.
• It is helpful when someone
wants to undo (ctrl+z) the
action.
• You undo the last action then
Action 5 is popped from stack
(as shown).
• You undo again then Action 4 is
popped from the stack (as
shown).
Implementation of Stack
• Stack can be
implemented with arrays
and linked list.
• Array has fixed length
• Linked list can be
extended during
programming execution.
Implementation using array
• Push an element in
stack
• Pushing an element
uses constant time so
time complexity is:
Theta(1)
Implementation using array
• As we are using static array so after inserting some elements the stack becomes full.
• There are two solutions:
• First: Check the size of the array before inserting an element.
• Second: Extend (double) the size of the array and copy the elements of old array into new
array.
• The first one blocks the execution of any further push operation once the limit of the array size
has been reached.
• The second one uses the idea of dynamic arrays.
• A new array is created, usually with double the size of the original array.
• Elements are copied to this second array and the operation Push can proceed.
Implementation using array
• 1st Solution:
• As shown in the code.
• Code is added to check
that either space is
available for further
push or not.
Implementation using array
• 2nd Solution:
• As shown in the code and diagram.
• Array is extended and elements
are copied to new array.
• So, the time complexity of the
push operation increases to
Theta(n), because we need to
copy all the elements already
stored in the stack to the larger
array.
Pop() function
• When one element is
popped then the Top
variable decrements by
1 as shown in the code.
• This function prints
“empty stack” when
there is no element of
pop().
• Time complexity of
Pop() function is shown
in the figure.
• As it takes constant
time for each
operation, so time
complexity is Theta(1).
PEEK Operation
• PEEK, which returns the value of
the element at the top of the
stack.
• This operation is very simple, and
it just returns the value at the top
of the stack.
• All instructions inside the peak
operation take a constant time to
be executed,
• Therefore, its time complexity is
Theta(1).
ISEMPTY() Operation
• Finally, the operation ISEMPTY
simply checks the value of top.
• If the variable top is equal to -1 then
the stack is empty and the Boolean
variable TRUE is returned.
• In any other case the Boolean
variable FALSE is returned.
• All the instructions executed by the
ISEMPTY operation take a constant
time, and therefore its time
complexity is Theta(1).
Array implementation of Stack
• Table showing the
summary.
Implementation using Linked List:
PUSH() Operation
• Linked list is a dynamic
data structure so no
worries of space as it
grown dynamically.
• Following figure shows
the PUSH() operation
and its code.
POP() Operation
• POP operation removes the last element inserted into
the stack.
• This is the same as removing the first element of the
list. So this is the pseudocode for the POP operation.
• First you check if the list is empty, in which case you
cannot pop any element from it.
• And then you make the top bypass the element to be
deleted by making it point to the second element of
the list.
• We are assuming that because it's not pointed at by
any other node, the first node of the list is
automatically eliminated from memory.
• All instructions inside the POP operation take a
constant time to be executed.
• Therefore, POP has a time complexity equal to
Theta(1).
PEEK() Operation
• PEEK() operations returns
top element in the list.
• It will print “empty stack”
if stack is empty.
• Each operation in this
function takes constant
time so time complexity is
Theta(1).
ISEMPTY() Operation
• This function returns
Boolean value TRUE if
stack is empty and
FALSE otherwise.
• Table showing the
summary of linked list
implementation of
stack.