Stack

A stack is an Abstract Data Type (ADT), commonly used in most programming

languages. It is named stack as it behaves like a real-world stack, for example – a deck
of cards or a pile of plates, etc.

A real-world stack allows operations at one end only. For example, we can place or
remove a card or plate from the top of the stack only.

This feature makes it FILO data structure. FILO

stands for first-in last-out. Here, the element which is
placed (inserted) first, is accessed last. In stack
terminology, insertion operation is called PUSH operation
and removal operation is called POP operation.

The underlying container may be one of the standard container class template or
some other specifically designed container class. This underlying container shall
support at least the following operations:

• empty – test whether container is empty;

• size – return size;
• top – access top element
• push – insert element to the back;
• pop – remove front element;

7 7 7

5 5 5 5 5
empty Push(5) Push(7) Push(2) Pop() Pop()

Push numbers into the stack and pop them in FILO order:
#include <cstdio>
#include <stack>
using namespace std;
 int main(void)
{
// Create an empty stack s.
stack<int> s;

// Push to the stack the squares of numbers from 1 to 100.

for (int i = 1; i <= 10; i++) [Link](i*i);

// Create stack t that equals to s using copy constructor

stack<int> t(s);

// Print the top element and the size of the stack

printf("Top element is %d\n", [Link]());
printf("Stack size is %d\n", [Link]());

// Print all stack elements, sequentially removing them from the top
while (![Link]())
{
printf("%d ", [Link]());
[Link]();
}
printf("\n");
return 0;
}

E-OLYMP 6122. Simple stack Design and implement the data structure “stack”.
Write the program to simulate the stack operations, implement all methods mentioned
below. The program reads the sequence of commands and executes the corresponding
operation. After processing each command the program must print one line of output.
The possible commands are:
• push n – Add to the stack the number n (value n is given after the
command). Print ok.
• pop – Remove the last element from the stack. Print the value of this
element.
• back – Print the value of the last element, not removing it from the stack.
• size – Print the number of elements in the stack.
• clear – Clear the stack and print ok.
• exit – Print bye and terminate.

It is guaranteed that the set of input commands satisfies the following

requirements: the maximum number of elements in the stack at any time does not
exceed 100, all commands pop and back are correct, that is, when executed the stack
contains at least one element.

Input. Each line contains a single command.

Output. For each command print on a separate line the corresponding result.
 Sample input Sample output
push 2 ok
push 3 ok
push 5 ok
back 5
size 3
pop 5
size 2
push 7 ok
pop 7
clear ok
size 0
exit bye

In this problem you need to simulate the stack.

Algorithm realization
Declare a stack.
stack<int> s;

Read a command str. Read the commands until the end of the file.
while(cin >> str)
{
if (str == "push")
{

Command push. Читаем число n и заносим его в стек. Выводим сообщение

“ok”.
cin >> n;
[Link](n);
cout << "ok" << endl;
} else
if (str == "pop")
{

Command pop. Print the number at the top of the stack. Delete the top element.
cout << [Link]() << endl;
[Link]();
} else
if (str == "back")
{

Command top. Print the number at the top of the stack.

cout << [Link]() << endl;
} else
 if (str == "size")
{

Command size. Print the size of the stack.

cout << [Link]() << endl;
} else
if (str == "clear")
{

Command clear. Delete the entire stack. Since C++ does not have a clear method
for the stack, we have to sequentially remove stack elements one by one.
while(![Link]()) [Link]();
cout << "ok" << endl;
} else
{

Command exit. Print “bye” and terminate the program.

cout << "bye" << endl;
break;
}
}
return 0;
}

E-OLYMP 5327. Bracket sequence The bracket sequence is a correct arithmetic

expression from which all numbers and operation signs have been removed. For
example,
1+(((2+3)+5)+(3+4))→((())())

Input. A sequence of opening and closing brackets is given. The length of the
sequence is no more than 4 * 106.

Output. Print “YES” if the bracket sequence is correct and “NO” otherwise.

Sample input 1 Sample output 1

((())()) YES

Sample input 2 Sample output 2

(() NO

Let’s declare a stack in which we will store only opening brackets. Upon receiving
each character, we perform the following operation with the stack:
• If the character ‘(‘ is encountered, we push it onto the stack;
• if the character ‘)’ is encountered, we pop an element from the stack. If the
stack is empty at this point, the sequence is not a bracket sequence (at some
point, the number of closing brackets exceeds the number of opening
brackets);
 At the end of processing the string, the stack should be empty.

We can simulate the stack using a single variable. Let the variable cnt store the
number of open brackets in the stack. Then, when pushing ‘(‘ onto the stack, we
perform the operation cnt++, and when removing an element from the stack, we
perform the operation cnt--.

Example
Let’s simulate the stack operations for the string “((())())” from the first
example.
( ( ( ) ) ( ) )

( ( ( (

( ( ( ( ( ( (

open 0 1 2 3 2 1 2 1 0

Algorithm realization
Read the input string.
cin >> s;

The variable cnt stores the number of current unclosed brackets (i.e., the number of
opening brackets for which corresponding closing brackets have not yet been
encountered).
The variable flag will be set to 1 if, at any iteration, the number of closing brackets
exceeds the number of opening brackets. Initially, we set flag = 0.
cnt = flag = 0;

Process the input string character by character, simulating stack operations.

for (i = 0; i < [Link](); i++)
{

Process the current character s[i].

if (s[i] == '(') cnt++; else cnt--;

If the number of closing brackets exceeds the number of opening brackets at any
iteration, then the input sequence is not a bracket sequence.
if (cnt < 0) flag = 1;
}
 Depending on the values of the variables flag and cnt, print the answer. The stack
will be empty at the end of processing the string if cnt = 0.
if (flag == 0 && cnt == 0)
cout << "YES\n"; else cout << "NO\n";

E-OLYMP 2479. Parentheses balance You are given a string consisting of

parentheses ( ) and [ ]. A string of this type is said to be correct:
• if it is the empty string
• if A and B are correct, AB is correct,
• if A is correct, (A) and [A] is correct.
Write a program that takes a sequence of strings of this type and check their
correctness. Your program can assume that the maximum string length is 128.

Input. The first line contains the number of test cases n. Each of the next n lines
contains the string of parentheses ( ) and [ ].

Output. For each test case print in a separate line “Yes” if the expression is correct
or “No” otherwise.

Sample input Sample output

3 Yes
([]) No
(([()]))) Yes
([()[]()])()

To solve the problem we’ll use stack of characters. We will process sequentially
the symbols of the input string and:
• if the current character is an opening parenthesis (round or square), push it
into the stack.
• if the current character is a closing bracket, then the corresponding opening
parenthesis must be at the top of the stack. If this is not the case, or if the
stack is empty, then the expression is not correct.
At the end of processing the correct line, the stack should be empty.

Example
Let’s simulate the stack for the string “( ( [ ] ) [ ] )”.
 ( ( [ ] ) [ ] )

( ( ( [

( ( ( ( ( ( (

E-OLYMP 5060. Reverse Polish notation Reverse Polish notation (RPN) is a

mathematical notation in which every operator follows all of its operands. It is also
known as postfix notation and does not need any parentheses as long as each operator
has a fixed number of operands.

For example:
• the expression 2 + 4 in RPN is represented like 2 4 +
• the expression 2 * 4 + 8 in RPN is represented like 2 4 * 8 +
• the expression 2 * (4 + 8) in RPN is represented like 2 4 8 + *
Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid
operators are +, -, *, /. Operator / is an integer division (14 / 3 = 4). Each operand may
be an integer or another expression.

Input. One line contains expression written in Reverse Polish notation. The length
of expression is no more than 100 symbols.

Output. Print the value of expression given in Reverse Polish notation.

Sample input 1 Sample output 1

2 4 * 8 + 16

Sample input 2 Sample output 2

2 4 8 + * 24

Let’s partition the input expression into terms, which are the number or one of the
four operators. The terms will be processed as follows:
• if term is a number, push it into stack;
• if term is an operator, extract two numbers from the stack, perform the
operation and push the result into stack.
When the expression is processed, the stack contains one number that is the result
of calculations.
 Example
The expression “2 4 * 8 +” is equivalent to “2 * 4 + 8”.

2 4 * 8 +

4 8

2 2 8 8 16

The expression “2 4 8 + *” is equivalent to “2 * (4 + 8)”.

2 4 8 + *

4 4 12

2 2 2 2 24

E-OLYMP 940. Majority element Given an array of size n, find the majority
element. The majority element is the element that appears more than n / 2 times.

Input. The first line contains number n (1 ≤ n ≤ 100). The second line contains n
positive integers.

Output. If the array contains majority element, then print it. Otherwise print -1.

Sample input 1 Sample output 1

7 3
3 3 5 4 2 3 3

Sample input 2 Sample output 2

4 -1
2 3 2 3

Let x be the majority element. We start processing the input numbers. Each number
equal to x we shall push onto the stack. When a number not equal to x is received, we
shall pop one number from the stack. Then at the end of processing the data, the top of
the stack will contain the majority element.
 Initially clear the stack. When processing the next element a:
• If stack is empty, then push(a);
• If the top of the stack contains number a, then push(a);
• If the top of the stack contains number other than a, then pop();

If at the end of processing all the numbers in array, the top of the stack contains
some number x (if stack is empty, then there is no majority element), then it should be
checked if it is a majority element. To do this, count how many times the number x
appears in the original array. If x appears more than n / 2 times, then the answer is
affirmative.

At any time stack contains only one element (possibly multiple times), so let’s
simulate the stack with two variables:
• maj – number in the stack;
• cnt – number of times the number maj appears in the stack;

Example
Consider the first sample.
3 3 5 4 2 3 3

3 3 3 2 3

maj - 3 3 3 - 2 - 3
cnt 0 1 2 1 0 1 0 1
At the end of the algorithm the stack contains 3. Let's check if it is a majority
element. To do this, we need to count how many times the number 3 appears in the
original array. The number 3 appears 4 times in the array of length n = 7. Since 4 >
7 / 2 , the number 3 is a majority element.

Algorithm realization
Store the input sequence in array m.
int m[110];

Declare variables maj and cnt to simulate the stack:

• maj is the number in the stack;
• cnt is the number of times the number maj is present in the stack;
int maj, cnt;
 Read the input data.
scanf("%d",&n);
for(i = 0; i < n; i++)
scanf("%d",&m[i]);

Initially set the stack to be empty.

maj = 0; cnt = 0;

Process the input numbers. Simulate the stack.

for(int i = 0; i < n; i++)
{

If stack is empty (cnt = 0), push m[i] into it.

if (cnt == 0) {maj = m[i]; cnt++;}

If the current element m[i] matches the top of the stack maj, then push m[i] onto
the stack.
else if (m[i] == maj) cnt++;

Otherwise pop element from the stack.

else cnt--;
}

In the variable cnt count how many times the number maj appears in the array m.
cnt = 0;
for(int i = 0; i < n; i++)
if (m[i] == maj) cnt++;

If cnt > n / 2 , then the majority element exists. Otherwise it does not (res will be
assigned -1).
if(2 * cnt > n) res = maj; else res = -1;

Print the answer.

printf("%d\n",res);

E-OLYMP 4259 Minimum in the stack Implement a data structure with the next
operations:
1. Push x to the end of the structure.
2. Pop the last element from the structure.
3. Print the minimum element in the structure.
Input. The first line contains the number of operations n (1 ≤ n ≤ 106). Each of the
next n lines contains one operation. The i-th line contains the number ti – the type of
operation:
 • 1 in the case of a push operation;
• 2 in the case of a pop operation;
• 3 if the operation asks to find the minimum;
In the case of a push operation, next comes the integer x (-109 ≤ x ≤ 109) – element
to be inserted into the structure. It is guaranteed that before each pop or getMin
operation the structure is not empty.

Output. For each getMin operation, print on a separate line one number – the
minimal element in the structure.

Sample input Sample output

8 -3
1 2 2
1 3 2
1 -3
3
2
3
2
3

Obviously, the required data structure is the stack. Since the number n of
operations with stack is no more than 106, we will choose a static array of the specified
length as its container.
The pop() method will be modeled as usual by removing the top element of the
stack, and the push(x) method will be rewritten as follows:
• If the stack is empty, push x to the stack;
• Otherwise, push to the stack the minimum between x and the current value
of its top.
Thus, the minimum element of the stack will always be at the top. At the same
time, we lose the values pushed onto the stack, although in reality they are not needed
for further requests.

Minimum
2 element is on
3 3 the top of the
3 3 3 stack
5 5 5 5

push(5) push(3) push(8) push(2)

content of
5 5, 3 5, 3, 8 5, 3, 8, 2 structure
min(8, 3) = 3
When we process number 8, we push min (8, 3) = 3 at the top of the stack.
 E-OLYMP 11456 Next greater element Given an array, print the Next Greater
Element for every element.
The Next Greater Element for an element x is the first greater element on the
right side of x in the array. Elements for which no greater element exist, consider the
next greater element as -1.

Input. The first line contains number n (n ≤ 105). The second line contains n
positive integers, each not greater than 109.

Output. For each element of input array print the Next Greater Element.

Sample input Sample output

10 8 8 -1 7 -1 7 3 3 7 -1
5 3 8 5 7 4 2 1 3 7

Let’s declare a stack of integers that will store information about the next greater
elements. We’ll process the numbers sequentially from right to left. When processing
the i-th number:
• remove from the stack the numbers not greater than the i-th number;
• the number at the top of the stack will be the next element greater than the i -
th number. If stack is empty, then the next greater element is -1;
• push the i-th number into the stack;

At any moment of time, stack stores numbers in descending order. When the next
number arrives, all numbers not greater than it are removed from the stack. After that,
the new number takes place at the top of the stack.

Example
Consider the processing of numbers from the example.
 8
7 7
5 5
4
3 3
2
1
0 1 2 3 4 5 6 7 8 9

2 1

5 3 5 4 3 3 3

8 8 8 7 7 7 7 7 7 7

8 8 -1 7 -1 7 3 3 7 -1

E-OLYMP 10379 Maximum frequency stack Design a stack-like data structure

to push elements to the stack and pop the most frequent element from the stack. The
possible commands are:
• push n – pushes an integer n onto the top of the stack;
• pop – removes and prints the most frequent element in the stack. If there is a
tie for the most frequent element, the element closest to the stack’s top is
removed and printed.

Input. Each line contains a single command.

Output. For each pop command print on a separate line the corresponding result.

Sample input 1 Sample output 1

push 4 4
push 5 5
push 4 7
push 6
push 7
pop
push 5
pop
pop

Sample input 2 Sample output 2

push 5 3
push 3 9
push 1 1
 push 3 3
push 9 5
pop
pop
pop
pop
pop

For each number x we’ll store the number of times freq[x] that it occurs in the
stack. Let’s choose a map as a data structure for freq.
Declare an array of stacks vector<stack<int>> st. Here st[i] stores elements that
occur on the stack i + 1 times (the numbering of cells in the st array starts from zero).
The order in which the elements are in st[i] matches the order in which they are pushed
onto the stack.
Let the number x be pushed to the stack for the k-th time. If the element st[k – 1]
does not exist, then add (push_back) the element to the st array. Then push x to the top
of the stack st[k – 1].
push 5
push 4 6
push 6
push 4 5 5
push 5 4 4 4
push 4
st0 st1 st2
When you delete element, you must pop the item from the top of the last stack.
pop
push 5
push 4 6
push 6
push 4 5 5
push 5 4 4 4
push 4
st0 st1 st2
For example, if in the future there are only pop operations, then the elements from
the stack will be removed in the following order: 4, 5, 4, 6, 5, 4.

Example
Consider the order in which elements are pushed into array of stacks for the next
example.
 push 2
push 1 2
push 1
push 5 6
push 6
push 1 1 1 1
push 5 5 5 5
push 5
st0 st1 st2
When removed, items will be popped from the stack in the following order: 1, 5, 1,
5, 2, 6, 1, 5.