How do you implement a stack using an array in c plus plus?

Answer 1

An array in C++ is fixed-size and is unsuitable for implementing stacks. You can use a C-style dynamic array, of course, but the C++ method is to use a vector. A vector encapsulates a C-style dynamic array along with its size and greatly simplifies the way you work with arrays.

Dynamic arrays are generally the best way to implement a stack, however be aware that when the array is full and you want to add a new element, you must reallocate the array which can occasionally cause the entire array to be moved to new memory. A vector, on the other hand, automatically reserves 1.6 times the consumed memory on each reallocation and thus minimises the need to reallocate.

Vectors provide a push_back() and pop_back() method, since these are the fastest methods of inserting and extracting elements from an array (inserting or extracting anywhere else would result in elements being shunted up and down the array, which is inefficient). These two methods alone are all you need to implement a stack. However, vectors also permit random access to any element within the array. To eliminate all unnecessary features, you must encapsulate the vector within an adaptor class (a thin-wrapper) that only exposes the functionality you actually need. A minimal implementation is presented here:

#include<vector>

template<typename T>

class stack

{

std::vector<T> m_data;

public:

stack() =default;

~stack() =default;

stack(const stack&) =default;

stack(stack&&) =default;

stack& operator= (const stack&) =default;

stack& operator= (stack&&) =default;

void push (const T& data) {m_data.push_back (data);}

void pop () {m_data.pop_back ();}

T& top () {return m_data.back();}

const T& top () const {return m_data.back();}

};

This is fairly similar to the way a std::stack is implemented in the STL, although it also provides specialisations for pointer types. For more information on the implementation, consult the <stack> header in the standard library.

Answer 2

#include<stdio.h>

#include<conio.h>

int st_arr[20];

int t=-1;

void push_ele(int ele);

int pop_ele();

void display_ele();

void main()

{

char choice,num1=0,num2=0;

while(1)

{

clrscr();

printf("======================================");

printf("\n\t\t MENU ");

printf("\n======================================");

printf("\n[1] Using Push Function");

printf("\n[2] Using Pop Function");

printf("\n[3] Elements present in Stack");

printf("\n[4] Exit\n");

printf("\n\tEnter your choice: ");

fflush(stdin);

scanf("%c",&choice);

switch(choice-'0′)

{

case 1:

{

printf("\n\tElement to be pushed: ");

scanf("%d",&num1);

push_ele(num1);

break;

}

case 2:

{

num2=pop_ele(1);

printf("\n\tElement to be popped: %d\n\t",num2);

getch();

break;

}

case 3:

{

display_ele();

getch();

break;

}

case 4:

exit(1);

break;

default:

printf("\nYour choice is invalid.\n");

break;

}

}

}

/*Implementing the push() function. */

void push_ele(int ele)

{

if(t==99)

{

printf("STACK is Full.\n");

getch();

exit(1);

}

st_arr[++t]=ele;

}

/*Implementing the pop() function. */

int pop_ele()

{

int ele1;

if(t==-1)

{

printf("\n\tSTACK is Empty.\n");

getch();

exit(1);

}

return(st_arr[t--]);

}

/*Implementing display() function. */

void display_ele()

{

int k;

printf("\n\tElements present in the stack are:\n\t");

for(k=0;k<=t;k++)

printf("%d\t",st_arr[k]);

}

by Bipin

Answer 3

#include<stdio.h>

#include<stdlib.h>

#include<memory.h>

#include<time.h>

// an array of unsigned integers

typedef struct arraystack_t {

unsigned* arr; // pointer to a variable length array of type unsigned

unsigned sz; // overall length of array (in elements)

unsigned space; // unused elements

} arraystack;

bool is_empty (arraystack*);

unsigned size (arraystack*);

unsigned top (arraystack*);

int initialise (arraystack*);

int push (arraystack*, unsigned);

int expand (arraystack*);

void pop (arraystack*);

void clear (arraystack*);

// calculates and returns the length of the stack

unsigned size (arraystack* stk) {

return stk->sz-stk->space;

}

// returns true if the stack is empty

bool is_empty (arraystack* stk) {

return stk->space==stk->sz;

}

// clear the stack

void clear (arraystack* stk) {

if (stk->arr) free (stk->arr);

memset (stk, 0, sizeof (arraystack));

}

// initialise the stack

int initialise (arraystack* stk) {

const unsigned sz = 1; // start with 1 unused element

memset (stk, 0, sizeof (arraystack));

stk->arr = (unsigned*) malloc (sz * sizeof (unsigned));

if (!stk->arr) return -1; // out of memory

stk->sz = sz;

stk->space = sz;

return 0;

}

// increase the size of the stack (create space)

int expand (arraystack* stk) {

unsigned space, t, i, *p;

if (stk->space) return 0; // no need to expand when we have space

// reallocate the array to create space

space = (unsigned) (0.6 * stk->sz + 1); // optimum growth: 160%

p = (unsigned*) realloc (stk->arr, (stk->sz + space) * sizeof(unsigned));

if (!p) return -1; // out of memory

stk->arr = p;

stk->sz += space;

stk->space = space;

return 0;

}

// insert value on top of stack

int push (arraystack* stk, unsigned val) {

if (expand (stk))

return -1; // out of memory

stk->arr[size(stk)] = val;

--stk->space;

return 0;

}

// extract value from top of stack

void pop (arraystack* stk) {

++stk->space;

}

// return the top value from the stack

unsigned top (arraystack* stk) {

return stk->arr[size(stk)-1];

}

// returns true or false at random (used by test program)

bool is_true (void) {

return rand() & 0x1;

}

// prints the content of the stack (used by test program)

void print_stack (arraystack* stk) {

unsigned i, sz;

sz = size (stk);

printf ("{");

for (i=0; i<sz; ++i) printf ("%u%s", stk->arr[i], i!=sz-1?", ":"");

printf ("}\n");

}

// test program

int main (void) {

unsigned i, loop;

srand((unsigned) time(0)); // seed random generator

arraystack stk;

initialise (&stk); // initialise the stack

for (loop=0; loop<100; ++loop) {

if (is_true ()) {

i = rand() % 10;

printf ("Pushing %u:\t", i);

if (push (&stk, i))

break; // out of memory

print_stack (&stk);

}

if (!is_empty (&stk) && is_true ()) {

printf ("Popping %u:\t", top (&stk));

pop (&stk);

print_stack (&stk);

}

}

while (!is_empty (&stk)) {

printf ("Popping %u:\t", top (&stk));

pop (&stk);

print_stack (&stk);

}

clear (&stk);

return 0;

}

Answer 4

An array in C++ is fixed-size and is unsuitable for implementing stacks. You can use a C-style dynamic array, of course, but the C++ method is to use a vector. A vector encapsulates a C-style dynamic array along with its size and greatly simplifies the way you work with arrays.

Dynamic arrays are generally the best way to implement a stack, however be aware that when the array is full and you want to add a new element, you must reallocate the array which can occasionally cause the entire array to be moved to new memory. A vector, on the other hand, automatically reserves 1.6 times the consumed memory on each reallocation and thus minimises the need to reallocate.

Vectors provide a push_back() and pop_back() method, since these are the fastest methods of inserting and extracting elements from an array (inserting or extracting anywhere else would result in elements being shunted up and down the array, which is inefficient). These two methods alone are all you need to implement a stack. However, vectors also permit random access to any element within the array. To eliminate all unnecessary features, you must encapsulate the vector within an adaptor class (a thin-wrapper) that only exposes the functionality you actually need. A minimal implementation is presented here:

#include

template

class stack

{

std::vector m_data;

public:

stack() =default;

~stack() =default;

stack(const stack&) =default;

stack(stack&&) =default;

stack& operator= (const stack&) =default;

stack& operator= (stack&&) =default;

void push (const T& data) {m_data.push_back (data);}

void pop () {m_data.pop_back ();}

T& top () {return m_data.back();}

const T& top () const {return m_data.back();}

};

This is fairly similar to the way a std::stack is implemented in the STL, although it also provides specialisations for pointer types. For more information on the implementation, consult the header in the standard library.