C++数据结构创建栈

（一）建立一个空栈；对已经建立的栈进行插入、删除、取栈顶元素等基本操作。

提示：定义顺序栈的数据类型-顺序栈类SeqStack，包括入栈、出栈、取栈顶元素等基本操作。

const int StackSize=10;

template <class T>

class SeqStack

{

public:

SeqStack( ) ; //构造函数，栈的初始化

void Push(T x); //将元素x入栈

T Pop( ); //将栈顶元素弹出

T GetTop( ); //取栈顶元素（并不删除）

private:

T data[StackSize]; //存放栈元素的数组

int top; //栈顶指针，指示栈顶元素在数组中的下标

};

（二）建立一个空队列；对已经建立的队列进行插入、删除、组队头元素等基本操作。

提示：定义链队列的数据类型-链队列类LinkQueue，包括入队、出队、取队列头元素等基本操作。

template <class T>

struct Node

{

T data;

Node<T> *next;

};

template <class T>

class LinkQueue

{

public:

LinkQueue( ); //构造函数，初始化一个空的链队列

~~LinkQueue( ); //析构函数，释放链队列中各结点的存储空间

void EnQueue(T x); //将元素x入队

T DeQueue( ); //将队头元素出队

T GetQueue( ); //取链队列的队头元素

private:

Node<T> *front, *rear; //队头和队尾指针，分别指向头结点和终端结点

};

1、栈

#include <iostream>
using namespace std;

const int StackSize = 10;

template <class T>
class SeqStack
{
public:
SeqStack( ) ; //构造函数，栈的初始化
void Push(T x); //将元素x入栈
T Pop( ); //将栈顶元素弹出
T GetTop( ); //取栈顶元素（并不删除）
private:
T data[StackSize]; //存放栈元素的数组
int top; //栈顶指针，指示栈顶元素在数组中的下标
};

template <class T>
SeqStack<T>::SeqStack()
: top( 0 )
{ }

template <class T>
void SeqStack<T>::Push( T x )
{
data[top++] = x;
}

template <class T>
T SeqStack<T>::Pop()
{
return data[--top];
}

template <class T>
T SeqStack<T>::GetTop()
{
return data[top-1];
}

int main()
{
SeqStack<int> a;
a.Push( 1 );
a.Push( 2 );
a.Push( 3 );
cout << a.Pop();
cout << a.Pop();
cout << a.Pop();
}


2、队列

#include <iostream>
using namespace std;

template <class T>
struct Node
{
T data;
Node<T> *next;
};

template <class T>
class LinkQueue
{
public:
LinkQueue( ); //构造函数，初始化一个空的链队列
~LinkQueue( ); //析构函数，释放链队列中各结点的存储空间
void EnQueue(T x); //将元素x入队
T DeQueue( ); //将队头元素出队
T GetQueue( ); //取链队列的队头元素
private:
Node<T> *front, *rear; //队头和队尾指针，分别指向头结点和终端结点
};

template <class T>
LinkQueue<T>::LinkQueue()
:front( 0 ), rear( 0 )
{ }

template <class T>
LinkQueue<T>::~LinkQueue()
{
Node<T>* tmp;
while ( front ) {
tmp = front;
front = front->next;
delete tmp;
}
}

template <class T>
void LinkQueue<T>::EnQueue( T x )
{
Node<T>* tmp = new Node<T>;
tmp->data = x;
tmp->next = 0;
if ( !rear )
front = rear = tmp;
else {
rear->next = tmp;
rear = tmp;
}
}

template <class T>
T LinkQueue<T>::GetQueue()
{
return front->data;
}

template <class T>
T LinkQueue<T>::DeQueue()
{
Node<T>* tmp = front;
front = front->next;
T t = tmp->data;
delete tmp;
return t;
}

int main()
{
LinkQueue<int> a;
a.EnQueue( 1 );
a.EnQueue( 2 );
a.EnQueue( 3 );
cout << a.DeQueue();
cout << a.DeQueue();
cout << a.DeQueue();
}