Stack

A stack is an Adaptor that provides a restricted subset of Container functionality: it provides insertion, removal, and inspection of the element at the top of the stack.

View version details

Contents

Definition
Description
Performance
Stack Operations
Page Comments

Definition

The stack template is defined in the standard header <stack>, and in the nonstandard backward-compatibility header <stack.h>.

#include<stack>
namespace std {
   template <class T, class Container = deque<T>> 
   class stack;
}

Description

A stack is a Container Adaptor which provides a restricted subset of container functionality like insertion, removal, and inspection of the element at the top of the stack. The deque interface is restricted (i.e., much of it is hidden) so that the required LIFO (Last In, First Out) stack-like behavior is provided. Stack does not allow iteration through its elements.

A simple example of creating a stack is:

stack<int> IntStack; // creates a stack of integer type

Another short example illustrates the methods size() and empty():

#include <iostream>
#include <stack>
#include <conio.h>
 
using namespace std;
 
int main()
{
  stack<char> codes;
  codes.push('a');
  codes.push('b');
  cout<<"The size of the stack is:"<<codes.size<<endl; 
  // checking if the stack is empty
  if(codes.empty()==true)
  cout<<"The Stack is Empty"; // prints the size of the stack 
  _getch();
  return 0;
}

The output of this program will be 2 since there are 2 elements in the stack.

Performance

Stack is a Container Adaptor, meaning that it is implemented on top of some underlying container type. By default that underlying type is deque, but a different type may be selected explicitly. (see Example 2)

Stacks are used frequently in parsers. Very common examples includes "Infix to Postfix conversion", "Parenthesis Matching", "Back Tracking" (mostly in games programming).

Stack Operations

Create and Copy Operations

Operation	Effect
stack< El > c	Creates an empty stack c which can hold values of type El
stack< El > c1(c2)	Creates c1 as a copy of c2, whose component type must be El
stack< El > c1=c2	Copy constructor (alternate usage syntax)

Note: Any stack will have a container data member (by default, a deque) which will hold its elements. That data member will have its own destructor which will automatically be involved when the stack goes out of scope.

Nonmodifying Operations of Stacks

Operation	Effect
c1==c2	Returns if c1 is equal to c2
c1!=c2	Returns if c1 is not equal to c2 (equivalent to !(c1==c2))
c1<c2	Returns if c1 is less than c2
c1<=c2	Returns if c1 is less than or equal to c2 (equivalent to !(c2<c1))
c1>c2	Returns if c1 is greater than c2 (equivalent to c2<c1)
c1>=c2	Returns if c1 is greater than or equal to c2 (equivalent to !(c1<c2))
c.top()	Returns a reference (or `const_reference`) to the top component of c
c.size()	Returns a value of type `size_type` giving the number of values currently in c
c.empty()	Returns true if c is empty (contains zero values); otherwise returns false

Modifying Operations of Stacks

Operation	Effect
c1=c2	Assigns c2 to c1, and return the common value. The stack on the left of an assignment receives the values and size of the one on the right
c.push(val)	Adds val to the top of c, increasing the size of c by one
c.pop()	Removes the top value of c, decreasing the size of c by one

References:

http://www.codersource.net
http://www.sgi.com
Nicolai M. Josuttis: "The C++ Standard Library"

Example:

Example - stack methods

Problem

This program illustrates stack methods like size(), pop() and push().

Workings

#include <iostream>
#include <stack>
using namespace std;
 
int main()
{
  int data[] = {41, 38, 53, 20, 78, 52, 69};
  stack<int> s;
  cout << "The stack size is now " << s.size() << endl;
 
  cout << "Pushing 4 elements " << endl;
  for (int i = 0; i < 4; ++i)
    s.push(thedata[i]);

  cout << "The stack size is now " << s.size() << endl;
 
  cout << "Popping 3 elements " << endl;
  for (int i = 0; i < 3; ++i) {
    cout << s.top() << endl;
    s.pop();
  }
  cout << "The stack size is now " << s.size() << endl;

  return 0;
}

Solution

Output:

The stack size is now 0
Pushing 4 elements
The stack size is now 4
Popping 3 elements
20
53
38
The stack size is now 1

References:

Page Comments

You must login to leave a messge