Cvičení 3

Implementace obousměrného kruhového seznamu a zásobníku.
Dobrovolný úkol:

• doplňte metody třídy LinkedList
• rozšiřte příklady použití
• a implementujte podobným způsobem frontu

soubor list.h

#ifndef _LIST_H
#define _LIST_H

struct ListNode {
  ListNode *mpNext, *mpPrev;
  int mData;
};

class LinkedList {
  public:
      LinkedList();      
      LinkedList(int *array, int size);
      LinkedList(LinkedList&);
      ~LinkedList();

      void append(int data);
      void prepend(int data);
      void joinWith(LinkedList& other);

      int popLast();
      int popFirst();
      bool isEmpty() const;

      void print();
  private:
      ListNode *mpFirst;
};

class Stack {
  public:
      void push(int);
      int pop();
      bool isEmpty() const;
      void print();
  private:
      LinkedList mList;
};

#endif

soubor list.cpp

#include <iostream>

#include "list.h"

using namespace std;

LinkedList::LinkedList(): mpFirst(NULL) {}

LinkedList::LinkedList(int *array, int size)
{
}

LinkedList::LinkedList(LinkedList& list)
{
mpFirst = NULL;
if (list.mpFirst != NULL)
{
 ListNode *actual = list.mpFirst;
 do {
  append(actual->mData);
  actual = actual->mpNext;
 } while (actual != list.mpFirst);
}
}

LinkedList::~LinkedList()
{
if (mpFirst != NULL)
{
 ListNode *item = mpFirst;
 while (item->mpNext != mpFirst) {
  item = item->mpNext;
  delete item->mpPrev;
 }
 delete mpFirst;
 mpFirst = NULL;
}
}

void LinkedList::append(int data) {
if (mpFirst == NULL) {
 mpFirst = new ListNode;
 mpFirst->mData = data;
 mpFirst->mpNext = mpFirst;
 mpFirst->mpPrev = mpFirst;
} else {
 ListNode *newItem = new ListNode;
 newItem->mData = data;
 newItem->mpNext = mpFirst;
 newItem->mpPrev = mpFirst->mpPrev;
 mpFirst->mpPrev = newItem;
 newItem->mpPrev->mpNext = newItem;
}
}

void LinkedList::prepend(int data)
{
append(data);
mpFirst = mpFirst->mpPrev;
}

void LinkedList::joinWith(LinkedList& other)
{
}

int LinkedList::popLast()
{
if (mpFirst == NULL)
{
 cerr << "ERROR: removing items from empty list" << endl;
 exit(1);
} else {
 ListNode *item = mpFirst->mpPrev;
 int value;
 if (item->mpNext == item)
 {
  mpFirst = NULL;
 }
 item->mpPrev->mpNext = item->mpNext;
 item->mpNext->mpPrev = item->mpPrev;
 value = item->mData;
 delete item;
 return value;
}
}

int LinkedList::popFirst()
{
int value;
mpFirst = mpFirst->mpNext;
return popLast();
}

bool LinkedList::isEmpty() const
{
return mpFirst == NULL;
}

void LinkedList::print()
{
if (mpFirst == NULL)
{
 cout << "[]" << endl;
} else {
 cout << "[";
 ListNode *actual = mpFirst;
 while (1)
 {
  cout << actual->mData;
  actual = actual->mpNext;
  if (actual == mpFirst)
  {
   break;
  }
  cout << ", ";
 }
 cout << "]" << endl;
}
}

void Stack::push(int data)
{
mList.append(data);
}

int Stack::pop()
{
return mList.popLast();
}

bool Stack::isEmpty() const
{
return mList.isEmpty();
}

void Stack::print()
{
mList.print();
}

soubor priklad3.cpp

#include <iostream>
#include "list.h"

using namespace std;

int main(int argc, char **argv) {
LinkedList list;
for (int i=1; i<=5; i++)
{
 list.append(i);
}
LinkedList list2(list);
list2.popFirst();
list2.popLast();
list2.print();
list.print();

cout << "priklad na zasobnik" << endl;
Stack s;
for (int i=1; i<=5; i++)
{
 s.push(i);
}
while(!s.isEmpty()) {
 cout << s.pop() << endl;
}
return 0;
}