Реализация АТД "Стек" и "Очередь"

Задание:

1. Реализовать программу-клиента, использующую АТД «Стек», реализованный на базе массива и на базе связного списка.
2. Реализовать программу-клиента, использующую АТД «Очередь», реализованный на базе массива и на базе связного списка.

Листинг программы:

 

#include <iostream>

#include <conio.h>

void StackMassiv();

void StackList();

void QueueMassiv();

void QueueList();

int main();

 

using namespace std;

 

template <class Item>

class STACK

{

    private:

Item *s; int N;

   

public:

STACK (int maxN)

{

s = new Item [maxN]; N=0;

}

int empty() const

{

return N==0;

}

void push (Item item)

{

s[N++]=item;

}

Item pop()

{ 

s[--N]='_';

return s[N];

}

void print(int N)

{

cout<<endl;

for (int i=0;i<N;i++)cout<<s[i]<<" ";

}

};

 

template <class Item_List>

class STACK_List

{

    private:

        struct node

        {

            Item_List item;

            node *next;

            node (Item_List x, node *t)

            {

                item = x;

                next = t;

            }

        };

typedef node * link;

link head;

    public:

STACK_List (Item_List)

{

head = 0;

}

 

int empty() const {return head==0;}

void push (Item_List x){head = new node(x,head);}

 

Item_List pop()

{

Item_List V = head->item;

link t = head->next;

delete head;

head = t;

return V;

}

    void print()

    {

        cout<<endl;

link  p;

for(p=head;  p;  p=p->next)

                cout<<p->item<<" ";

    }

};

 

template <class item>

class QUEUE

{

    private:

item *q; int N, head,tail;

    public:

 

QUEUE (int maxN)

{q = new item [maxN+1];

N=maxN+1;

head = N;

tail = 0;}

int empty()const {return head%N==tail;}

void put(item x)

{

q[tail++]=x; tail=tail%N;

}

item get()

{

head=head%N; q[head]=0;

return q[head++];

}

void print(int N)

{

cout<<endl;

for (int i=0;i<N;i++)cout<<q [i]<<" ";

}

};

 

template<class itemList>

class QUEUE_List

{

    private:

struct node

{

itemList item; node * next; node (itemList x)

{

item=x; next = 0;

}

};

typedef node *link;

link head,tail;

    public:

QUEUE_List(itemList){

head=0;

}

int empty()const

{

return head==0;

}

void put(itemList x)

{

link t = tail; tail = new node(x); if (head ==0)head=tail; else t->next=tail;

}

itemList get()

{

itemList v = head->item;

link t = head->next;

delete head;

head = t;

return v;

}

 

void print()

{

cout<<endl;

link  p;

for(p=head;  p;  p=p->next)

                cout<<p->item<<" ";

}

};

 

 

 

int main()

{

int MainMenu=1;

while (MainMenu!=0) {

 

cout<<"To choose ATI 'StackMassiv' press 1"<<endl;

cout<<"To choose ATI 'StackList'   press 2"<<endl;

cout<<"To choose ATI 'QueueMassiv' press 3"<<endl;

cout<<"To choose ATI 'QueueList'   press 4"<<endl;

cout<<"Press 0 to Exit"<<endl;

cin>>MainMenu;

switch(MainMenu)

{

 

case 0: exit(1);

case 1: StackMassiv(); break;

case 2: StackList(); break;

case 3: QueueMassiv(); break;

case 4: QueueList(); break;

}

}

getch();

return 0;

}

void StackMassiv()

{

 

const int N=20;

int SubMenu=1;

char el;

STACK< int > mas(N);

 

while(SubMenu != 0){

system("cls");

 

cout<<"Press 1 to Push"<<endl;

cout<<"Press 2 to Pop"<<endl;

cout<<"Press 0 to Exit"<<endl;

mas.print(N);

cin>>SubMenu;

switch (SubMenu)

{

case 0:

exit (1);

case 1:

system("cls");

cin>>el;

 

mas.push(el);

 

break;

case 2:

system("cls");

mas.pop();

 

break;

}

}

 

getch();

}

void StackList()

{

 

const int N=20;

int SubMenu=1;

char el;

STACK_List< int > List(N);

 

while(SubMenu != 0){

 

system("cls");

 

cout<<"Press 1 to Push"<<endl;

cout<<"Press 2 to Pop"<<endl;

cout<<"Press 0 to Exit"<<endl;

List.print();

cin>>SubMenu;

switch (SubMenu)

{

case 0:

exit (1);

case 1:

system("cls");

cin>>el;

 

List.push(el);

 

break;

case 2:

system("cls");

List.pop();

 

break;

}

}

 

getch(); 

}

void QueueMassiv()

{

 

const int N=20;

int SubMenu=1;

char el;

QUEUE < int > oc_mas(N);

 

while(SubMenu != 0){

system("cls");

 

cout<<"Press 1 to Put"<<endl;

cout<<"Press 2 to Get"<<endl;

cout<<"Press 0 to Exit"<<endl;

oc_mas.print(N);

cin>>SubMenu;

switch (SubMenu)

{

case 0:

exit (1);

case 1:

system("cls");

cin>>el;

 

oc_mas.put(el);

 

break;

case 2:

system("cls");

oc_mas.get();

 

break;

}

}

 

getch();

}

void QueueList()

{

 

const int N=20;

int SubMenu=1;

char el;

QUEUE_List< int > List_oc(N);

 

while(SubMenu != 0){

 

system("cls");

 

cout<<"Press 1 to Put"<<endl;

cout<<"Press 2 to Get"<<endl;

cout<<"Press 0 to Exit"<<endl;

List_oc.print();

cin>>SubMenu;

switch (SubMenu)

{

case 0:

exit (1);

case 1:

system("cls");

cin>>el;

 

List_oc.put(el);

 

break;

case 2:

system("cls");

List_oc.get();

 

break;

}

}

getch(); 

}

 

 

 

Главное меню:

 

.

Пункт 1, порядок введения символов – 1,2,3,4,5

 

 

Удаление двух символов:

 

 

Пункт 2, порядок введения символов – 1,2,3,4,5

 

 

Удаление двух символов:

 

 

 

 

Пункт 3, порядок введения символов – 1,2,3,4,5

 

 

 

Удаление двух символов:

 

 

Пункт 4, порядок введения символов – 1,2,3,4,5

 

 

Удаление двух символов: