C++ Stack

This post was written and published to describe the stack implementation in the C++ programming language. However, I already created a separate post that defines everything about the "stack" data structure. Therefore, in this post, I'll only cover the implementation of the stack in C++ programming, but before we begin, let's first briefly introduce it.

A stack is a LIFO (Last In First Out) structure that can be implemented physically as an array or as a linked list. A stack implemented as an array inherits all of the properties of an array, and if implemented as a linked list, it inherits all of the properties of a linked list. However, no matter how a stack is implemented, insertions and deletions occur only at the top. A stack insertion is known as pushing, and a stack deletion is known as popping.

C++: Array Stack

As arrays are static data structures, the space required for them must be predetermined; i.e., how many total elements will be existing together at any given point in time must be known beforehand. Therefore, the creation of a stack as an array involves determining the number of elements beforehand.

C++: Insertion in a Stack as an Array

If you push an element in the stack, the new element will only be inserted at the top of the stack. This may cause other elements in the stack to shift, depending on how you implemented the stack. For example, at any given instant, we have a stack (in the form of an array), as shown in Fig. (a).

When you push an item, say "P," the stack will change into Fig. (b). The stack transformed into Fig. (c) after another element, "L," was pushed into it.

The "stack-full" condition refers to the scenario in which the array has reached its capacity and there is no room for any additional elements to be added. An overflow is another name for this particular condition.

Consider the following program as an example of stack array pushing:

#include <iostream>
using namespace std;

int push(int[], int &, int);
void display(int[], int);
const int SIZE = 50;

int main()
{
   int stack[SIZE], item, top = -1, res;
   char ch = 'y';
   while (ch == 'y' || ch == 'Y')
   {
      cout << "Enter item for insertion: ";
      cin >> item;
      res = push(stack, top, item);
      if (res == -1)
      {
         cout << "Aborting due to overflow.\n";
         return 0;
      }
      cout << "\nThe element was successfully inserted!\n";
      cout << "\nThe stack is now\n";
      display(stack, top);
      cout << "\nWant to enter more? (y/n): ";
      cin >> ch;
   }
   return 0;
}

int push(int stack[], int &top, int elem)
{
   if (top == SIZE - 1)
   {
      return -1;
   }
   else
   {
      top++;
      stack[top] = elem;
   }
   return 0;
}
void display(int stack[], int top)
{
   cout << stack[top] << " <-- " << "\n";
   for (int i = top - 1; i >= 0; i--)
   {
      cout << stack[i] << "\n";
   }
}

The following snapshot shows the initial output produced by the above program:

Now type a number, say 1, and hit the ENTER key to insert, and then type "y" and hit the ENTER key to again insert an item at program runtime. The following snapshot shows the sample run with some user inputs:

C++: Deletion in a Stack as an Array

When an element is "popped," which means it is removed from a stack, the element is moved to the top of the stack. As you observed in the earlier illustration of pushing, the figure for popping is the same, but it is in the opposite manner, that is, after popping an element, it will be removed. Consider the following program as an example:

#include <iostream>
using namespace std;

int pop(int[], int &);
int push(int[], int &, int);
void display(int[], int);
const int SIZE = 50;

int main()
{
   int stack[SIZE], item, top = -1, res;
   char ch = 'y';
   while (ch == 'y' || ch == 'Y')
   {
      cout << "Enter item for insertion: ";
      cin >> item;
      res = push(stack, top, item);
      if (res == -1)
      {
         cout << "Aborting due to overflow.\n";
         return 0;
      }
      cout << "\nThe stack  is now\n";
      display(stack, top);
      cout << "\nWant to enter more? (y/n): ";
      cin >> ch;
   }
   cout << "Now the deletion of elements starts.\n";
   ch = 'y';
   while (ch == 'y' || ch == 'Y')
   {
      res = pop(stack, top);
      if (res == -1)
      {
         cout << "\nAborting due to underflow.\n";
         return 0;
      }
      else
      {
         cout << "\nElement deleted is: " << res << endl;
         cout << "\nThe Stack now is:\n";
         display(stack, top);
      }
      cout << "Want to delete more? (y/n): ";
      cin >> ch;
   }
   return 0;
}

int push(int stack[], int &top, int elem)
{
   if (top == SIZE - 1)
      return -1;
   else
   {
      top++;
      stack[top] = elem;
   }
   return 0;
}

int pop(int stack[], int &top)
{
   int ret;
   if (top == -1)
      return -1;
   else
   {
      ret = stack[top];
      top--;
   }
   return ret;
}

void display(int stack[], int top)
{
   if (top == -1)
      return;
   cout << stack[top] << " <-- " << "\n";
   for (int i = top - 1; i >= 0; i--)
      cout << stack[i] << "\n";
}

The sample run with some user inputs is shown in the following box:

Enter item for insertion: 1

The stack  is now
1 <--

Want to enter more? (y/n): y
Enter item for insertion: 2

The stack  is now
2 <--
1

Want to enter more? (y/n): y
Enter item for insertion: 3

The stack  is now
3 <--
2
1

Want to enter more? (y/n): n
Now the deletion of elements starts.

Element deleted is: 3

The Stack now is:
2 <--
1
Want to delete more? (y/n): y

Element deleted is: 2

The Stack now is:
1 <--
Want to delete more? (y/n): y

Element deleted is: 1

The Stack now is:
Want to delete more? (y/n): y

Aborting due to underflow.

Process returned 0 (0x0)   execution time : 18.986 s

C++: Linked Stack

A linked stack is a type of dynamic data structure that does not require the space requirements to be determined in advance. All of these properties are also passed down to a stack that is implemented as a linked list. The process of creating a stack (as a linked list) is identical to the process of creating a linked list; specifically, after obtaining a node for the item that is to be inserted, the TOP (pointer pointing to the top) points to the newly inserted node. This is the same process that is used to create a linked list.

C++: Insertion in a linked stack

Because a push can only happen at the top, TOP is changed every time. The following program demonstrates how to insert an item into a linked stack.

#include <iostream>
using namespace std;

struct node
{
   int info;
   node *next;
} *top, *newptr, *save, *ptr;

node *create_new_node(int);
void push(node *);
void display(node *);

int main()
{
   int inf;
   char ch = 'y';
   top = NULL;
   while (ch == 'y' || ch == 'Y')
   {
      cout << "Enter information for the new node: ";
      cin >> inf;
      newptr = create_new_node(inf);
      if (newptr == NULL)
      {
         cout << "\nSorry..!!.. Can't create a new node...!!..Aborting...!!\n";
         return 0;
      }
      push(newptr);
      cout << "\nThe stack is now\n";
      display(top);
      cout << "\nWant to enter more? (y/n): ";
      cin >> ch;
   }
   return 0;
}

node *create_new_node(int x)
{
   ptr = new node;
   ptr->info = x;
   ptr->next = NULL;
   return ptr;
}
void push(node *n)
{
   if (top == NULL)
      top = n;
   else
   {
      save = top;
      top = n;
      n->next = save;
   }
}
void display(node *n)
{
   while (n != NULL)
   {
      cout << n->info << " -> ";
      n = n->next;
   }
   cout << "!!\n";
}

Following is a sample run of the above program:

Enter information for the new node: 1

The stack is now
1 -> !!

Want to enter more? (y/n): y
Enter information for the new node: 2

The stack is now
2 -> 1 -> !!

Want to enter more? (y/n): y
Enter information for the new node: 3

The stack is now
3 -> 2 -> 1 -> !!

Want to enter more? (y/n): n

Process returned 0 (0x0)   execution time : 6.621 s

C++: Deletion from a Linked Stack

Deletion, also known as popping, necessitates the modification of TOP, which entails making TOP point to the next node in the sequence. Consider the following program as an example of deletion from a linked stack.

#include <iostream>
using namespace std;

struct node
{
   int info;
   node *next;
} *top, *newptr, *save, *ptr;

node *create_new_node(int);
void push(node *);
void pop();
void display(node *);

int main()
{
   int inf;
   char ch = 'y';
   top = NULL;
   while (ch == 'y' || ch == 'Y')
   {
      cout << "Enter information for the new node: ";
      cin >> inf;
      newptr = create_new_node(inf);
      if (newptr == NULL)
      {
         cout << "\nSorry..!!.. Can't create a new node...!!..Aborting...!!\n";
         return 0;
      }
      push(newptr);
      cout << "\nWant to enter more? (y/n): ";
      cin >> ch;
   }
   do
   {
      cout << "\nThe stack is now\n";
      display(top);
      cout << "\nWant to pop an element? (y/n): ";
      cin >> ch;
      if (ch == 'y' || ch == 'Y')
         pop();
      cout << "\n";
   } while (ch == 'y' || ch == 'Y');
   return 0;
}

node *create_new_node(int x)
{
   ptr = new node;
   ptr->info = x;
   ptr->next = NULL;
   return ptr;
}
void push(node *n)
{
   if (top == NULL)
      top = n;
   else
   {
      save = top;
      top = n;
      n->next = save;
   }
}
void pop()
{
   if (top == NULL)
   {
      cout << "\nAborting due to underflow.\n";
      exit(0);
   }
   else
   {
      ptr = top;
      top = top->next;
      delete ptr;
   }
}
void display(node *n)
{
   while (n != NULL)
   {
      cout << n->info << " -> ";
      n = n->next;
   }
   cout << "!!\n";
}

For your convenience, a sample run with some user inputs is shown in the box below.

Enter information for the new node: 10

Want to enter more? (y/n): y
Enter information for the new node: 12

Want to enter more? (y/n): y
Enter information for the new node: 43

Want to enter more? (y/n): y
Enter information for the new node: 45

Want to enter more? (y/n): n

The stack is now
45 -> 43 -> 12 -> 10 -> !!

Want to pop an element? (y/n): y


The stack is now
43 -> 12 -> 10 -> !!

Want to pop an element? (y/n): y


The stack is now
12 -> 10 -> !!

Want to pop an element? (y/n): y


The stack is now
10 -> !!

Want to pop an element? (y/n): y


The stack is now
!!

Want to pop an element? (y/n): y

Aborting due to underflow.

Process returned 0 (0x0)   execution time : 17.319 s

C++ Quiz

« Previous Tutorial Next Tutorial »