1. The array implementation in this chapter keeps the top variable pointing to t

Question

1. The array implementation in this chapter keeps the top variable pointing to the
next array position above the actual top of the stack. Rewrite the array
implementation such that stack[top] is the actual top of the stack.
2. There is a data structure called a dropout stack that behaves like a stack in every
respect, except that if the stack size is n, when the n + 1 element is pushed, the
first element is lost. Implement a dropout stack using an array.
Hint: A circular array implementation would make sense.

Explanation / Answer

Hi, Please find my implementation for Q1.

Please repost other in separate post

Please let me know in case of any issue in Q1.

The idea here is to initialize top with -1 .

//stack.h file
#ifndef _STACK_H
#define _STACK_H
#define MAX 100
class Stack {
public:
Stack();
int size() const;
bool isEmpty() const;
void push(int value);
int pop();
private:
   int arr[MAX];
   int top;
};

#endif

//stack.cpp file
#include "stack.h"

Stack::Stack(){
    top = -1;
}
// `int size()` - returns the number of elements in the stack (0 if empty)
int Stack::size() const {
return top;
}

// `bool isEmpty()` - returns if the list has no elements, else false
bool Stack::isEmpty() const {
return top == -1;;
}

// `void push(int val)` - pushes an item to the stack in O(1) time
void Stack::push(int value) {
    if(top < MAX-1)
        arr[++top] = value;
}

// `int pop()` - removes an item off the stack and returns the value in O(1) time
int Stack::pop() {
   if(count > -1){
       int t = arr[top];
       top = top - 1;
       return t;
   }
  
return -1;
}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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