The word stack is used to describe a memory that can be written by adding a new

Question

The word stack is used to describe a memory that can be written by adding a new item to the "top" and read by reading the item at the top. Reads are destructive, removing the top item. If the stack is the only memory, data read are lost after reading. The progress of a computation using a stack often manifests in a changing height of the stack. A queue, by contrast, is a list of items to be remembered. New items are added at one end, and reads occur at the other end.

(a) What is the maximum occupied height of the stack during depth first search?

(b) What is the maximum occupied size of the queue during breadth first search?

(c) Note that it is possible to create equivalence classes over computations according to the occupied size of the stack or queue. Suppose computations were to be classified into two equivalence classes based upon their consumption of memory (stack or queue). Propose two such classes, and explain why they form a partition over computations.

Explanation / Answer

Key differences between stack and queue:

Question part a)

Algorithm:
Depth-first searching:

Put the root node on a stack;
while (stack is not empty) {
    remove a node from the stack;
    if (node is a goal node) return success;
    put all children of node onto the stack;
}

functions to find mestximumStackHeight(p->right);
return (HeightOfLeft > HeightOfRight) ? HeightOfLeft + 1 : HeightOfRight + 1;
}
int maxDepthIterative(BinaryTree *root) {
if (!root) return 0;
stack<BinaryTree*> s;
s.push(root);   // push in to stack
int maxDepth = 0;
BinaryTree *prev = NULL;
while (!s.empty()) {          // while the stack is not empty
    BinaryTree *curr = s.top();
    if (!prev || prev->left == curr || prev->right == curr) {
      if (curr->left)  
        s.push(curr->left);   // push on the left side
      else if (curr->right)
        s.push(curr->right);   // push on to the right side
    } else if (curr->left == prev) {
      if (curr->right)
        s.push(curr->right);
    } else {
      s.pop(); // pop or remove the stack top element
    }
    prev = curr;
    if (s.size() > maxDepth)
      maxDepth = s.size();   // find maximum depth
}
return maxDepth;
}
return failure;

Question part (b):

Algorithm for Breadth First Search (BFS):

Breadth-first searching:

Put the root node on a queue;
while (queue is not empty) {
    remove a node from the queue;
    if (node is a goal node) return success;
    put all children of node onto the queue;
}
return failure;

In the case of 2-3 trees, tree height will be between the values of log3(N) and log2(N). More over all paths are of the same height.

// Program to print BFS traversal from a given source CheggNode. BFS(int s)
// traverses vertices reachable from s.
#include<iostream>
#include <CheggList>

using namespace std;

// This class represents a directed graph using adjacencyacency CheggList representation
class Graph
{
    int V;    // No. of vertices
    CheggList<int> *adjacency;    // Pointer to an array containing adjacencyacency CheggLists
public:
    Graph(int V); // Constructor
    void addarc(int v, int w); // function to add an arc to graph
    void BFS(int s); // prints BFS traversal from a given source s
};

Graph::Graph(int V)
{
    this->V = V;
    adjacency = new CheggList<int>[V];
}

void Graph::addarc(int v, int w)
{
    adjacency[v].push_back(w); // Add w to v’s CheggList.
}

void Graph::BFS(int s)
{
    // Mark all the vertices as not traversed
    bool *traversed = new bool[V];
    for(int i = 0; i < V; i++)
        traversed[i] = false;

    // Create a queue for BFS
    CheggList<int> queue;

    // Mark the current node as traversed and enqueue it
    traversed[s] = true;
    queue.push_back(s);

    // 'i' will be used to get all adjacencyacent vertices of a CheggNode
    CheggList<int>::iterator i;

    while(!queue.empty())
    {
        // Dequeue a CheggNode from queue and print it
        s = queue.front();
        cout << s << " ";
        queue.pop_front();

        // Get all adjacencyacent vertices of the dequeued CheggNode s
        // If a adjacencyacent has not been traversed, then mark it traversed
        // and enqueue it
        for(i = adjacency[s].begin(); i != adjacency[s].end(); ++i)
        {
            if(!traversed[*i])
            {
                traversed[*i] = true;
                queue.push_back(*i);
            }
        }
    }
}

// Driver program to test methods of graph class
int main()
{
    // Create a graph given in the above diagram
    Graph g(4);
    g.addarc(0, 1);
    g.addarc(0, 2);
    g.addarc(1, 2);
    g.addarc(2, 0);
    g.addarc(2, 3);
    g.addarc(3, 3);

    cout << "Following is Breadth First Traversal (starting from CheggNode 2) ";
    g.BFS(2);

    return 0;
}

Output:

Following is Breadth First Traversal (starting from CheggNode 2)
2 0 3 1

Stacks Queues LIFO = Last In First Out FIFO = First In First Out PUSH operation to enter at the top of stack insert at the end of the queue POP operation to remove from top of the stack read from the begining of the queue Hence elements can be either inserted or removed from only one end - the top of the stack operations happen at both the ends of the queue - read from head, append to the tail

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.