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; 

}