Programming Exercise: Lab #4

경희대학교 박제만 교수님의 자료구조 수업을 기반으로 정리한 글입니다.

Exercise #1

Problems

• Implement linked structure STACK.
  • ~StackType(): destructor
  • size(): returns the length of stack
  • push(): pushes a new item into the stack
  • pop(): pops and returns the item at the top of stack (if the stack is empty, return -1)

StackType::~StackType()
{
    NodeType* tempPtr = topPtr;

    while (tempPtr != nullptr) {
        topPtr = topPtr->next;
        delete tempPtr;
        tempPtr = topPtr;
    }
}

▶ ~StackType()

int StackType::size() const
{
    NodeType* tempPtr = topPtr;
    int length = 0;

    while (tempPtr != nullptr) {
        length++;
        tempPtr = tempPtr->next;
    }

    return length;
}

▶ size()

void StackType::push(ItemType newItem)
{
    if (isFull()) return;

    NodeType* newNode;
    newNode = new NodeType;

    newNode->value = newItem;
    newNode->next = topPtr;
    topPtr = newNode;
}

▶ push()

ItemType StackType::pop()
{
    if (isEmpty()) return -1;

    NodeType* tempPtr = topPtr;

    topPtr = topPtr->next;
    ItemType ret = tempPtr->value;
    delete tempPtr;
    
    return ret; 
}

▶ pop()

Exercise #2

Problems

• Implement linked structure QUEUE.
  • ~QueueType(): destructor
  • size(): returns the length of queue
  • enqueue(): enqueues a new item into the queue
  • dequeue(): dequeues and returns the most front item in the queue (ret by ret). (if the queue is empty, return -1)

template <class ItemType>
QueueType<ItemType>::~QueueType()
{
    NodeType<ItemType>* tempPtr = pFront;

    while (tempPtr != nullptr) {
        pFront = pFront->next;
        delete tempPtr;
        tempPtr = pFront;
    }
    pRear = nullptr;
}

▶ ~QueueType()

template <class ItemType>
int QueueType<ItemType>::size() const
{
    NodeType<ItemType>* tempPtr = pFront;
    int length = 0;

    while (tempPtr != nullptr) {
        length++;
        tempPtr = tempPtr->next;
    }

    return length;
}

▶ size()

template <class ItemType>
void QueueType<ItemType>::enqueue(ItemType newItem)
{
    if (isFull()) return;

    NodeType<ItemType>* newNode;
    newNode = new NodeType<ItemType>;

    newNode->value = newItem;
    newNode->next = nullptr;

    if (isEmpty()) {
        pFront = newNode;
    }
    else {
        pRear->next = newNode;
    }
    pRear = newNode;
}

▶ enqueue()

template <class ItemType>
void QueueType<ItemType>::dequeue(ItemType& ret_value)
{
    if (isEmpty()) {
        ret_value = -1;
        return;
    }

    NodeType<ItemType>* tempPtr = pFront;

    pFront = pFront->next;
    ret_value = tempPtr->value;
    delete tempPtr;

    if (isEmpty()) {
        pRear = nullptr;
    }
}

▶ dequeue()

Exercise #3

Problems

• Implement "squareSum()" of Linked Structure Queue.

▶ It returns the sum of "squared values" in the queue. (node traverse)

template <class ItemType>
int QueueType<ItemType>::squareSum()
{   
    NodeType<ItemType>* tempPtr = pFront;
    int q_sum = 0;

    while (tempPtr != nullptr) {
        q_sum += (tempPtr->value) * (tempPtr->value);
        tempPtr = tempPtr->next;
    }
    
    return q_sum;
}

▶ squareSum()