Algorytmy i struktury danych,

Ć wiczenia

VII

27.11.2012r.

Lista 7

Zapoznać się z klasa dotyczącą tworzenia stosu zaimplementowaną w używanym oprogramowaniu.
Zdefiniować klasę do obsługi stosu przy użyciu tablicy lub klasy VECTOR lub zdefiniować własną klasę
do obsługi stosu przy użyciu tablicy

Zadanie 1

a. z danego stosu liczb całkowitych zdejmując elementy utworzyć dwa stosy – jeden złożony

z liczb parzystych, drugi z liczb nieparzystych

b. Sprawdzić czy na stosie są dwa identyczne elementy

#include

"stdafx.h"

#include

<iostream>

#include

<stack>

#include

<time.h>

using

namespace

std;

int

_tmain(

int

argc, _TCHAR* argv[]){

srand(time(NULL));

stack <

int

> losowy;

stack <

int

> parzyste;

stack <

int

> nieparzyste;

stack <

int

> stos1;

stack <

int

> stos2;

int

temp;

int

licz, liczba;

bool

powtorzenie=0;

for

(

int

i=0; i<20; i++){

losowy.push(rand()%100);

stos1.push(losowy.top());

}

cout <<

"Stos\n"

;

while

(!losowy.empty()){

cout << losowy.top() <<

" "

;

if

(losowy.top()%2==0)

parzyste.push(losowy.top());

else

nieparzyste.push(losowy.top());

losowy.pop();

}

cout <<

"\n\nLiczby parzyste\n"

;

while

(!parzyste.empty()){

cout << parzyste.top() <<

" "

;

parzyste.pop();

}

cout <<

"\n\nLiczby nieparzyste\n"

;

while

(!nieparzyste.empty()){

cout << nieparzyste.top() <<

" "

;

nieparzyste.pop();

}

for

(

int

i=0; i<20; i++){

temp=stos1.top();

stos1.pop();

licz=0;

for

(

int

j=i+1; j<21-licz; j++){

if

(temp==stos1.top()){

powtorzenie=1;

liczba=temp;

break

;

}

stos2.push(stos1.top());

stos1.pop();

licz++;

}

for

(

int

j=0; j<licz;j++){

stos1.push(stos2.top());

stos2.pop();

}

if

(powtorzenie==1)

break

;

if

(i==20)

break

;

}

if

(powtorzenie==1) cout<<

"\nPowtara sie: "

<<liczba<<endl;

else

cout<<

"\nNie powtarzaja sie zadne liczby\n"

;

system(

"pause"

);

return

0;

}

Zadanie 2

a. Sprawdzić czy w danym fragmencie kodu programu każdy nawias otwierający na swój

odpowiednik zamykający

b. Użyć stosu do odwrócenia kolejności liter tekstu

#include

"stdafx.h"

#include

<iostream>

#include

<stack>

#include

<string>

using

namespace

std;

int

_tmain(

int

argc, _TCHAR* argv[]){

stack <

int

> stos1;

stack <string> stos2;

bool

k=0;

string n, temp;

cin>>n;

for

(

int

i=0; i<n.length(); i++){

if

(n[i]==

'{'

)

stos1.push(

'{'

);

if

(n[i]==

'}'

&& !stos1.empty())

stos1.pop();

}

if

(!stos1.empty())cout<<

"\nZa malo znakow '{' lub '}' "

<<endl;

if

(stos1.empty()) cout<<

"\nTaka sama ilosc '{' i '}' "

<<endl;

for

(

int

i=0; i<n.length(); i++){

temp=n[i];

stos2.push(temp);

}

while

(!stos2.empty()){

cout << stos2.top();

stos2.pop();

}

cout<<endl;

system(

"pause"

);

return

0;

}

Zadanie 3

a. Dany jest stos S liczb całkowitych. Używając standardowych operacji na stosie podać

algorytm Stos uporządkowany, który ustawia elementy na stosie S w porządku rosnącym (na
szczycie jest element największy). Można korzystać z jednego pomocniczego stosu P i kilku
(skończonej liczby) zmiennych.

b. Dane są: stos A i pusty stos B. Używając standardowych funkcji obsługi stosów usunąć ze

stosu A element o najmniejszej wartości położony najgłębiej (w stosie może być kilka
elementów o tej samej najmniejszej wartości).

#include

"stdafx.h"

#include

<iostream>

#include

<stack>

#include

<time.h>

using

namespace

std;

int

_tmain(

int

argc, _TCHAR* argv[]){

srand(time(NULL));

stack <

int

> stos1;

stack <

int

> stos2;

stack <

int

> stos3;

int

temp, min, indeks=0;

cout<<

"Stos nieposortowany\n"

;

for

(

int

i=0; i<20; i++){

stos1.push(rand()%100);

stos3.push(stos1.top());

cout<<stos1.top()<<

" "

;

if

(i==0) min=stos1.top();

if

(stos1.top()<=min){

min=stos1.top();

indeks=i;

}

}

cout <<

"\n\nStos posortowany\n"

;

stos2.push(stos1.top());

stos1.pop();

while

(!stos1.empty()){

if

(stos1.top()<=stos2.top()){

stos2.push(stos1.top());

stos1.pop();

}

else

{

temp=stos1.top();

stos1.pop();

while

(!stos2.empty() && stos2.top()<=temp){

stos1.push(stos2.top());

stos2.pop();

}

stos2.push(temp);

}

}

while

(!stos2.empty()){

cout << stos2.top() <<

" "

;

stos2.pop();

}

cout<<endl;

int

i=0;

cout<<

"\n\nStos bez najmniejszej wartosci bedacej najglebiej\n "

<<endl;

while

(!stos3.empty()){

if

(i!=19-indeks)

stos1.push(stos3.top());

stos3.pop();

i++;

}

while

(!stos1.empty()){

cout << stos1.top() <<

" "

;

stos1.pop();

}

system(

"pause"

);

return

0;

}