Question

C++ Please

Fill in for the functions for the code below. The functions will implement an integer stack using deques ONLY. It is possible to use only one deque but using two deques also works. Additional public helper functions or private members/functions can be used. The Stack class will be instantiated via a pointer and called as shown below:

Stack *ptr = new Stack();

ptr->push(value);

int pop1 = ptr->pop();

int pop2 = ptr->pop();

bool isEmpty = ptr->empty();

class Stack{

    public:

// Default Constructor

Stack() {// ... }

// Push integer n onto top of stack

void push(int n) {// ... }

// Pop element on top of stack

int pop() {// ... }

// Get the top element but do not pop it (peek at top of stack)

int top() {// ... }

// Return whether the stack is empty or not

bool empty() {// ... }

};

Answer 1

A stack is a linear structure implemented in LIFO(last in first out) manner where insertions and deletions are restricted to occure only at one end ie, stack's top.The stack is also a dynamic data structure as it can grow(with increas in number of elements or shrink(with decrease in number of elements).

A Queue is also a linear dynamic structure implemented in FIFO (first in first out) manner where insertions can occure at the"rear" end ,and deletions occur only from "front" end.

Stack:

Logically ,a stack is a LIFO structure and physically it can be implemented as an array or as a linked list.A stack implemented as an array inherits all the properties of an array and if implemented as a linked list ,all characteristics of a linked list are possessed by it.But whatever way a stack may be implemented ,insertions and deletions occure at the top only.An insertion in a stack is called pushing and a deletion from a stack is called popping.

Insertion in a stack as an array(PUSHING):

Pushing an element in the stack involves shifting of elements as the new elements will be inserted at the top only.

  

      

a

s

d

g

fig(.a)

w

a

s

d

g

fig(b)

e

w

a

s

d

g

fig(c)

for instance ,at any point of time we have stack(as an array) like fig(a).

After pushing W,stack becomes as fig(b).After pushing another element E,the stack becomes fig(c).Every time a push occures,elements are shifted down wards to accommodate the new entrant.

In case the array is full and no new element can be accommodated ,it is called STACK-FULL condition.This condition is also called an overflow.

Algorithm for a push in a stack:

1.ctr=N,top=0

2.repeat steps 3 and 4 until ctr=top

3.stack[ctr]=stack[ctr-1]

4.ctr=ctr-1

5.stack[top]=ITEM.

Deletion in a stack (as an array) POPPING:

Popping ie,deletion of an element from a stack also involves re shifting of elements .For instance ,from the stack shown in fig(a),the top most element which is E,can be popped and after popping E,the stack looks as shown in fig(d),after popping another element W,the stack looks as fig(e).In case ` the last element is popped ,the stack becomes empty.

w

a

s

d

g

fig(d)

a

s

d

g

fig(e)

Algorithm for a pop in a stack:

1.ctr=top.

/*print top most element*/

2.print stack[top].

/*move the elements upward to fill the top */

3.repeat steps 4 and 5 until ctr=N.

4.stack[ctr]=stack[ctr+1].

5.ctr==ctr+1.1``

template <class T>

class stack

{

private:

int top;

T*nodes;

public:

stack();

int empty(void);

void push(T&);

T pop (void);

T pop(int &);

~stack ();

};

program:

template <class T> int stack<T>:: empty(void)

{

return top>=0;

};

template<class T> void stack<T>::push(T &j)

{

if(top==STACKSIZE)

{

count<<"stack overflow"<< end1;

return;

}

nodes[++top]=j;

}

template<class T> T stack <T>::pop(void)

{

T p;

if(empty())

{

count<<"stack underflow"<< end1;

return p;

}

p=nodes[top--];

return p;

};

template <class T>T stack<T>::pop(int & und)

{

Tp;

if (empty())

{

und=1;

return p;

}

und=0;

p=nodes[top--];

return p;

};