%=====================================================================
% 秋田高専 2E 情報工学概論 テキスト
%　　テーマ　スタックとキュー
%    本テキストの内容
%        ・
%        ・
%        ・
%        ・
%　　　 　・
%
% last updated 2005.11.13
%    created by  Masashi Yamamoto
%     e-mail yamamoto@akita-nct.jp
%=====================================================================
\documentclass[10pt,a4paper]{jarticle}
\usepackage{graphicx,amsmath,amssymb,ascmac,float}
\usepackage{html, listings, jlisting}
\oddsidemargin 0mm  %左の余白 25.4mm-0mm　奇数ページ
\evensidemargin 0mm %左の余白 25.4mm-0mm　偶数ページ
\textwidth 160mm
\newcommand{\command}[1]{「\texttt{#1}」}
\newcommand{\cl}[1]{\texttt{#1}}
\newcommand{\tw}[1]{\texttt{#1}}
%
\newcounter{toi_num}
\newcommand{\toi}{\textbf{\texttt [問\arabic{toi_num}]}
   \addtocounter{toi_num}{1}}
\newcommand{\qbox}[1]{
    {\fboxsep=2pt\fboxrule=0.4pt\fbox{\hspace{3mm}{#1}\hspace{3mm}}}
}
%
\renewcommand{\lstlistingname}{リスト}
\lstset{language=C,%
        basicstyle=\footnotesize,%
        commentstyle=\textit,%
        classoffset=1,%
        keywordstyle=\bfseries,%
	frame=tRBl,framesep=5pt,%
	showstringspaces=false,%
        numbers=left,stepnumber=1,numberstyle=\footnotesize%
	}%
%
\begin{htmlonly}
\usepackage{verbatimfiles}
 \providecommand{\lstinputlisting}[2][]{\verbatimlisting{#2}}
\end{htmlonly}
%
\begin{document}
\title{スタックとキュー}
\author{山本昌志\thanks{独立行政法人　秋田工業高等専門学校　電気情報工学科}}
\date{2005年12月12日}
\maketitle
%
%
%=====================================================================
\section{本日の学習内容}
%=====================================================================
%---------------------------------------------------------------------
\subsection{前回の復習}
%---------------------------------------------------------------------
前回は，リストというデータ構造を学習した．イメージは，図\ref{fig:list}のようなものであっ
た．配列とは異なり，ランダムアクセスはできないが，要素の追加や削除が容易なデータ
構造である．
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=1.0]
  {figure/list.eps}
  \caption{リスト}
  \label{fig:list}
 \end{center}
\end{figure}
%
%
%---------------------------------------------------------------------
\subsection{本日の学習内容}
%---------------------------------------------------------------------
スタックとキュー呼ばれるデータ構造を学習する．本日の授業のゴールは，
\begin{itemize}
 \item スタックとキューのデータ構造のイメージがつかめる．イメージの図が書ける．
 \item スタックとキューの操作の仕方が分かる．
 \item スタックとキューの実装方法が理解できる．
\end{itemize}
である．
%
%=====================================================================
\section{スタック}
%=====================================================================
%---------------------------------------------------------------------
\subsection{イメージ}
%---------------------------------------------------------------------
スタック(stack)を辞書で調べてみると，次のような意味が書かれている．
\begin{enumerate}
 \item (干し草などの)大きな山，積みわら(haystack);(物のきちんとした)積み重ね
 \item (図書館などの)書棚の列，書架；((the 〜s)) (図書館の)(閉架)書庫
 \item (屋上の)組み合わせ煙突(chimney stack);煙突，煙出し
 \item 《コンピューター》スタック:最後に入れたデータを最初に取り出せるようにしたデータ構造
\end{enumerate}
もちろん，情報科学の分野で使われるのは最後の意味で，図\ref{fig:stack}のようなデータ構造で
ある．データ構造であるから，データを蓄えることと，それを取り出すことができる．ス
タックの特徴は，最後に入れたデータが一番最初に取り出されることにある．取り出され
るデータは，格納されている最新のデータで，最後に入れられたものが最初に取り出され
ることから，LIFO(last in first out, 後入れ先出し)と呼ばれる．スタックの途中のデー
タを取り出すことは許されないのである．

スタックにデータを積むことをプッシュ(push)と，スタックからデータを取り出すことを
ポップ(pup)と呼ぶ．これらの英語の意味は，
\begin{description}
 \item[push]＜人・物を＞押す，突く
 \item[pop]ポンという音を立てる，ひょいとやって来る[出て行く]，急にはいる[出る],
	    ひょっこり現れる
\end{description}
である．
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=1.0]
  {figure/stack.eps}
  \caption{スタック}
  \label{fig:stack}
 \end{center}
\end{figure}
%
%
%---------------------------------------------------------------------
\subsection{実際の応用}
%---------------------------------------------------------------------
スタックは単純なデータ構造であるが，有用でいろいろな場面で使われる．例えば，次の
ような場合である．
\begin{itemize}
 \item 関数を呼び出した場合，呼び出し元のデータをいったん保存するときのデータ構
       造として使われる．
 \item 算術式の評価(教科書の List 4-3)
\end{itemize}

教科書では，カッコの対応を調べるプログラム(p.104-108 List 4-2)や逆ポーランド記法
を用いた数式の計算(p.114-115 List 4-3)が示されている．授業では説明しないので，興
味のある者は自分でソースコードを解析するのが良いだろう．
%
%---------------------------------------------------------------------
\subsection{スタックの実装}
%---------------------------------------------------------------------
スタックを実装する関数をリスト\ref{prog:stack_1}に示す．これは，教科書の
List 4-1(p.100)と同じである．

スタックを実装するために必要な記憶領域は，スタックそのものの記憶領域とスタックの
頂上を表す記憶領域である．スタックのための記憶領域として配列\tw{stack[]}を使って
いる．また，スタックの頂上を表すために，変数\tw{stack\_top}を使っている
\footnote{ここでは単なる変数を使ったが，実際のプログラムではポインターが使われる
ことが多い．そのため，頂上を表す変数をスタックポインターと呼ぶ．}．

スタックのために必要な記憶領域が確保されたならば，それを操作しなくてはならない．
スタックに必要な操作は2つで，データを積む(push)ことと，データを取り出す(pop)こと
である．リスト\ref{prog:stack_1}では，次の2つの関数でそれを行っている．
\begin{description}
 \item[\tw{void stack\_push(double val)}]スタックへデータ\tw{val}をプッシュする関
	    数である．データを積み重ねたならば，スタックの頂上を表す変数
	    \tw{stack\_top}を1加算している．スタックがいっぱいで，さらにデータを
	    プッシュしようとするとプログラムは終了するようになっている．
 \item[\tw{double stack\_pop(void)}]スタックからデータを取り出す関数で，戻り値が取り
	    出されたデータである．データを取り出したならば，スタックの頂上を表す
	    変数\tw{stack\_top}を1減算している．スタックが空の状態でデータをポッ
	    プしようとするとプログラムは終了するようになっている．
\end{description}

ここで使われているプログラムのテクニックは，すでに学習済みであるが，分かりにくい
ものだけ述べておく．
%
\begin{itemize}
 \item 15行目 \tw{exit(EXIT\_FAILURE);}\vspace{-3mm}
 \begin{quote}
  関数\tw{exit()}は，正常にプログラムを終了させるために使う．これが呼び出される
  と，諸々の処理を行いプログラムが止まる．ここで使われている引数\tw{EXIT\_FAILURE}の定義
  は\tw{stdlib.h}に書かれている．私のコンパイラーでは，
  \begin{quote}
   \setlength{\baselineskip}{12pt}
   \begin{verbatim}
	#define	EXIT_FAILURE	1	/* Failing exit status.  */
   \end{verbatim}
  \end{quote}\vspace{-5mm}
  となっていた．したがって，この行は，
  \begin{quote}
   \setlength{\baselineskip}{12pt}
   \begin{verbatim}
	exit(1);
   \end{verbatim}
  \end{quote}\vspace{-5mm}
  と同じである．\tw{exit(EXIT\_FAILURE);}とすると処理系定義の不成功状態の形式が
  返される．
 \end{quote}
%
\end{itemize}

\lstinputlisting[caption=スタックの実装,label=prog:stack_1]
{program/list4-1e.c}
%
%
%=====================================================================
\section{キュー}
%=====================================================================
%---------------------------------------------------------------------
\subsection{イメージ}
%---------------------------------------------------------------------
待ち行列と呼ばれるキュー(queue)も辞書で調べてみた．それには，次のような意味がある．
\begin{enumerate}
 \item 順番を待つ人・車などの）列(line)；（待つ）一群の人々
 \item 《コンピューター》待ち行列
\end{enumerate}
これは，窓口に並ぶ順番待ちの行列の意味で，図\ref{fig:queue}のようなデータ構造となっている．
スタックではデータの挿入と取り出しが列の一方からのみであったの対して，キューは列
の両端から行う．一方がデータの追加で一方がデータの取り出しとして使われる．キュー
では，最初に入れたデータが一番最初に取り出されることにある．取り出され
るデータは格納されている最古のデータで，最初に入れられたものが最初に取り出され
ることから，FIFO(first in first out, 先入れ先出し)と呼ばれる．スタック同様，スタッ
クの途中のデータを取り出すことは許されないのである．
%
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=0.9]
  {figure/queue.eps}
  \caption{キュー}
  \label{fig:queue}
 \end{center}
\end{figure}
%

キューはスタックに比べて少しばかり，構造が複雑になっている．実際，それを直線的な
イメージのメモリーにデータを追加しようとすると，以下のような問題が生じる．
\begin{itemize}
 \item FIFOを続けると，いずれはメモリーの端に到達して，データの追加が出来なくな
       る．
 \item データを追加したり取り出したりする毎に，データの列を移動させることも考え
       られる．こうすると計算量が増加して不経済である．
\end{itemize}
これを防ぐために，図\ref{fig:ring_buffer}のようなリングバッファと言うものが考えられた．
%
\begin{figure}[H]
 \begin{center}
  \includegraphics[keepaspectratio,scale=1.0]
  {figure/ring_buffer.eps}
  \caption{リングバッファー}
  \label{fig:ring_buffer}
 \end{center}
\end{figure}
%
%---------------------------------------------------------------------
\subsection{実際の応用}
%---------------------------------------------------------------------
これは，入れられた順序通りに処理すべきデータに使われる．たとえば，次のような応用
がある．

\begin{itemize}
 \item データをバッファーにためて，処理を行う場合．プリンターの処理などである．
       プリント待ちのデータをプリントキューと言うことがある．
 \item オンライントランザクション処理\footnote{ネットワークに接続された複数のパ
       ソコンがホストコンピュータに処理要求を行い、ホストコンピュータがその要求にも
       とづいてデータを処理し、処理結果を即座にパソコンに送り返す処理方式。データベー
       スの処理などに多く使われる．}の管理に用いれれる．この処理では，原則的に
       は到着順に処理しなくてはならない．
\end{itemize}

教科書では，配列を用いたプリントキューのプログラム(p.123-125 List 4-5)を載せてい
る．これも講義では説明しないので，各自，プログラムを解析せよ．
%---------------------------------------------------------------------
\subsection{キューの実装}
%---------------------------------------------------------------------
キューを実装する関数をリスト\ref{prog:queue_1}に示す．これは，教科書の
List 4-4(p.120-121)と同じである．

このプログラムでは，配列\tw{queue[]}を使ってキューを実現している．配列
\tw{queue[]}とキューの先頭を表す変数\tw{queue\_first}と末尾を表す
\tw{queue\_last}はグローバル変数と宣言されているので，以下のキューを操作する関数
で直にアクセスすることができる．

キューを実装するための記憶領域が確保されたならば，それを操作しなくてはならない．
キューの操作は2つで，データを追加することと，データを取り出すこと
である．リスト\ref{prog:queue_1}では，次の2つの関数でそれを行っている．
\begin{description}
 \item[\tw{void enqueue(int val)}]キューへデータ\tw{val}を追加する関
	    数である．データを追加したならば，キューの末尾を表す変数
	    \tw{queue\_last}を1移動(加算)している．キューがいっぱいで，さらにデータを
	    追加しようとするとプログラムはメッセージを出すようになっている．
 \item[\tw{int dequeue(void)}]キューからデータを取り出す関数で，戻り値が取り出し
	    たデータである．データを
	    取り出したならば，キューの先頭を表す変数
	    \tw{queue\_first}を1移動(加算)している．キューが空の状態でデータを
	    取り出そうとするとプログラムは\tw{QUEUE\_EMPTY}を返すようになっている．
\end{description}

ここで使われているプログラムのテクニックは，すでに学習済みであるが，分かりにくい
ものだけ述べておく．
%
\begin{itemize}
 \item 15行目 \tw{(queue\_last+1)\%QUEUE\_MAX}\vspace{-3mm}
 \begin{quote}
  2項演算子\tw{\%}は，割り算の結果の余りを返す．これをりようして，このプログラム
  では，\tw{queue\_last}や\tw{queue\_first}の値を，
  \begin{equation*}
   \cdots\rightarrow0\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5\rightarrow
    0\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow
    5\rightarrow 0\rightarrow 1\rightarrow\cdots
  \end{equation*}
  とサイクリック(cyclic:周期の)に変化させている．5の次の値を0にしているのである．
  これは，サイクリックに値を変化させて対時の常套手段である．
 \end{quote}
\end{itemize}
\lstinputlisting[caption=キューの実装,label=prog:queue_1]
{program/list4-4e.c}
%
%=====================================================================
\section{練習問題}
%=====================================================================
スタックとキューについて，以下の操作を定義する．
\begin{quote}
 \begin{tabular}{ll}
  PUSH($n$) &:スタックにデータ$n$をプッシュする．戻り値は無し．\\
  POP() & :スタックからデータをポップする．戻り値は，取り出した値．\\
  ENQ($n$) &:キューにデータ$n$を追加する．戻り値はなし．\\
  DEQ() & :キューからデータを取り出す．戻り値は取り出した値．
 \end{tabular}
\end{quote}
\begin{quote}
空のスタックやキューに対して，以下の操作を行ったとき，データ構造の様子を図で示せ．
\setcounter{toi_num}{1}
 \begin{itemize}
  \item[\toi]PUSH(3)$\rightarrow$PUSH(5)$\rightarrow$POP()$\rightarrow$PUSH(2)$\rightarrow$PUSH(1)$\rightarrow$POP()$\rightarrow$POP()$\rightarrow$PUSH(1)$\rightarrow$POP()$\rightarrow$PUSH(7)
  \item[\toi]PUSH(1)$\rightarrow$POP()$\rightarrow$PUSH(9)$\rightarrow$PUSH(5)$\rightarrow$POP()$\rightarrow$PUSH(2)$\rightarrow$POP()$\rightarrow$PUSH(4)$\rightarrow$PUSH(8)$\rightarrow$POP()
  \item[\toi]ENQ(6)$\rightarrow$ENQ(2)$\rightarrow$DEQ()$\rightarrow$ENQ(7)$\rightarrow$DEQ()$\rightarrow$ENQ(3)$\rightarrow$ENQ(1)$\rightarrow$ENQ(2)$\rightarrow$DEQ()$\rightarrow$DEQ()
  \item[\toi]ENQ(1)$\rightarrow$DEQ()$\rightarrow$ENQ(2)$\rightarrow$DEQ()$\rightarrow$ENQ(3)$\rightarrow$DEQ()$\rightarrow$ENQ(4)$\rightarrow$ENQ(5)$\rightarrow$DEQ()
  \item[\toi]PUSH(3)$\rightarrow$ENQ(POP())$\rightarrow$PUSH(8)$\rightarrow$PUSH(5)$\rightarrow$ENQ(POP())$\rightarrow$PUSH(DEQ())$\rightarrow$ENQ(2)
 \end{itemize}
\end{quote}
%---------------------------------------------------------------------
\subsection{レポート提出要領}
%---------------------------------------------------------------------
提出方法は、次の通りとする。
% 
\begin{quote}
 \begin{tabular}{ll}
  期限 & 12月19日(月) AM 10:40 \\
  用紙 & A4 \\
  提出場所 & 山本研究室の入口のポスト \\
  表紙 & 表紙を1枚つけて、以下の項目を分かりやすく記述すること。\\
       & \qquad 授業科目名「情報工学」\\
       & \qquad 課題名「課題　スタックとキュー」\\
       & \qquad 2E\quad 学籍番号\quad 氏名\\
       & \qquad 提出日\\
  内容 & 2ページ以降に問いに対する答えを分かりやすく記述すること．
 \end{tabular}
\end{quote}
%=====================================================================
%  参考文献
%=====================================================================
\bibliographystyle{jplain}
\bibliography{reference}
%=====================================================================
\end{document}