Yığın ve Kuyruk

Yığın ve Kuyruk / Sunum 2

Yığın İçerik
 Yığın SVT
 Yığının temel işlemleri
 Pushing, popping etc.
 Yığının gerçekleştirilmesi
 dizilerle
 bağlantılı listelerle
Yığın ve Kuyruk / Sunum 3

Yığın SVT
 Yığın kısıtlanmış bir liste olarak tanımlanabilir.
 ekleme ve silme sadece listenin tepesinden (top) yapılabilir.

 Diğer uç alt (bottom) olarak isimlendirilir.

 Temel İşlemler:
 Push: ekle işleminin eşdeğeridir
 Pop: en son eklenen elemanı siler
 Top: en son eklenen elemanı pozisyonunu tutar.
Yığın ve Kuyruk / Sunum 4

Yığın SVT
 Yığınların esnekliği sınırlıdır.
 fakat uygulanması daha etkili ve kolaydır.
 Yığınlar LIFO (Last In, First Out) listeler olarak
bilinirler.
 Eklenen en son eleman, her zaman çağrılan ilk
eleman olacaktır.
 Yığın ve Kuyruk / Sunum 5

Push ve Pop
 Birincil işlemler : Push and Pop
 Push
 Yığının tepesine bir eleman ekle
 Pop
 Yığının tepesindeki elemanı sil

boş yığın push:eleman ekle push:yeni pop

eleman ekle

top
B
top top A
A A
tepe(top)
Yığın ve Kuyruk / Sunum 6

Yığınların Gerçekleştirilmesi
 Bir yığını gerçekleştirmek için herhangi bir
liste gerçekleştirilmesi kullanılabilir.
 Diziler (statik: en başta yığının boyutu belirtilmeli)
 Bağlantılı listeler (dinamik: asla dolmaz)
 Dizi ve bağlantılı liste gerçekleştirmeleri
görülecek.
 Öncelikle dizi gerçekleştirmesini görelim.
Yığın ve Kuyruk / Sunum 7

Dizi Gerçekleştirmesi
 En başta dizi boyutunun belirtilmesi gerekir.
 Her yıpında TopOfStack bilgisi tutulur.
 boş bir yığın için , TopOfStack -1 olarak ayarlanır.
 Push
 (1) TopOfStack değerini 1 arttır.
 (2) Yığın[TopOfStack] = X atamasını yap.
 Pop
 (1) Return deperine Stack[TopOfStack] olarak ayarla.
 (2) TopOfStack değerini 1 azalt.
 Bu işlemler çok hızlı yapılır. Karmaşıklığı sabit zamandır.
Yığın ve Kuyruk / Sunum 8

Stack sınıfı
class Stack {
public:
Stack(int size = 10); // constructor
~Stack() { delete [] values; } // destructor
bool IsEmpty() { return top == -1; }
bool IsFull() { return top == maxTop; }
double Top();
void Push(const double x);
double Pop();
void DisplayStack();
private:
int maxTop; // max stack size = size - 1
int top; // current top of stack
double* values; // element array
};
Yığın ve Kuyruk / Sunum 9

Stack sınıfı
 Stack in özellikleri
 maxTop: yığının maksimum boyutu
 top: yığının tepesini gösteren indeks
 values: yığın elemanlarını depolayan diziyi işaret eder.
 Stack in işlemleri
 IsEmpty: eğer yığın boş ise true, diğer durumda ise false dönderir.
 IsFull: yığın dolu ise true, diğer durumda ise false dönderir.
 Top: yığının tepe indeksinin dönderir.
 Push: yığının tepesine eleman ekler.
 Pop: yığının tepesinden eleman siler.
 DisplayStack: yığındaki bütün elemanları ekrana yazar.
Yığın ve Kuyruk / Sunum 10

Yığın Oluşturma
 Stack ın kurucusu (constructor)
 size kadar bir yığın dizisi yeri ayır. Varsayılan (default)
size = 10.
 Yığın dolduğunda, top maksimum değeri alacak, yani size – 1.
 En başta top değeri -1 dir. Bu yığının boş olduğunu gösterir.

Stack::Stack(int size /*= 10*/) {

maxTop = size - 1;
values = new double[size];
top = -1;
}

Kurucu yığın dizisi için dinamik olarak yer ayırmasına rağmen,

yığın hala statiktir. Dizi boyutu başlatıldıktan (initialization)
sonra sabitlenir.
Yığın ve Kuyruk / Sunum 11

Yığına Ekleme (Push)

 void Push(const double x);
 Yığının tepesine eleman ekle
 Eğer yığın dolu ise, hata mesajı ver.
 top her zaman en üstteki elemanı temsil eder. Bir eleman
ekledikten sonra, top değerini 1 arttır.

void Stack::Push(const double x) {

if (IsFull())
cout << "Error: the stack is full." << endl;
else
values[++top] = x;
}
Yığın ve Kuyruk / Sunum 12

Yığından Silme (Pop)

 double Pop()
 Yığının tepesindeki elemanı dönder.
 Eğer yığın boş ise, hata mesajı ver. (Bu durumda
geri dönen değer faydasızdır.)
 top değeri 1 azaltılır.
double Stack::Pop() {
if (IsEmpty()) {
cout << "Error: the stack is empty." << endl;
return -1;
}
else {
return values[top--];
}
}
Yığın ve Kuyruk / Sunum 13

Yığının Tepesi (Top)

 double Top()
 Yığının tepesindeki elemanı dönder.
 Pop olduğu gibi, bu fonksiyon yığının tepedeki
elemanı silmez.

double Stack::Top() {
if (IsEmpty()) {
cout << "Error: the stack is empty." << endl;
return -1;
}
else
return values[top];
}
Yığın ve Kuyruk / Sunum 14

Bütün elemenları yazma

 void DisplayStack()
 Bütün elemanları yazar.

void Stack::DisplayStack() {
cout << "top -->";
for (int i = top; i >= 0; i--)
cout << "\t|\t" << values[i] << "\t|" << endl;
cout << "\t|---------------|" << endl;
}
Yığın ve Kuyruk / Sunum 15

Stack kullanımı
result
int main(void) {
Stack stack(5);
[Link](5.0);
[Link](6.5);
[Link](-3.0);
[Link](-8.0);
[Link]();
cout << "Top: " << [Link]() << endl;

[Link]();
cout << "Top: " << [Link]() << endl;
while (![Link]()) [Link]();
[Link]();
return 0;
}
Yığın ve Kuyruk / Sunum 16

Bağlantılı Liste tabanlı Gerçekleştirmesi

 List kodunu en iyi şekilde kullanabilmek
için, Stack’i List‘i inherit ederek
gerçekleştirebiliriz.
 Stack’in private üye olan head’e erişimi sağlamak
için, Stack’ı List’in arkadaşı (friend) yaparız.

class List {
public:
List(void) { head = NULL; } // constructor
~List(void); // destructor
bool IsEmpty() { return head == NULL; }
Node* InsertNode(int index, double x);
int FindNode(double x);
int DeleteNode(double x);
void DisplayList(void);
private:
Node* head;
friend class Stack;
};
Yığın ve Kuyruk / Sunum 17

Bağlantılı Liste tabanlı Gerçekleştirmesi

class Stack : public List {
public:
Stack() {} // constructor
~Stack() {} // destructor
double Top() {
if (head == NULL) {
cout << "Error: the stack is empty." << endl;
return -1;
}
else
return head->data;
}
void Push(const double x) { InsertNode(0, x); }
double Pop() {
if (head == NULL) {
cout << "Error: the stack is empty." << endl;
return -1;
}
else {
double val = head->data;
DeleteNode(val); Note: the stack
return val;
} implementation
} based on a linked
void DisplayStack() { DisplayList(); }
}; list will never be full.
Yığın ve Kuyruk / Sunum 18

Sembollerin Takip Edilmesi

 Parantez veya köşeli parantez açma yine parantez
veya köşeli parantez kapama ile bitmeli
 örnek [( )] doğru, fakat [( ] ) yanlış
 Algoritma
(1) Boş bir yığın yap.
(2) Dosya sonuna kadar karakterleri oku
i. Eğer karakter açma sembolü ise, yığına ekle
ii. Eğer parantez kapama sembolü ise yığını boşalt ve hata rapor et.
iii. Diğer durumda yığından sil. Eğer silinen sembol açma sembolünün
karşılığı değilse hata rapor et.
(3) Dosya sonunda, eğer yığın boş değilse hata mesajı ver.
Yığın ve Kuyruk / Sunum 19

Sonek (Postfix) İfadeleri

 4.99 * 1.06 + 5.99 + 6.99 * 1.06 hesapla
 Öncelik kurallarını bilmek gerekiyor
 Sonek ifadeleri
 4.99 1.06 * 5.99 + 6.99 1.06 * +
 Sonek ifadelerini hesaplamak için yığın kullan
 Bir sayı geldiğinde, yığına ekle
 Bir işlem geldiğinde, işlem yığından pop edilen iki sayı
üzerine uygulanır. Sonuç yığına eklenir.
 Örnek
 hesapla 6 5 2 3 + 8 * + 3 + *
 Sonek ifadelerini hesaplamanın zaman karmaşıklığı
O(N)
 girişteki her bir elemanın işlenmesi yığın işlemlerini içerir ve
böylece sabit zaman karmaşıklığına sahiptir.
Yığın ve Kuyruk / Sunum 20
Yığın ve Kuyruk / Sunum 21

Kuyruk İçerik
 Kuyruk SVT
 Temek kuyruk işlemleri
 Enqueuing, dequeuing etc.
 Kuyruk gerçekleştirmesi
 Dizi
 Bağlantılı Liste
Yığın ve Kuyruk / Sunum 22

Kuyruk SVT
 Yığın gibi, kuyruk (queue ) da bir listedir.
Fakat, kuyrukta, ekleme bir uçtan yapılırken,
silme diğer uçtan yapılır.
 Kuyruk elemanlarına erişim First In, First Out
(FIFO) düzeni şeklindedir.
 Bir markette ödemeyi yapmak için bekleyen
müşteriler gibi, sıradaki ilk müşteri ödemeyi yapan
ilk kişi olacaktır.
Yığın ve Kuyruk / Sunum 23

Kuyruk SVT
 Listenin diğer bir sınırlandırılmış şeklidir.
 Ekleme bir uçtan yapılırken, silme de diğer uçtan yapılır.
 Temel işlemler:
 enqueue: en arkaya (rear) eleman ekleme
 dequeue: listenin başından eleman silme

 First-in First-out (FIFO) liste

Yığın ve Kuyruk / Sunum 24

Enqueue ve Dequeue
 Birincil kuyruk işlemleri: Enqueue and Dequeue
 Marketteki ödeme sırası gibi, kuyrukta bir ön vardır
birde arka
 Enqueue
 Kuyruğun arkasına eleman ekleme
 Dequeue
 Kuyruğun önünden eleman silme

Remove Insert
(Dequeue) ön arka (Enqueue)
Yığın ve Kuyruk / Sunum 25

Kuyruğun Gerçekleştirilmesi
 Yığınlar gibi diziler ve bağlantılı listeler ile
gerçekleştirilebilir
 Dinamik kuyrukların, statik kuyruklara avantajı
dinamik yığınların, static yığınlara olan
avantajı gibidir.
Yığın ve Kuyruk / Sunum 26

Kuyruğun Dizilerle Gerçekleştirilmesi

 Enqueue ve Dequeue işlemlerinin
gerçekleştirilmesi için çeşitli algoritmalar
vardır.
 En basiti
 enqueue işleminde ön indeks daima sabittir ve
arka indeks dizide ileri doğru hareket eder.
rear rear rear

3 3 6 3 6 9

front front front

Enqueue(3) Enqueue(6) Enqueue(9)
Yığın ve Kuyruk / Sunum 27

Kuyruğun Dizilerle Gerçekleştirilmesi

 (Toy Yaklaşım) Naïve way
 enqueue işleminde ön indeks daima sabittir ve
arka indeks dizide ileri doğru hareket eder.
 dequeue işleminde, kuyruğun önündeki eleman
silinir. Diğer bütün elemanlar bir öne kayar. (etkili
değil!!!)
rear rear rear = -1

6 9 9

front front front

Dequeue() Dequeue() Dequeue()
Yığın ve Kuyruk / Sunum 28

Kuyruğun Dizilerle Gerçekleştirilmesi

 Daha iyi yol
 Bir eleman enqueue olduğunda arka indeksi ileri
hareket ettir.
 Bir eleman dequeue olduğunda, ön indeks kuyruğun
arkasına bir eleman hareket eder. (Böylece ön
elemanı siler ve komşu elemanları kopyalayıp taşıma
olmaz.).

(front)XXXXOOOOO (rear)
OXXXXOOOO (1 dequeuedan sonra, ve 1 enqueue)
OOXXXXXOO (diğer 1 dequeuedan sonra, ve 2 enqueues)
OOOOXXXXX (2 dequeuesdan sonra, ve 2 enqueues)
Buradaki problem, arka indeks dizinin son hücresinden sonra
ileri gidemez.
Yığın ve Kuyruk / Sunum 29

Dairesel Diziler kullanarak Gerçekleştirilmesi

 Dairesel diziler kullanarak
 Dairesel dizide son elemana ulaşınca, dizinin
başından itibaren sarmaya devam edilir.
 OOOOO7963  4OOOO7963 (Enqueue(4)’ den sonra )
 Enqueue(4)’ den sonra, arka indeks 3’ten 4’ e kayar.
Yığın ve Kuyruk / Sunum 30
Yığın ve Kuyruk / Sunum 31

Boş veya Dolu?

 Boş kuyruk
 arka = ön - 1
 Dolu kuyruk?
 aynı!
 Sebep: n+1 durumu göstermek n değer vardır
 Çözümler
 Kuyruğun boş olup olmadığını gösterecek boolean bir
değişken kullanılması
 Dizinin boyutunu n+1 yap ve sadece n elemanın
depolanmasına izin ver
 Kuyruktaki elemanların sayısını tutan bir sayaç kullan.
 Kuyruğun Dizi kullanılarak
Yığın ve Kuyruk / Sunum 32

Gerçekleştirilmesi
class Queue {
public:
Queue(int size = 10); // constructor
~Queue() { delete [] values; } // destructor
bool IsEmpty(void);
bool IsFull(void);
bool Enqueue(double x);
bool Dequeue(double & x);
void DisplayQueue(void);
private:
int front; // front index
int rear; // rear index
int counter; // number of elements
int maxSize; // size of array queue
double* values; // element array
};
Yığın ve Kuyruk / Sunum 33

Queue Sınıfı
 Kuyruk özellikleri
 front/rear: ön/arka indeks
 counter: kuyruktaki eleman sayısı
 maxSize: kuyruğun kapasitesi
 values: kuyruğun elemanlarını depolayan bir diziye işaret eder
 Kuyruk İşlemleri
 IsEmpty: kuyruk boş ise true, diğer durumda false dönder
 IsFull: kuyruk dolu ise true, yoksa false dönder
 Enqueue: kuyruğun arkasına bir eleman ekle
 Dequeue: kuyruktan bir eleman sil
 DisplayQueue: verinin hepsini yaz
Yığın ve Kuyruk / Sunum 34

Kuyruk Oluştur
 Queue(int size = 10)
 size boyutundan bir dizi için yer ayarla. Başlanğıçta, size = 10.
 front değeri 0, dizinin ilk elemanını gösterir.
 rear değeri -1. Başlanğıçta kuyruk boştur.

Queue::Queue(int size /* = 10 */) {

values = new double[size];
maxSize = size;
front = 0;
rear = -1;
counter = 0;
}
Yığın ve Kuyruk / Sunum 35

IsEmpty & IsFull

 counter, kullanılarak dizinin boş mu dolu mu
olduğunu anlamak kolaydır.

bool Queue::IsEmpty() {
if (counter) return false;
else return true;
}
bool Queue::IsFull() {
if (counter < maxSize) return false;
else return true;
}
Yığın ve Kuyruk / Sunum 36

Enqueue
bool Queue::Enqueue(double x) {
if (IsFull()) {
cout << "Error: the queue is full." << endl;
return false;
}
else {
// calculate the new rear position (circular)
rear = (rear + 1) % maxSize;
// insert new item
values[rear] = x;
// update counter
counter++;
return true;
}
}
Yığın ve Kuyruk / Sunum 37

Dequeue
bool Queue::Dequeue(double & x) {
if (IsEmpty()) {
cout << "Error: the queue is empty." << endl;
return false;
}
else {
// retrieve the front item
x = values[front];
// move front
front = (front + 1) % maxSize;
// update counter
counter--;
return true;
}
}
Yığın ve Kuyruk / Sunum 38

Elemanların Yazılması

void Queue::DisplayQueue() {
cout << "front -->";
for (int i = 0; i < counter; i++) {
if (i == 0) cout << "\t";
else cout << "\t\t";
cout << values[(front + i) % maxSize];
if (i != counter - 1)
cout << endl;
else
cout << "\t<-- rear" << endl;
}
}
Yığın ve Kuyruk / Sunum 39

Queue Kullanımı

int main(void) {
Queue queue(5);
cout << "Enqueue 5 items." << endl;
for (int x = 0; x < 5; x++)
[Link](x);
cout << "Now attempting to enqueue again..." << endl;
[Link](5);
[Link]();
double value;
[Link](value);
cout << "Retrieved element = " << value << endl;
[Link]();
[Link](7);
[Link]();
return 0;
}
Yığın ve Kuyruk / Sunum 40

Bağlantılı Liste kullanılarak Yığın

class Queue { Gerçekleştirilmesi
public:
Queue() { // constructor
front = rear = NULL;
counter = 0;
}
~Queue() { // destructor
double value;
while (!IsEmpty()) Dequeue(value);
}
bool IsEmpty() {
if (counter) return false;
else return true;
}
void Enqueue(double x);
bool Dequeue(double & x);
void DisplayQueue(void);
private:
Node* front; // pointer to front node
Node* rear; // pointer to last node
int counter; // number of elements
};
Yığın ve Kuyruk / Sunum 41

Enqueue
void Queue::Enqueue(double x) {
Node* newNode = new Node;
newNode->data = x;
newNode->next = NULL;
if (IsEmpty()) {
front = newNode;
rear = newNode;
} rear

else { 8 5
rear->next = newNode;
rear = newNode;
rear
}
counter++; 8 5
} newNode
Yığın ve Kuyruk / Sunum 42

Dequeue
bool Queue::Dequeue(double & x) {
if (IsEmpty()) {
cout << "Error: the queue is empty." << endl;
return false;
}
else {
x = front->data;
Node* nextNode = front->next;
delete front;
front = nextNode;
counter--;
} front
}
3 8 5

front

8 5
Yığın ve Kuyruk / Sunum 43

Bütün Elemanların Yazdırılması

void Queue::DisplayQueue() {
cout << "front -->";
Node* currNode = front;
for (int i = 0; i < counter; i++) {
if (i == 0) cout << "\t";
else cout << "\t\t";
cout << currNode->data;
if (i != counter - 1)
cout << endl;
else
cout << "\t<-- rear" << endl;
currNode = currNode->next;
}
}
Yığın ve Kuyruk / Sunum 44

Sonuç
 Bağlantılı liste kullanılarak yapılan kuyruk asla
dolmayacaktır

Dizi kullanılarak Bağlantılı liste kullanılarak