C++データ構造のスタックとキュー
3100 ワード
スタックとキューも一般的なデータ構造です.スタックの“先進的な後出”の性質はそれに多くの応用があって、もしあなたがアセンブリ言語を学んだことがあるならば、プログラムを設計する時、中断が現れて、中断に応答して、それではプログラムの中の重要なレジスタの情報はスタックの中に押し込んで、中断プログラムが実行し終わってブレークポイントの情報をスタックから出ます;また、コンソールで計算機プログラムを設計する場合は、一連の演算数と演算子を入力して演算結果を得るには、通常スタック操作も使用されます.ポーランドアルゴリズムを知っていれば、スタックを通じて逆ポーランドアルゴリズムを実現し、計算器の設計を完了することができます.キューの役割は明らかで,先進先出はキューのように,ネットワークでのリクエストや返信,CPU内部の命令キューなどである.さあ、そのままC++で実現しましょう~
一、スタックは直接スタックのクラスを書いて、下のコードをstackに置くことができます.hのヘッダファイルで、m_stackは動的に申請する空間をスタックとして、m_topはスタックトップを指し、m_ncountはスタックのサイズです.スタックに入る操作では、スタックがいっぱいかどうか、すなわちスタックがオーバーフローしているかどうかを判断する必要があります.
同じようにスタックを考慮し、スタックがスタックの底に着いたかどうかを考慮します.
このスタックをテストするには、次のコードでテストできます.
二、キュー
キューリングのキューを作ります~同じキュークラスqueueを書きます.h
テストコード:
一、スタックは直接スタックのクラスを書いて、下のコードをstackに置くことができます.hのヘッダファイルで、m_stackは動的に申請する空間をスタックとして、m_topはスタックトップを指し、m_ncountはスタックのサイズです.スタックに入る操作では、スタックがいっぱいかどうか、すなわちスタックがオーバーフローしているかどうかを判断する必要があります.
bool isFull()同じようにスタックを考慮し、スタックがスタックの底に着いたかどうかを考慮します.
bool isEmpty()#pragma once
typedef int DATA;
class Stack
{
DATA *m_stack;
int m_ntop;
int m_ncount;
public:
Stack(int ncount = 5)
{
m_ncount = ncount;
m_ntop = -1;
m_stack = new DATA[m_ncount];
}
bool isFull()
{
return m_ntop+1 >= m_ncount;
}
bool isEmpty()
{
return m_ntop == -1;
}
void push(const DATA& data)
{
if (!isFull())
{
m_stack[++m_ntop] = data;
}
}
bool pop(DATA &data)
{
if (!isEmpty())
{
data = m_stack[m_ntop--];
return true;
}
return false;
}
};このスタックをテストするには、次のコードでテストできます.
#include
#include"stack.h"
using namespace std;
int main()
{
Stack s;
int i = 0;
while (i < 10)
{
s.push(i + 1);
++i;
}
DATA data;
while (i > 0)
{
if(s.pop(data))
cout << data << endl;
}
return 0;
}
二、キュー
キューリングのキューを作ります~同じキュークラスqueueを書きます.h
#pragma once
typedef int DATA;
class Queue
{
DATA *m_data;
int m_ncount;
int m_head;
int m_tail;
public:
// 6, ， 5 ，
Queue(int ncount=6):m_ncount(ncount)
{
m_head = m_tail = 0;
m_data = new DATA[ncount];
}
bool isFull()
{
return (m_tail+1)%6==m_head;
}
bool isEmpty()
{
return m_head==m_tail;
}
void push(const DATA& data)
{
if (!isFull())
{
m_data[m_tail] = data;
// m_tail 0-5 6 ， m_tail 5 ，
if (++m_tail >= m_ncount)
m_tail = 0;
}
}
bool pop( DATA &data)
{
if(!isEmpty())
{
data = m_data[m_head];
if (++m_head >= m_ncount)
m_head = 0;
return true;
}
return false;
}
};テストコード:
#include
#include"queue.h"
using namespace std;
int main()
{
Queue q;
int i = 0;
while (i < 10)
{
q.push(i + 1);
++i;
}
DATA data;
q.pop(data);
while (i >0)
{
if (q.pop(data))
cout << data << endl;
--i;
}
return 0;
}