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.
#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
#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;
}
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
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 is an abstract data type that allows you to input and output data in a way that the first data which was placed in the stack will be the last one to get out. We use physical examples of stack in our daily lives such as the stack of dishes or stack of coins where you only add or remove objects from the top of the stack. You can see the implementation in c++ in related links, below.
No. You can declare a dynamic array without specifying a length, but in order to physically instantiate (either by using malloc or by using object-oriented construction) you must provide a length.
You can write a C++ fib pro using arrays but the problem is the prog becomes very complicated since u need to pass the next adding value in an array.....
An ordered list of data in any programming language is simply a sorted array or list. In C++ this can either mean a sorted array, vector, list or forward list.
The lowest subscript of an array in C, or C++ is 0.
The easiest way to implement a calculator is an RPN calculator (enter the numbers first, perform the operation last). You need a last-in-first-out stack (there's a "stack" class in C++, but you can also implement your own using an array or a linked list), and a set of functions that pop the last elements from the stack and push the result (e.g. Add() pops the last 2 values and pushes their addition).You'll need the math.h library for scientific operations.
Stack is an abstract data type that allows you to input and output data in a way that the first data which was placed in the stack will be the last one to get out. We use physical examples of stack in our daily lives such as the stack of dishes or stack of coins where you only add or remove objects from the top of the stack. You can see the implementation in c++ in related links, below.
No.
truzi i Ghal
No. You can declare a dynamic array without specifying a length, but in order to physically instantiate (either by using malloc or by using object-oriented construction) you must provide a length.
You can write a C++ fib pro using arrays but the problem is the prog becomes very complicated since u need to pass the next adding value in an array.....
Yes, it is possible to purchase, or 'stack', additional time to your Plus membership
An ordered list of data in any programming language is simply a sorted array or list. In C++ this can either mean a sorted array, vector, list or forward list.
The lowest subscript of an array in C, or C++ is 0.
It depends how the array is declared (fixed size or variable size) and where it is declared (global scope or local scope). If the array is declared in global scope (outside a function) and is fixed size, it will be allocated in static memory. If it is variable size, the pointer is stored in static memory while the array itself is allocated on the heap. The pointer in static memory points to the start address of the array in heap memory. If the array is declared in local scope (inside a function) and is fixed size, it will be allocated on the stack in whichever thread the function was called. If it is variable size, the local pointer is stored on the stack while the array is allocated on the heap. The pointer will fall from scope when the function returns so the array must not be allowed to outlive the function in which the pointer is declared. If the array must outlive the function that allocates the array, the pointer must be declared at a higher scope in the call stack and must be passed by reference to or returned by value from the function that allocates the array. If you provide your own memory manager, however, an array may be allocated wherever the memory manager's memory pool is allocated, be it in static memory, the stack or the heap. A memory manager essentially allocates an array of bytes which you can then utilise as you see fit (the array of bytes will be allocated as per the previous description for arrays in general).
You cannot add elements to a fixed array in C or C++. If, however, the array is declared as a pointer to an array, you can add elements by allocating a new array, copying/adding elements as needed, reassigning the new array to the pointer, and deallocating the original array.
int array[10] = {...}; for (int i = 0; i < 10; ++i) { if (i % 2 == 0) array[i] += 5; else array[i] -= 10; }