\documentclass[12pt]{exam}
\usepackage[utf8]{inputenc} % For UTF8 source encoding.
\usepackage{amsmath} % For displaying math equations.
\usepackage{amssymb}
\usepackage{amsfonts} % For mathematical fonts (like \mathbb{E}!).
\usepackage{upgreek} % For upright Greek letters, such as \upvarphi.
\usepackage{wasysym} % For additional glyphs (like \smiley!).
% For document margins.
\usepackage[left=.8in, right=.8in, top=1in, bottom=1in]{geometry}
\usepackage{lastpage} % For a reference to the number of pages.
\usepackage{graphicx}
\usepackage{stmaryrd}
%\usepackage{fontspec} % 字体设置宏包
%\usepackage{ctex}
% TODO: Enter your name here :)
\newcommand*{\authorname}{[Your name goes here]}
\newcommand*{\psetnumber}{2}
\newcommand*{\psetdescription}{Stack and Queue}
\newcommand*{\duedate}{Nov 19th, 2020}
\newcommand*{\duetime}{11:59 pm}
% Fancy headers and footers
\headrule
\firstpageheader{BJSL0060}{Homework \psetnumber\\\psetdescription}{\authorname}
\runningheader{BJSL0060}{Homework \psetnumber}{\authorname}
\runningheader{BJSL0060}{Homework \psetnumber}{Due: \duedate\\at \duetime}
\footer{}{\footnotesize{Page \thepage\ of \pageref{LastPage}}}{}
% Exam questions.
\newcommand{\Q}[1]{\question{\large{\textbf{#1}}}}
\qformat{} % Remove formatting from exam questions.
% Useful macro commands.
\newcommand*{\ex}{\mathbb{E}}
\newcommand*{\bigtheta}[1]{\Theta\left( #1 \right)}
\newcommand*{\bigo}[1]{O \left( #1 \right)}
\newcommand*{\bigomega}[1]{\Omega \left( #1 \right)}
\newcommand*{\prob}[1]{\text{Pr} \left[ #1 \right]}
\newcommand*{\var}[1]{\text{Var} \left[ #1 \right]}
% Custom formatting for problem parts.
\renewcommand{\thepartno}{\roman{partno}}
\renewcommand{\partlabel}{\thepartno.}
% Framed answers.
\newcommand{\answerbox}[1]{
\begin{framed}
\hspace{\fill}
\vspace{#1}
\end{framed}}
\printanswers
\setlength\answerlinelength{2in} \setlength\answerskip{0.3in}
\begin{document}
\title{Homework \psetnumber: \psetdescription}
%\author{\authorname}
\date{}
\maketitle
\thispagestyle{headandfoot}
\begin{questions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Q{Problem Description}
1. Given an empty stack, what will be in the stack after the following operations?
\begin{itemize}
\item push(9)
\item push(2)
\item pop()
\item push(pop()*7)
\item push(30)
\item push(pop()/3)
\end{itemize}
2. Given an empty stack, what will be the result after the following operations?
\begin{itemize}
\item push(1)
\item push(pop()+3)
\item push(pop()/2)
\item pop()
\item pop()
\end{itemize}
3. Given a stack $s$, $S$ is $s$.push($s$.pop() + $s$.pop()) and $T$ is $s$.push($s$.pop() * $s$.pop()). What will be the result after the following operations?
\begin{itemize}
\item$s$.push(1) -> $s$.push(2) -> $s$.push(3) -> $s$.push(4) -> $s$.push(5) -> $S$ -> $T$ -> $S$ -> $T$
\end{itemize}
4. Suppose you can model a line (排队) as a stack. The top of the stack to represent the end of the line, and the bottom of the stack to represent the front of the line. If a new person comes, he/she will be the top of the stack. When you are ready for servicing someone, he/she will be removed from the bottom of the stack. If there are 200 people waiting in line, how many operations on the stack will be required in order to service the line's first person ?
5. Given a stack with 15 elements and a queue with 30 elements, performing the following set of operations 60 times:
\begin{itemize}
\item enqueue(pop()) /*remove the top element of the stack and insert it into the queue
\item push(dequeue()) /*remove the last element of the queue and insert it into the stack
\end{itemize}
How many of the 45 total elements are involved in this process?
\textit{(Note: This is NOT asking how many times elements move, but how many elements move.)}
6. Given two stacks (stack1, stack2), to implement a queue, you can assume stack1 will always contain the data in the correct order, i.e., stack1 will represent the tail of the queue where data is added and the bottom will represent the head. Removing from the top of stack1 will always give the most recently added data. In contrast, when stack2 contains data, it is reversed, with its top representing the head of a queue where data is removed. Removing from its top will always give the oldest data still stored. You can also assume that at any given time at least one stack is completely empty.
With above assumptions, you may use the following to implement the dequeue() function:
If stack1 contains data, then pop all the elements off of stack1 and put them on stack2.
Pop an element off of stack2.
And, you may implement the enqueue(i) function as follows:
If stack2 contains data, then pop all the elements off of stack2 putting them on stack1.
Push element onto stack1.
Questions: 1) Will the above algorithm work? If it does not work, please fix it and provide details; 2) Consider the above algorithm or your modified version, what is the time complexity of an enqueue operation directly after a dequeue operation?
Please submit the PDF version to assistant.
\begin{solution}
Your answers and proofs go here. Note that all math symbols should be in \$\$, such as $\div$, or use the ``equation" command to generate a complex formula.
\end{solution}
\end{questions}
\end{document}