\documentclass[12pt]{article}
\usepackage[a4paper]{geometry}
\usepackage[myheadings]{fullpage}
\usepackage{fancyhdr}
\usepackage{lastpage}
\usepackage{graphicx}
\usepackage[T1]{fontenc}
\usepackage[font=small, labelfont=bf]{caption}
\usepackage{fourier}
\usepackage[protrusion=true, expansion=true]{microtype}
\usepackage[english]{babel}
\usepackage{sectsty}
\usepackage{url, lipsum}
\usepackage{tgbonum}
\usepackage{hyperref}
\usepackage{xcolor}
\usepackage{listings}
\usepackage{textcomp}
\newcommand\tab[1][1cm]{\hspace*{#1}}
\newcommand{\HRule}[1]{\rule{\linewidth}{#1}}
\setcounter{tocdepth}{5}
\setcounter{secnumdepth}{5}
\begin{document}
{
\fontfamily{put}\selectfont
\title
{
\normalsize \textsc{}
\\ [2.0cm]
\HRule{3pt} \\
\LARGE \textbf
{
{
Lab Report - Tutorial Writing \\
Assignment no. 03 \\
CSE 4614 - Technical Report Writing \\
}
\HRule{3pt} \\ [0.5cm]
\date{\vspace{1.5 cm} \textbf{\LARGE{July 27, 2019}}} \vspace*{1 \baselineskip}
\textbf{\LARGE{Assignment topic : Stack}}
}
}
\author
{
S. M. Rayeed \\
ID : 160041045 \\
Lab Group - 1B
}
\maketitle
\newpage
\section {Introduction}
\subsection{What is Stack?}
\tab A stack is an Abstract Data Type which allows operations at one end only. It contains data in reverse order. At any given time, we can only access the top element of a stack. This feature makes it LIFO data structure -- where the element which is placed last, is accessed first.
\newline \tab In other words, a stack is a recursive data structure. Here are the key factors of a stack:
\begin{itemize}
\item a stack is a container of objects or simply data
\item a stack is either empty or full
\begin{itemize}
\item if empty, no data can be removed or popped
\item if full, no data can be added or pushed
\end{itemize}
\item it consists of a top which is the only accessible position
\end{itemize}
\tab In stack terminology, insertion operation is called PUSH operation and removal operation is called POP operation.
\subsection{Stack Representation}
\tab As mentioned earlier, stack has two basic operations -- PUSH for insertion and POP for deletion; and only the TOS (Top of Stack) is accessible. Now, if we focus on how a stack can be represented along with its operations in a graphical way, the following figure is a good representation --
\begin{figure}[ht]
\graphicspath{ {D:\Stack} }
\center \includegraphics[width=10cm, height=6cm]{stack_representation.jpg}
\caption{{Stack Representation}}
\end{figure}
\section {Data Storage in Stack}
\tab In a stack, data or objects are stored in reverse order. If any insertion operation occurs in an empty stack, the data will be TOS element. But after that, the next data inserted, will be placed on top of the first data. The following figure will give us a clear view about data storage in stack --
\begin{figure}[ht]
\graphicspath{ {D:\Stack} }
\center \includegraphics[width=10cm, height=6cm]{stack_storage.jpg}
\caption{Stack Storage}
\end{figure}
\tab In the above figure, at first 1 has been inserted into an empty stack named "s" using the PUSH command. Now, this 1 is the TOS (top of stack) element. After that, 2 has been inserted and has been placed on top of 1 -- meaning that now it is the TOS and similarly for every insertion, the storage of data will be in reverse order. Also one more thing to remember, we can only access the TOS at any given time.
\newline \tab One more thing to mention, size of a stack can either be fixed or it can dynamically change. If the size is fixed, once the stack is full, we cannot store any further data. But the size can be adjusted dynamically through stack-implementation using linked-list which we will focus later on.
\section {Operations in Stack}
\tab Operations in stack is pretty-much straight-forward -- we only have the freedom to insert and delete any element. Moreover, we have restrictions in insertion and deletion --
\begin{itemize}
\item insertion can only be at the top of stack (TOS)
\item deletion can only occur at the top of stack (TOS)
\end{itemize}
\tab These restrictions simply means -- only the top element of stack is accessible. In a stack, there can be two operations -- PUSH operation and POP operation.
%subsection -> PUSH
\subsection{PUSH Operation -- Inserting Elements}
\tab When we want to insert an element into a stack, PUSH operation is conducted using the command \textcolor{black}{stackname.push(element\textunderscore to \textunderscore be \textunderscore pushed))} in standard template library. Steps in PUSH operation is mentioned below --
\begin{itemize}
\item Step 1 -- Checks if the stack is full.
\item Step 2 -- If the stack is full, produces an error and exit.
\item Step 3 -- If the stack is not full, increments the TOS(Top of Stack) to point the immediate next empty space.
\item Step 4 -- Adds data element to the stack location where TOS is pointing to.
\item Step 5 -- Returns successful insertion.
\end{itemize}
\begin{figure}[ht]
\graphicspath{ {D:\Stack} }
\centering \includegraphics[width=8cm, height=5cm]{push.jpg}
\caption{{Push Operation in Stack}}
\end{figure}
%subsection -> POP
\subsection{POP Operation -- Deleting Elements}
\tab When we want to delete an element into a stack, POP operation is conducted using the command \textcolor{black}{stackname.pop()} in standard template library. Steps in POP operation is mentioned below --
\begin{itemize}
\item Step 1 -- Checks if the stack is empty.
\item Step 2 -- If the stack is empty, produces an error and exit.
\item Step 3 -- If the stack is not empty, accesses the data element at which top is pointing.
\item Step 4 -- Decreases the value of top by 1.
\item Step 5 -- Returns successful deletion.
\end{itemize}
\begin{figure}[ht]
\graphicspath{ {D:\Stack} }
\center \includegraphics[width=8cm, height=5cm]{pop.jpg}
\caption{{Pop Operation in Stack}}
\end{figure}
\subsection{Push and POP Operation -- Graphical Representation}
\tab Here is an exmple how the push and pop operation operates in a stack
\begin{itemize}
\item Stage 1 -- 1 is the top element of the stack
\item Stage 2 -- stack.push(4) operates on the stack; which means 4 has been inserted and now it is the top element
\item Stage 3 -- stack.pop() will remove the Top element i.e. 4 from the stack
\item Finally, again 1 is at the Top of stack
\end{itemize}
\begin{figure}[ht]
\graphicspath{ {D:\Stack} }
\center \includegraphics[width=12cm, height=8cm]{opertaion.jpg}
\caption{{Operations in Stack -- An Example }}
\end{figure}
\subsection{Additional Operations}
\tab To ensure the efficient use of a stack, we need to check the states of the stack. The following operations suffice that --
\begin{itemize}
\item isFull() :
\begin{itemize}
\item checks if stack is full.
\item if full, push() operation cannot be conducted.
\end{itemize}
\item isEmpty() :
\begin{itemize}
\item checks if stack is empty.
\item if empty, pop() operation cannot be conducted.
\end{itemize}
\item peek() : returns stack[top] -- provides access to the top element of the stack. Unlike pop, does not remove the top element. Also known as top() operation.
\item size() : determines the size of the stack.
\end{itemize}
\vspace{.5cm}\tab Also, the position of the Top element determines the status of the stack. Have a look at the following table --
\begin{table}[h!]
\centering
\begin{tabular}{ |p{7cm}||p{7cm}| }
\hline
\multicolumn{2}{|c|}{Determining Status of Stack via TOS} \\
\hline
\centering Position of TOS&\tab \tab Status of Stack \\
\hline
\centering -1 & Stack is Empty\\
\centering 0 & One Element in the Stack\\
\centering N-1 & Stack is Full\\
\centering N & Overflow State of Stack\\
\hline
\end{tabular}
\end{table}
\section {Implementations of Stack}
\tab Stack can be easily implemented using an Array or a Linked List. Arrays are quick, but are limited in size and Linked List requires overhead to allocate, link, unlink and deallocate; but is not limited in size. There are many different approaches in implementation of stack.
\subsection {Implementations of Stack -- Standard Template Library}
\tab In the standard template library of classes, the data type stack is an adapter class, meaning that a stack is built on top of other data structures. The functions associated with stack are :
\begin{itemize}
\item empty() -- Returns whether the stack is empty
\item size() -- Returns the size of the stack
\item top() -- Returns a reference to the top most element of the stack
\item push(A) -- Adds the element A at the top of the stack
\item pop() -- Deletes the top most element of the stack
\end{itemize}
\subsubsection{Stack in STL - Code}
\tab Here is an exemplary C++ code that depicts Stack and its operations in STL. The Function showstack() displays the current state of the stack while being called --
\newline
\lstinputlisting[language=c]{stack_implementation_STL.cpp}
\subsection {Implementations of Stack -- Arrays}
\tab Array implementation of stack is easy but the size is static -- means the stack cannot be dynamically increasing or decreasing. Unlike the STL implementation, in array implementation, the stack-operations are not built-in; hence we need to define the operational functions like -- push(), pop(), top(), isEmpty(), isFull() etc.
\newline \tab As we need to define the functions, it is very much necessary to know how each functions work and for that, the best way is to know the algorithms that each of these follows.
\subsubsection{Algorithm - isFull()}
\tab isFull() is a boolean function that returns a true value if the stack is full, otherwise returns false. Now, how do we know when the stack is full? Well, in array representation, we define the maximum size of the array -- in this case which is our stack. Now, while insertion, the value of the TOS gradually increases. If the TOP equals to the maximum size, it means that it has reached the limit; no value can be inserted unless popping. Here, the algorithm is given below --
\lstinputlisting[language=c]{isFull.cpp}
\vspace{2mm} \tab
One thing to notice, if the size of the array is declared as N, then the maxsize will be N-1; because array elements starts from 0.
\subsubsection{Algorithm - isEmpty()}
\tab isEmpty() is also a boolean function that returns a true value if the stack is empty, otherwise returns false. Now, how do we know when the stack is empty? Well, quite easy! In array representation, we generally initialize the index of the array at -1; because the array indexing starts from 0, so when the first element of the array is being inserted, the index should be 0. It implies if the index value is -1 then the array is empty. The concept is very much straightforward and is shown below --
\lstinputlisting[language=c]{isEmpty.cpp}
\vspace{2mm}
\tab As index-value of -1 implies that the array is empty, the first element inserted will have the index-value of 0 -- which suffices the array-condition.
\subsubsection{Algorithm - TOS()}
\tab TOS() is a function that returns the element that is on the top position of a stack. The type of this function depends on the type of the array. The function is necessary because in stack, we only can operate on the top element. And after every insertion or deletion operation, the top element changes. This function has no functionality rather than this -- \vspace{2.5mm}
\lstinputlisting[language=c]{TOS.cpp}
\vspace{3mm} \tab Here, stack is an array where the indexing starts from 0 and gradually increases by 1 after an insertion and decreases by 1 after a deletion operation. The integer-type variable "TOP" stores the index-value of the element which is in the top of stack. So, when this function is called, it returns the element having the TOP index -- that is how it works.
\subsubsection{Algorithm - push()}
\tab push() is one of the most-influential function in stack as it operates to insert an element. It is a parameterized function that checks whether the stack is full or not; and if not, it stores the element on top of the stack and increases the value of TOP (as TOP stores the index-value of the top-most element, after every insertion, its value should be increased by 1). Well, needless to say, but if the stack is full, then the function will show "Overflow" and quit its operation. Here one example of the push function is being shown --
\lstinputlisting[language=c]{push.cpp}
\vspace{2mm}
\tab Here, n is the size of the stack, x is the element that needs to be inserted in the stack. As array-indexing starts from 0; in an array of size n, the top-most element will have an index of n-1 (0 to n-1 : Total n number of elements). So, if the value of top reaches the limit, push() will show "Overflow", otherwise it will increase the value of top - that means top will point to the next position and in that position of stack, the element x will be inserted.
\par Well, one thing to mention, as we have defined isFull() function, instead of checking manually, we could simply call that function to determine whether the stack is full or not. In pop() operation, it has been shown.
\subsubsection{Algorithm - pop()}
\tab pop() is also a very influential function in stack as it operates to delete an element. It is a parameterized function that checks whether the stack is empty or not; and if not, it deletes the element on top of the stack and decreases the value of TOP (as TOP stores the index-value of the top-most element, after every deletion, its value should be decreased by 1). Well, needless to say, but if the stack is empty, then the function will show "Underflow" and quit its operation. Here one example of the pop function is being shown --
\lstinputlisting[language=c]{pop.cpp}
\vspace{2mm}
\tab Here, n is the size of the stack. As we have already defined the isEmpty() function, we can easily implement pop() by calling the isEmpty() function. If the stack is empty, the isEmpty() function will return True, hence nothing is there to be popped. So, the pop() will show "Underflow Condition", but otherwise it will decrease the value of top -- meaning, the element that was next to the top-most element is now being pointed by top; hence the top-most element is gone.
\subsubsection{Stack using Array - Code}
\tab Here is an exemplary C++ code that depicts Stack and its operations using array. Unlike STL, the functions are not pre-defined --
\newpage
\lstinputlisting[language=c]{stack_implementation_using_array.cpp}
\subsection {Implementations of Stack -- Linked Lists}
\tab A stack can be easily implemented through the linked list. In such stack implementation, a stack contains a top pointer. which is “head” of the stack where pushing and popping items happens at the head of the list. first node have null in link field and second node link have first node address in link field and so on and last node address in "top" pointer.
\newline \tab The main advantage of using linked list over an arrays is that it is possible to implements a stack that can shrink or grow as much as needed. In using array will put a restriction to the maximum capacity of the array which can lead to stack overflow. Here each new node will be dynamically allocate. so overflow is not possible.
\subsubsection{Implementation of Stack using Linked Lists -- Functions}
\tab In linked list implementation, we have the same functions as before -- having the same analogy, but with different approach of implementations. Also as mentioned before, since the stack can dynamically expand or shrink, there\textquotesingle s no need of overflow. The generic functions are mentioned below --
\begin{enumerate}
\item push() : Insert the element into linked list at the top node of Stack.
\item pop() : Return top element from the Stack and move the top pointer to the second node of linked list.
\item peek(): Return the top element.
\item display(): Print all elements of Stack.
\end{enumerate}
\subsubsection{Stack using Linked Lists -- push() function}
\begin{itemize}
\item Utility function to add an element data in the stack
\item Steps in push() operation --
\begin{itemize}
\item creates new node temp and allocate memory
\item initializes data into temp data field
\item puts top pointer reference into temp link
\item makes temp as top of Stack
\end{itemize}
\item An example of the push() function is attached below --
\end{itemize}
\lstinputlisting[language=c]{push_linked_list.cpp}
\subsubsection{Stack using Linked Lists -- pop() function}
\begin{itemize}
\item Utility function to pop the top element data from the stack
\item Steps in pop() operation --
\begin{itemize}
\item checks for stack underflow
\item top assign into temp
\item assigns second node to top
\item destroys connection between first and second
\item releases memory of top node
\end{itemize}
\item An example of the pop() function is attached below --
\end{itemize}
\lstinputlisting[language=c]{pop_linked_list.cpp}
\subsubsection{Stack using Linked Lists -- peek() function}
\begin{itemize}
\item Checks for empty stack and if empty, exits
\item Otherwise, returns top element data
\item An example of the peek() function is attached below --
\end{itemize}
\lstinputlisting[language=c]{peek.cpp}
\subsubsection{Stack using Linked Lists -- display() function}
\begin{itemize}
\item Function to print all the elements of the stack
\item Steps in display() operation --
\begin{itemize}
\item check for stack underflow
\item if yes, exits
\item otherwise, print node data until temp gets zero
\end{itemize}
\item An example of the display() function is attached below --
\end{itemize}
\lstinputlisting[language=c]{display.cpp}
\subsubsection{Stack using Linked Lists -- Complete Code}
\tab Here is an exemplary C++ code that depicts Stack and its operations in Linked-lists --
\lstinputlisting[language=c]{stack_implementation_linked_list.cpp}
\section {Example -- Infix to Postfix Conversion}
\tab There are huge number of examples and real-life implementations of stack. Such as Deck of cards, pile of dishes in kitchen, the tower of Hanoi problem and so on. From the data-structure perspective, a good example of stack is conversion of expressions. There are 3 types of expression --
\begin{enumerate}
\item Prefix -- Expression of the form operator a b. When an operator is in front of every pair of operands.
\item Infix -- Expression of the form a operator b. When an operator is in-between every pair of operands.
\item Postfix -- Expression of the form a b operator. When an operator is at the back of every pair of operands.
\end{enumerate}
Infix to Postfix is a very renowned conversion technique that is implemented by stack. We are going to have a look into this --
\subsection{Why Postfix representation of the expression?}
\tab The compiler scans the expression either from left to right or from right to left. Consider the below expression: \newline \tab \tab \tab \tab a op1 b op2 c op3 d ; \tab where --
\newline \tab \tab \tab \tab op1 = +, op2 = *, op3 = +
\newline \tab
\begin{itemize}
\item The compiler first scans the expression to evaluate the expression : b * c
\item Then again scan the expression to add a to it
\item The result is then added to d after another scan
\item The repeated scanning makes it very in-efficient
\item That\textquotesingle s why it is better to convert the expression to Postfix form before evaluation
\end{itemize}
\tab The corresponding expression in postfix form is: $$abc*+d+$$ \tab The postfix expressions can be evaluated easily using a stack by following the following algorithm --
\subsection{Infix to Postfix Conversion -- Algorithm}
\begin{enumerate}
\item Scan the infix expression from left to right.
\item If the scanned character is an operand, output it.
\item Else --
\begin{itemize}
\item If the precedence of the scanned operator is greater than the precedence of the operator in the stack( or the stack is empty or the stack contains a "("\space), then push it.
\item Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.)
\end{itemize}
\item If the scanned character is an "(", push it to the stack.
\item If the scanned character is an ")", pop the stack and and output it until a "(" is encountered, and discard both the parenthesis.
\item Repeat steps 2-6 until infix expression is scanned.
\item Print the output
\item Pop and output from the stack until it is not empty.
\end{enumerate}
\subsection{Conversion of A * B + C * D : --}
\tab Figure 6 Shows the conversion algorithm working on the expression -- $$ A * B + C * D $$
\begin{figure}[ht]
\graphicspath{ {D:\Stack} }
\center \includegraphics[width=12cm, height=7cm]{intopost.jpg}
\caption{{Infix to Postfix Conversion - An Example}}
\end{figure}
\tab Note that the first * operator is removed upon seeing the + operator. Also, + stays on the stack when the second * occurs, since multiplication has precedence over addition. At the end of the infix expression the stack is popped twice, removing both operators and placing + as the last operator in the postfix expression.
\subsection{Infix to Postfix Conversion -- Implementation using C++}
\tab Here is an exemplary C++ code that converts an infix experession into its corresponding postfix expression --
\lstinputlisting[language=c]{intopost.cpp}
\section {Complexity Analysis}
\tab Below mentioned are the time complexities for various operations that can be performed on the Stack data structure --
\begin{enumerate}
\item Push Operation : O(1) --
\begin{itemize}
\item While pushing an element, we can only insert in top of the stack.
\item As the insertion can be in one-way, it\textquotesingle s a one-step process.
\item That\textquotesingle s why the time complexity is fixed to O(1).
\end{itemize}
\item Pop Operation : O(1) --
\begin{itemize}
\item While popping element, we can only pop the top element from the stack
\item As the deletion can be in one-way, it\textquotesingle s a one-step process.
\item That\textquotesingle s why the time complexity is fixed to O(1).
\end{itemize}
\item Top Operation : O(1) --
\begin{itemize}
\item Only the top element of the stack is accessible.
\item Accessing the top-most element in a stack is a one-step process as we do not have to search elsewhere.
\item That\textquotesingle s why the time complexity is fixed to O(1).
\end{itemize}
\item Other cases --
\begin{itemize}
\item Access O(n) -- Stacks offer random access to their contents by popping the top element off the stack. You have to do this repeatedly to access an arbitrary element somewhere in the stack. Therefore, arbitrary access is O(n).
\item Search O(n) -- Searching for a given value in the stack requires repeatedly popping elements off the top of the stack until you find the value you seek. So search is O(n).
\end{itemize}
\end{enumerate}
\vspace{2mm} \tab To talk about space complexity, we need to know what the problem is. If n items are needed to be stored in the stack at the same time, then space complexity is O(n). But n items, can be stored in O(1) space too. By pushing and popping every item, we can use only 1 space.
\section {Applications}
\tab There are many applications of stack in data structure. Some of them are mentioned below in short --
\begin{enumerate}
\item Expression evaluation
\begin{itemize}
\item Stack is used to evaluate prefix, postfix and infix expressions.
\item In particular let\textquotesingle s consider arithmetic expressions. Suppose that, there are boolean and logical expressions that can be evaluated in the same way. Control structures can also be treated similarly in a compiler.
\item This study of arithmetic expression evaluation is an example of problem solving where we have to solve a simpler problem and then transform the actual problem to the simpler one.
\item We are accustomed to write arithmetic expressions with the operation between the two operands: a+b or c/d. If we write a+b*c, however, we have to apply precedence rules to avoid the ambiguous evaluation.
\item But there's no real reason to put the operation between the variables or values. They can just as well precede or follow the operands. Moreover, the advantage of prefix and postfix is the need for precedence rules and parentheses are eliminated.
\end{itemize}
\item Backtracking
\begin{itemize}
\item Backtracking is used in algorithms in which there are steps along some path (state) from some starting point to some goal
\begin{itemize}
\item Find your way through a maze
\item Find a path from one point in a graph (roadmap) to another point
\item Play a game in which there are moves to be made (checkers, chess)
\end{itemize}
\item In all of these cases, there are choices to be made among a number of options. We need some way to remember these decision points in case we want/need to come back and try the alternative.
\item Consider the maze. At a point where a choice is made, we may discover that the choice leads to a dead-end. We want to retrace back to that decision point and then try the other (next) alternative.
\item Again, stacks can be used as part of the solution. Recursion is another, typically more favored, solution, which is actually implemented by a stack.
\end{itemize}
\item Memory management
\begin{itemize}
\item Any modern computer environment uses a stack as the primary memory management model for a running program. Whether it\textquotesingle s native code (x86, Sun, VAX) or JVM, a stack is at the center of the run-time environment for Java, C++, Ada, FORTRAN, etc.
\item The discussion of JVM in the text is consistent with NT, Solaris, VMS, Unix runtime environments.
\item Each program that is running in a computer system has its own memory allocation containing the typical layout as shown below.
\end{itemize}
\item Call and return process
\begin{itemize}
\item When a method/function is called --
\begin{enumerate}
\item An activation record is created; its size depends on the number and size of the local variables and parameters.
\item The Base Pointer value is saved in the special location reserved for it
\item The Program Counter value is saved in the Return Address location
\item The Base Pointer is now reset to the new base (top of the call stack prior to the creation of the AR)
\item The Program Counter is set to the location of the first bytecode of the method being called
\item Copies the calling parameters into the Parameter region
\item Initializes local variables in the local variable region
\end{enumerate}
\item While the method executes, the local variables and parameters are simply found by adding a constant associated with each variable/parameter to the Base Pointer.
\item When a method returns --
\begin{enumerate}
\item Get the program counter from the activation record and replace what's in the PC
\item Get the base pointer value from the AR and replace what's in the BP
\item Pop the AR entirely from the stack.
\end{enumerate}
\end{itemize}
\end{enumerate}
\section {Conclusion}
\tab Stack is a very well-known and one of the most-frequently used data structures. Having less complexity, ease of understanding and numerous applications in our life -- stack has been playing a vital role in development and implementation of new techniques.
}
\centering \vfill \Large Thank You ...
\end{document}
