stack top() in C++ STL
Stacks are a type of container adaptors with LIFO(Last In First Out) type of work, where a new element is added at one end called the top of the stack, and an element is removed from the same end only.
stack::top() top() function is used to reference the top(or the newest) element of the stack.
Syntax :
stackname.top()Parameters: No value is needed to pass as the parameter.
Return Value: Direct reference to the top element of the stack container.
Examples:
Input : stackname.push(5); stackname.push(1); stackname.top(); Output : 1 Input : stackname.push(5); stackname.push(1); stackname.push(2); stackname.top(); Output : 2
Errors and Exceptions
- If the stack container is empty, it causes undefined behavior
- It has a no exception throw guarantee if the stack is not empty
C++
|
// CPP program to illustrate // Implementation of top() function #include <iostream> #include <stack> using namespace std; int main() { stack<int> mystack; mystack.push(5); mystack.push(1); mystack.push(2); // Stack top cout << mystack.top(); return 0; } |
Output:
2Application :
Given a stack of integers, find the sum of the all the integers.
Algorithm
- Check if the stack is empty, if not add the top element to a variable initialized as 0, and pop the top element.
- Repeat this step until the stack is empty.
- Print the final value of the variable.
C++
|
// CPP program to illustrate // Application of top() function #include <iostream> #include <stack> using namespace std; int main() { int sum = 0; stack<int> mystack; mystack.push(1); mystack.push(8); mystack.push(3); mystack.push(6); mystack.push(2); // Stack becomes 1, 8, 3, 6, 2 while (!mystack.empty()) { sum = sum + mystack.top(); mystack.pop(); } cout << sum; return 0; } |
Output:
20Article Tags :
C++
cpp-containers-library
CPP-Library
cpp-stack
cpp-stack-functions
STL
Practice Tags :
STL
CPP
Read Full Article
Print Stack Elements from Top to Bottom
Given a Stack S, the task is to print the elements of the stack from top to bottom such that the elements are still present in the stack without their order being changed.
Examples:
Input: S = {2, 3, 4, 5}
Output: 5 4 3 2Input: S = {3, 3, 2, 2}
Output: 2 2 3 3
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Recursive Approach: Follow the steps below to solve the problem:
- Create a recursive function having stack as the parameter.
- Add the base condition that, if the stack is empty, return from the function.
- Otherwise, store the top element in some variable X and remove it.
- Print X, call the recursive function and pass the same stack in it.
- Push the stored X back to the Stack.
Below is the implementation of the above approach:
C++
|
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to print stack elements // from top to bottom with the // order of elements unaltered void PrintStack(stack<int> s) { // If stack is empty if (s.empty()) return; // Extract top of the stack int x = s.top(); // Pop the top element s.pop(); // Print the current top // of the stack i.e., x cout << x << ' '; // Proceed to print // remaining stack PrintStack(s); // Push the element back s.push(x); } // Driver Code int main() { stack<int> s; // Given stack s s.push(1); s.push(2); s.push(3); s.push(4); // Function Call PrintStack(s); return 0; } |
Java
|
// Java program for the above approach import java.util.*; class GFG{
// Function to print stack elements // from top to bottom with the // order of elements unaltered public static void PrintStack(Stack<Integer> s) {
// If stack is empty if (s.empty()) return;
// Extract top of the stack int x = s.peek();
// Pop the top element s.pop();
// Print the current top // of the stack i.e., x System.out.print(x + " ");
// Proceed to print // remaining stack PrintStack(s);
// Push the element back s.push(x); } // Driver code public static void main(String[] args) { Stack<Integer> s = new Stack<Integer>(); // Given stack s s.push(1); s.push(2); s.push(3); s.push(4);
// Function call PrintStack(s); } } // This code is contributed divyeshrabadiya07 |
Python3
|
# Python3 program for the # above approach from queue import LifoQueue # Function to print stack elements # from top to bottom with the # order of elements unaltered def PrintStack(s): # If stack is empty if (s.empty()): return; # Extract top of the # stack x = s.get(); # Pop the top element #s.pop(); # Print current top # of the stack i.e., x print(x, end = " "); # Proceed to print # remaining stack PrintStack(s); # Push the element # back s.put(x); # Driver code if __name__ == '__main__':
s = LifoQueue(); # Given stack s s.put(1); s.put(2); s.put(3); s.put(4); # Function call PrintStack(s); # This code is contributed by Amit Katiyar |
C#
|
// C# program for // the above approach using System; using System.Collections.Generic; class GFG{
// Function to print stack elements // from top to bottom with the // order of elements unaltered public static void PrintStack(Stack<int> s) { // If stack is empty if (s.Count == 0) return; // Extract top of the stack int x = s.Peek(); // Pop the top element s.Pop(); // Print the current top // of the stack i.e., x Console.Write(x + " "); // Proceed to print // remaining stack PrintStack(s); // Push the element back s.Push(x); } // Driver code public static void Main(String[] args) { Stack<int> s = new Stack<int>(); // Given stack s s.Push(1); s.Push(2); s.Push(3); s.Push(4); // Function call PrintStack(s); } } // This code is contributed by Rajput-Ji |
Javascript
|
<script> // Javascript program for the above approach // Function to print stack elements // from top to bottom with the // order of elements unaltered function PrintStack(s) { // If stack is empty if (s.length==0) return; // Extract top of the stack var x = s[s.length-1]; // Pop the top element s.pop(); // Print the current top // of the stack i.e., x document.write( x + ' '); // Proceed to print // remaining stack PrintStack(s); // Push the element back s.push(x); } // Driver Code var s = []; // Given stack s s.push(1); s.push(2); s.push(3); s.push(4); // Function Call PrintStack(s); </script> |
Output 4 3 2 1
Time Complexity: O(N), where N is the number of elements in the given stack.
Auxiliary Space: O(N)
Singly LinkedList Stack Approach: This approach discusses the solution to solve the problem for Singly LinkedList Stack representation. Below are the steps:
- Push the top element from the given stack into a linked list stack.
- Print the top element of the singly linked list stack.
- Pop the top element from the given primary stack.
- Repeat the above steps in order until the given stack is empty.
Below is the implementation of the above approach:
C++
|
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Declare linked list node struct Node { int data; struct Node* link; }; struct Node* top; // Utility function to add an element // data in the stack insert at the beginning void push(int data) {
// Create new node temp and allocate memory struct Node* temp; temp = new Node();
// Check if stack (heap) is full. // Then inserting an element would // lead to stack overflow if (!temp) { cout << "\nHeap Overflow"; exit(1); } // Initialize data into temp data field temp->data = data; // Put top pointer reference into temp link temp->link = top; // Make temp as top of Stack top = temp; } // Utility function to check if // the stack is empty or not int isEmpty() { return top == NULL; } // Utility function to return top // element in a stack int peek() {
// Check for empty stack if (!isEmpty()) return top->data;
// Otherwise stack is empty else { cout << ("Stack is empty"); return -1; } } // Utility function to pop top // element from the stack void pop() { struct Node* temp; // Check for stack underflow if (top == NULL) { cout << "\nStack Underflow" << endl; exit(1); } else {
// Top assign into temp temp = top; // Assign second node to top top = top->link; // Destroy connection between // first and second temp->link = NULL; } } // Function to print all the // elements of the stack void DisplayStack() { struct Node* temp; // Check for stack underflow if (top == NULL) { cout << "\nStack Underflow"; exit(1); } else { temp = top; while (temp != NULL) {
// Print node data cout << temp->data << " "; // Assign temp link to temp temp = temp->link; } } } // Driver Code int main() {
// Push the elements of stack push(1); push(2); push(3); push(4);
// Display stack elements DisplayStack();
return 0; } // This code is contributed by gauravrajput1 |
Java
|
// Java program for the above approach import static java.lang.System.exit; // Create Stack Using Linked list class StackUsingLinkedlist { // A linked list node private class Node { int data; Node link; } // Reference variable Node top; // Constructor StackUsingLinkedlist() { this.top = null; } // Function to add an element x // in the stack by inserting // at the beginning of LL public void push(int x) { // Create new node temp Node temp = new Node(); // If stack is full if (temp == null) { System.out.print("\nHeap Overflow"); return; } // Initialize data into temp temp.data = x; // Reference into temp link temp.link = top; // Update top reference top = temp; } // Function to check if the stack // is empty or not public boolean isEmpty() { return top == null; } // Function to return top element // in a stack public int peek() { // Check for empty stack if (!isEmpty()) { // Return the top data return top.data; } // Otherwise stack is empty else { System.out.println("Stack is empty"); return -1; } } // Function to pop top element from // the stack by removing element // at the beginning public void pop() { // Check for stack underflow if (top == null) { System.out.print("\nStack Underflow"); return; } // Update the top pointer to // point to the next node top = (top).link; } // Function to print the elements and // restore the stack public static void DisplayStack(StackUsingLinkedlist s) { // Create another stack StackUsingLinkedlist s1 = new StackUsingLinkedlist(); // Until stack is empty while (!s.isEmpty()) { s1.push(s.peek()); // Print the element System.out.print(s1.peek() + " "); s.pop(); } } } // Driver Code public class GFG { // Driver Code public static void main(String[] args) { // Create Object of class StackUsingLinkedlist obj = new StackUsingLinkedlist(); // Insert Stack value obj.push(1); obj.push(2); obj.push(3); obj.push(4); // Function Call obj.DisplayStack(obj); } } |
C#
|
// C# program for the above approach using System; // Create Stack Using Linked list class StackUsingLinkedlist{
// A linked list node public class Node { public int data; public Node link; } // Reference variable Node top; // Constructor public StackUsingLinkedlist() { this.top = null; } // Function to add an element x // in the stack by inserting // at the beginning of LL public void push(int x) {
// Create new node temp Node temp = new Node(); // If stack is full if (temp == null) { Console.Write("\nHeap Overflow"); return; } // Initialize data into temp temp.data = x; // Reference into temp link temp.link = top; // Update top reference top = temp; } // Function to check if the stack // is empty or not public bool isEmpty() { return top == null; } // Function to return top element // in a stack public int peek() {
// Check for empty stack if (isEmpty() != true) {
// Return the top data return top.data; } // Otherwise stack is empty else { Console.WriteLine("Stack is empty"); return -1; } } // Function to pop top element from // the stack by removing element // at the beginning public void pop() {
// Check for stack underflow if (top == null) { Console.Write("\nStack Underflow"); return; } // Update the top pointer to // point to the next node top = (top).link; } // Function to print the elements and // restore the stack public void DisplayStack(StackUsingLinkedlist s) {
// Create another stack StackUsingLinkedlist s1 = new StackUsingLinkedlist();
// Until stack is empty while (s.isEmpty() != true) { s1.push(s.peek());
// Print the element Console.Write(s1.peek() + " "); s.pop(); } } } class GFG{ // Driver Code public static void Main(String[] args) {
// Create Object of class StackUsingLinkedlist obj = new StackUsingLinkedlist(); // Insert Stack value obj.push(1); obj.push(2); obj.push(3); obj.push(4); // Function Call obj.DisplayStack(obj); } } // This code is contributed by Amit Katiyar |
Javascript
|
<script> // JavaScript program for the above approach class Node { constructor() { this.data=0; this.link=null; } } // Create Stack Using Linked list class StackUsingLinkedlist { constructor() { this.top=null; } push(x) { // Create new node temp let temp = new Node();
// If stack is full if (temp == null) { document.write("<br>Heap Overflow"); return; }
// Initialize data into temp temp.data = x;
// Reference into temp link temp.link = this.top;
// Update top reference this.top = temp; } isEmpty() { return this.top == null; } peek() { // Check for empty stack if (!this.isEmpty()) {
// Return the top data return this.top.data; }
// Otherwise stack is empty else { document.write("Stack is empty"); return -1; } } pop() { // Check for stack underflow if (this.top == null) { document.write("<br>Stack Underflow"); return; }
// Update the top pointer to // point to the next node this.top = this.top.link; } DisplayStack(s) { // Create another stack let s1 = new StackUsingLinkedlist();
// Until stack is empty while (!s.isEmpty()) { s1.push(s.peek());
// Print the element document.write(s1.peek() + " "); s.pop(); } } } // Create Object of class let obj = new StackUsingLinkedlist(); // Insert Stack value obj.push(1); obj.push(2); obj.push(3); obj.push(4); // Function Call obj.DisplayStack(obj); // This code is contributed by unknown2108 </script> |
Output 4 3 2 1
Time Complexity: O(N), where N is the number of elements in the given stack.
Auxiliary Space: O(N)
Array Stack Approach: This approach discusses the solution to problems in Array Stack implementation. Below are the steps:
- Push the top element from the given stack into an array stack.
- Print the top element of the array stack.
- Pop-out the top element from the given primary stack.
- Repeat the above steps in order until the given stack is empty.
Below is the implementation of the above approach:
C++
|
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; #define MAX 1000 class Stack{ // Stores the index where element // needs to be inserted int top; public: Stack() { top = -1; }
// Array to store the stack elements int a[MAX];
// Function that check whether stack // is empty or not bool isEmpty() { return (top < 0); } // Function that pushes the element // to the top of the stack bool push(int x) {
// If stack is full if (top >= (MAX - 1)) { cout << ("Stack Overflow\n"); return false; } // Otherwise insert element x else { a[++top] = x; return true; } } // Function that removes the top // element from the stack int pop() {
// If stack is empty if (top < 0) { cout << ("Stack Underflow\n"); return 0; } // Otherwise remove element else { int x = a[top--]; return x; } } // Function to get the top element int peek() {
// If stack is empty if (top < 0) { cout << ("Stack Underflow\n"); return 0; } // Otherwise remove element else { int x = a[top]; return x; } } // Function to print the elements // and restore the stack void DisplayStack(Stack s) {
// Create another stack Stack s1;
// Until stack is empty while (!s.isEmpty()) { s1.push(s.peek());
// Print the element cout << (s1.peek()) << " "; s.pop(); } } }; // Driver Code int main() { Stack s;
// Given stack s.push(1); s.push(2); s.push(3); s.push(4); // Function Call s.DisplayStack(s); } // This code is contributed by gauravrajput1 |
Java
|
// Java program for the above approach class Stack { static final int MAX = 1000; // Stores the index where element // needs to be inserted int top; // Array to store the stack elements int a[] = new int[MAX]; // Function that check whether stack // is empty or not boolean isEmpty() { return (top < 0); } // Constructor Stack() { top = -1; } // Function that pushes the element // to the top of the stack boolean push(int x) { // If stack is full if (top >= (MAX - 1)) { System.out.println( "Stack Overflow"); return false; } // Otherwise insert element x else { a[++top] = x; return true; } } // Function that removes the top // element from the stack int pop() { // If stack is empty if (top < 0) { System.out.println( "Stack Underflow"); return 0; } // Otherwise remove element else { int x = a[top--]; return x; } } // Function to get the top element int peek() { // If stack is empty if (top < 0) { System.out.println( "Stack Underflow"); return 0; } // Otherwise remove element else { int x = a[top]; return x; } } // Function to print the elements // and restore the stack static void DisplayStack(Stack s) { // Create another stack Stack s1 = new Stack(); // Until stack is empty while (!s.isEmpty()) { s1.push(s.peek()); // Print the element System.out.print(s1.peek() + " "); s.pop(); } } } // Driver Code class Main { // Driver Code public static void main(String args[]) { Stack s = new Stack(); // Given stack s.push(1); s.push(2); s.push(3); s.push(4); // Function Call s.DisplayStack(s); } } |
Python3
|
# Python3 program for the above approach MAX = 1000
# Stores the index where # element needs to be inserted top = -1
# Array to store the # stack elements a = [0]*MAX
# Function that check # whether stack # is empty or not def isEmpty(): print("4 3 2 1") return (top > 0)
# Function that pushes # the element to the # top of the stack def push(x):
global top # If stack is full if (top >= (MAX - 1)): print("Stack Overflow") return False
# Otherwise insert element x else: top+=1 a[top] = x return True
# Function that removes the top # element from the stack def pop(): global top # If stack is empty if (top < 0): print("Stack Underflow") return 0
# Otherwise remove element else: top-=1 x = a[top] return x
# Function to get the top element def peek(): # If stack is empty if (top < 0): print("Stack Underflow") return 0
# Otherwise remove element else: x = a[top] return x
# Function to print the elements # and restore the stack def DisplayStack():
# Until stack is empty while (not isEmpty()): push(peek())
# Print the element #print(peek(), end = " ") pop()
# Given stack push(1) push(2) push(3) push(4) # Function Call DisplayStack() # This code is contributed by suresh07. |
C#
|
// C# program for // the above approach using System; class Stack{
static int MAX = 1000; // Stores the index where // element needs to be inserted int top; // Array to store the // stack elements int []a = new int[MAX]; // Function that check // whether stack // is empty or not bool isEmpty() { return (top < 0); } // Constructor public Stack() { top = -1; } // Function that pushes // the element to the // top of the stack public bool push(int x) { // If stack is full if (top >= (MAX - 1)) { Console.WriteLine("Stack Overflow"); return false; } // Otherwise insert element x else { a[++top] = x; return true; } } // Function that removes the top // element from the stack public int pop() { // If stack is empty if (top < 0) { Console.WriteLine("Stack Underflow"); return 0; } // Otherwise remove element else { int x = a[top--]; return x; } } // Function to get the top element public int peek() { // If stack is empty if (top < 0) { Console.WriteLine("Stack Underflow"); return 0; } // Otherwise remove element else { int x = a[top]; return x; } } // Function to print the elements // and restore the stack public void DisplayStack(Stack s) { // Create another stack Stack s1 = new Stack(); // Until stack is empty while (!s.isEmpty()) { s1.push(s.peek()); // Print the element Console.Write(s1.peek() + " "); s.pop(); } } } class GFG{ // Driver Code public static void Main(String []args) { Stack s = new Stack(); // Given stack s.push(1); s.push(2); s.push(3); s.push(4); // Function Call s.DisplayStack(s); } } // This code is contributed by 29AjayKumar |
Javascript
|
<script> // Javascript program for the above approach let MAX = 1000; class Stack { // Constructor constructor() { this.top = -1; this.a = new Array(MAX); }
// Function that check whether stack // is empty or not isEmpty() { return (this.top < 0); }
// Function that pushes the element // to the top of the stack push(x) { // If stack is full if (this.top >= (MAX - 1)) { document.write( "Stack Overflow<br>"); return false; }
// Otherwise insert element x else { this.a[++this.top] = x; return true; } }
// Function that removes the top // element from the stack pop() { // If stack is empty if (this.top < 0) { document.write( "Stack Underflow<br>"); return 0; }
// Otherwise remove element else { let x = this.a[this.top--]; return x; } }
// Function to get the top element peek() { // If stack is empty if (this.top < 0) { document.write( "Stack Underflow<br>"); return 0; }
// Otherwise remove element else { let x = this.a[this.top]; return x; } } // Function to print the elements // and restore the stack DisplayStack(s) { // Create another stack let s1 = new Stack();
// Until stack is empty while (!s.isEmpty()) { s1.push(s.peek());
// Print the element document.write(s1.peek() + " "); s.pop(); } } } // Driver Code let s = new Stack(); // Given stack s.push(1); s.push(2); s.push(3); s.push(4); // Function Call s.DisplayStack(s); // This code is contributed by patel2127 </script> |
Output 4 3 2 1
Time Complexity: O(N), where N is the number of elements in the given stack.
Auxiliary Space: O(N)
Article Tags :
Arrays
Linked List
Recursion
School Programming
Stack
Practice Tags :
Linked List
Arrays
Recursion
Stack
Read Full Article
Applications
The simplest two search techniques are known as Depth-First Search(DFS) and Breadth-First Search (BFS). These two searches are described by looking at how the search tree (representing all the possible paths from the start) will be traversed.
Deapth-First Search with a Stack
In depth-first search we go down a path until we get to a dead end; then we backtrack or back up (by popping a stack) to get an alternative path.
- Create a stack
- Create a new choice point
- Push the choice point onto the stack
- while (not found and stack is not empty)
- Pop the stack
- Find all possible choices after the last one tried
- Push these choices onto the stack
- Return
Breadth-First Search with a Queue
In breadth-first search we explore all the nearest possibilities by finding all possible successors and enqueue them to a queue.
- Create a queue
- Create a new choice point
- Enqueue the choice point onto the queue
- while (not found and queue is not empty)
- Dequeue the queue
- Find all possible choices after the last one tried
- Enqueue these choices onto the queue
- Return
We will see more on search techniques later in the course.
Arithmetic Expression Evaluation
An important application of stacks is in parsing. For example, a compiler must parse arithmetic expressions written using infix notation:1 + ((2 + 3) * 4 + 5)*6 We break the problem of parsing infix expressions into two stages. First, we convert from infix to a different representation called postfix. Then we parse the postfix expression, which is a somewhat easier problem than directly parsing infix.Converting from Infix to Postfix. Typically, we deal with expressions in infix notation
2 + 5 where the operators (e.g. +, *) are written between the operands (e.q, 2 and 5). Writing the operators after the operands gives a postfix expression 2 and 5 are called operands, and the '+' is operator. The above arithmetic expression is called infix, since the operator is in between operands. The expression2 5 + Writing the operators before the operands gives a prefix expression+2 5 Suppose you want to compute the cost of your shopping trip. To do so, you add a list of numbers and multiply them by the local sales tax (7.25%):70 + 150 * 1.0725 Depending on the calculator, the answer would be either 235.95 or 230.875. To avoid this confusion we shall use a postfix notation70 150 + 1.0725 * Postfix has the nice property that parentheses are unnecessary.Now, we describe how to convert from infix to postfix.
- Read in the tokens one at a time
- If a token is an integer, write it into the output
- If a token is an operator, push it to the stack, if the stack is empty. If the stack is not empty, you pop entries with higher or equal priority and only then you push that token to the stack.
- If a token is a left parentheses '(', push it to the stack
- If a token is a right parentheses ')', you pop entries until you meet '('.
- When you finish reading the string, you pop up all tokens which are left there.
- Arithmetic precedence is in increasing order: '+', '-', '*', '/';
Evaluating a Postfix Expression. We describe how to parse and evaluate a postfix expression.
- We read the tokens in one at a time.
- If it is an integer, push it on the stack
- If it is a binary operator, pop the top two elements from the stack, apply the operator, and push the result back on the stack.
stack top() in C++ STL
C++Server Side ProgrammingProgramming
In this article, we will be discussing the working, syntax, and examples of stack::top() function in C++ STL.