スタック

6112 ワード
テキストリンク

抽象データ（ADT）


  • クラスによる実装

  • ADTコンテンツ
  • は、格納するデータ(何が格納されているか)を記述する.
  • に格納されているデータに対してどのような機能を実行できますか?
  • エラーの処理方法
    =>classでそれぞれ定義されている場合(実装されている場合)、メンバー変数、メンバー関数、エラーヘンドラーは
    • になります.
    ※注意!ADTは機能のみを記述し、実施方法は記述しない!性能分析X
    パフォーマンス分析に使用されるのは疑似コードです

    スタックADT


  • last-in-first-out(LIFO)

  • データ構造のナビゲート、挿入、削除に必要な3つの基本機能:
    =>削除(pop)操作に集中したスタックのデータ構造
  • 主機能:ブラウズ(top)、挿入(push)、削除(pop)
  • 付属機能:size()、empty()

  • 同じタイプのデータしか保存できません.ただし、ストレージタイプは関連x

    • メソッドの説明


  • データ構造は自由に実装できますが、その特性に応じて適切に実装する必要があります.

  • Push(オブジェクト):戻り値x.同じタイプのデータしか格納できません

  • object pop():プログラマーの好み(必要)に応じて、戻り(object)を指定せずに削除するか、削除と同時に戻ることができます.

  • objecttop():上部に誰がいるかを答えるだけでいい
  • スタックでは、topには2つの用途がある.1つはメソッドtop()であり,もう1つは上部位置を表す変数topである.
  • スタックはtopの位置を知る必要があるので、ほとんどの場合、資料構造がうまく機能し、クラスでスタックを実現すれば、topを指す方法があるはずです.

  • integer size():整数要素を返します.

  • ブール空():空かどうかを判断し、ブール型に戻ります.

    • スタックADTインタフェース


  • 各メソッドは、必要に応じて、返すかどうか、返すかどうかタイプなど、特定の実施内容を変更することができる.

  • スタックが空の場合、空()またはpop()が呼び出されます.
    例外ハンドラthrow(StackEmpty)を有効にします.
  • 異常ハンドル破棄機能*空スタックのpop、top
    • 禁止
    // 메소드의 선언만 적어놓음 (각 메소드 정의 내용은 안 적어놓았음)

template <typename E>
class Stack{
public:
  int size() const;
  bbol empty() const;
  const E& top() const;
    throw(StackEmpty);
  void push(const E& e);
  void pop() throw(StackEmpty);
}

    例外ハンドラ


  • 特定のコード・ケースの問題の解決に役立ちます

  • 形状:throw Handler名
  • ex) throw StackEmpty
    =>
    • Handlerに処理する例外を投げ出す

  • スタックでハンドルを使用する場合.
  • StackEmpty=>空のスタックのpop、topでは
  • StackFull=>オーバーフロー:データの割り当てを続行すると、最初に定義したスタックのサイズを超える場合、

    • スタックの使用範囲

  • 関数呼び出し時ランタイムスタック=>c++ランタイムシステム
    • =>関数呼び出しが発生した場合は、以前の状況をスタックに保存し、関数の内容を実行し、スタックに格納されているタスクを返して再取り出して実行します.

  • 「Webブラウザで戻る」ボタン(最近アクセスしたサイトに戻る必要がある場合があります)

  • テキストエディタ=>UNDO機能を実装するには、コマンドを保存する必要があります.
    ケース

    • Run-Time Stack

  • main呼び出し関数保存現状.
  • メモリ要素:地域変数、戻り値、PC(プログラムカウンタ)
  • PCとは返さなければならないアドレスに関する情報を格納する(pcは実際にマシンコードに変換して位置を記憶する)
    (ex.PC=3=>ストレージは3行目に戻る必要があります)

  • サンプル分析
  • スタックのbarでは、PC=1は、barの実行内容の最初の行が関数を呼び出したことを示す.すなわち、ある関数を実行するbarの1行目に戻り、2行目からコンテンツ
    • を再実行する.
  • barのコンテンツが完了すると、次のコンテンツfooをスタックする3行目に戻り、次の行からコンテンツを実行します.次にmainの2行目に戻り、次の行からコンテンツ
    • の実行を開始する.

    スタック実装

  • 配列リンクリスト

    • アレイ別スタックの実装


  • 配列でスタックを実装する:アルゴリズムを作成し、関数を設計して、配列を使用してデータを格納し、配列を使用して演算する(push、top、pop)

  • 格納するデータ・オブジェクトに加えて、スタックには上部位置(インデックス)を格納する整数変数が必要です.
    (配列はインデックスに基づいて要素の場所にアクセスします.)

  • リンクリスト位置を実際のアドレスとして保存(ポインタを使用)
    •  // t : 스택의 꼭대기 인덱스를 저장하는 정수형 변수 
 // int t = -1; 으로 초기값이 설정되었을 것임
 // S : 배열

Algorithm size()
  return t+1 
  
Algorithm empty()
{
  if  S.size() = 0 then
    return true
  else 
    return false
}

Algorithm pop()
  if empty() then
    throw StackEmpty
  else
    t <- t -1 // 꼭대기 인덱스만 하나 이동시키면 마치 삭제된듯한 효과 발생(실제로 메모리에서 삭제되진 않음)
    return S[t+1] // t를 1감소시켰으므로 꼭대기 원소를 삭제하려면 t+1 에 있는 것을 삭제
    
Algorithm top()
  if empty() then
    throw StackEmpty
  else
   return S[t]
 
Algorithm push(o)
  if t = S.size() -1 then  // 배열이 꽉찼는데 push 하는 경우
    throw StackFull
  else
    t <- t + 1
    S[t] <- 0

    スタック性能分析

  • 「スタックは挿入操作O(1)によって実行される」
    =>半分は正しい、半分は間違っている.正しい言い方ではない.
  • スタックはAbstractデータ型であるため、パフォーマンスを提供できません.
  • スタックデータ型は、機能のみを記述し、性能は記述しない.
    • スタックはAbstractデータ型であるため、機能のみが記述され、パフォーマンスは記述されません.
    ただし、スタックを配列またはリンクリストとして実装すると、パフォーマンス分析が可能になります.
    すなわち、ADTは「性能分析」を行うために「実施」しなければならない.

    アレイ内のスタックパフォーマンスの解析


  • 5つの機能(push,pop,top,空,size)はいずれもO(1)

  • 空間はO(N)と同じように=>nではなくN!!(n:配列(スタック)の要素数、N:配列のサイズを指定)
    (メモリを初めて割り当てる場合、演算量は配列のNとなります.)

  • 限界:最大寸法は予め定められており、変更されません.→stackFullエラー
    • Algorithm size()
  return t+1   

Algorithm pop()
  if empty() then
    throw StackEmpty
  else
    t <- t -1 
    return S[t+1] 
    
Algorithm top()
  if empty() then
    throw StackEmpty
  else
   return S[t]
 
Algorithm push(o)
  if t = S.size() -1 then  // 배열이 꽉찼는데 push 하는 경우
    throw StackFull
  else
    t <- t + 1
    S[t] <- o

    リンクリストとして実装


  • リンクリストのheadをtopに設定

  • データ構造に輸出入がある
  • スタックは、その文の挿入、削除、および参照を行います.

  • 任意の位置の情報を提供するだけで、高速演算が可能
  • vsアレイ:任意の位置情報を迅速に計算できない

  • すべての演算はO(1)で実行される
  • セグメントでheadをtopとして使用します.tailはtopとしてpop演算はO(1)にできない.

  • push、pop、top演算子コード(大まかに記述)
    • // p : 노드 포인터 (node* p = new node;)

Algorithm push(data)
  p <- new node pointer struct(?) 이렇게 적는게 맞나 
  p.data <- data
  top.next <- p
  top <- p 
  size <- size + 1
  
Algorithm pop()
  if empty() then
    throw StackEmpty
  else
    q <- top
    top <- top.next
    size <- size - 1
    return p <- data

Algorithm top()
  if empty() then
    throw StackEmpty
  else
    return top.data

Algorithm empty()
  if top = NULL then
    return true
  else
    return false

    なぜ単一リンクリストでheadをtopとして使用するのか


    popによるsinglelist tailの演算にはO(n)が必要である
    A.最後の要素を削除したpopを比較します.
  • headが上部に配置されている場合、
  • Node* tmp = head; 2. head → next = head;
  • size =- 1; 4. delete tmp;
    いいけど
  • tailを上部に置くと
    • になります.
  • Node* tmp = tail; 2.for文でtailの前のノードを検索し、tail
    • を割り当てる
  • size —; 4. delete tmp;
    完了するプロセス.
    O(n)次検索tailの前のノードを実行します.
    tailをトップに置くのはheadをトップに置くより効率が低い.
    • cf.delete tmp既存head、tailのアドレスを無効にする
    TIL
    TIL