![見出し画像](https://assets.st-note.com/production/uploads/images/13726260/rectangle_large_type_2_ad064a2c8f32da0e40da66d8f9d95c06.jpeg?width=1200)
Stack
A stack is an abstract data type that allows operations to store and remove values in a collection of elements. All operations have a runtime complexity of O(1) because you can only delete or add an element in the top of the stack. Elements are added in an order of LIFO (last in, first out).
Source: https://en.wikipedia.org/wiki/Stack_(abstract_data_type)
//C++ vector implementation of STACK
#include <iostream>
#include <vector>
using namespace std;
class Stack {
private:
int itr = 0;
vector<int> v;
int i;
public:
void put(int val) {
v.push_back(val);
itr++;
}
void pop() {
itr--;
if( itr >= 0 ) {
cout << "val removed : " << v[itr] << endl;
} else {
cout << "Cannot remove value because stack is empty" << endl;
}
}
void printVector() {
if( itr < 0 ) {
cout << "Vector is empty" << endl;
} else {
cout << "Current stack : ";
for(i = 0; i < itr; i++) {
cout << v[i] << " ";
}
cout << endl;
}
}
};
int main(void) {
Stack stack;
for(int i = 1; i <= 6; i++) {
stack.put(i);
stack.printVector();
}
for(int i = 0; i < 5; i++) {
stack.pop();
stack.printVector();
}
stack.pop();
return 0;
}
//C++ vector implementation of STACK with pointers and input stream
#include <iostream>
#include <vector>
using namespace std;
const int MAX_SIZE = 100; //Maximum size of stack
int sp = 0; //stack pointer
vector<int> stack(MAX_SIZE); //Stack
bool push(int *n) {
if( sp < MAX_SIZE ) {
stack[sp] = *n;
cout << "Putting in" << endl;
cout << "stack[" << sp << "] = " << *n << endl;
sp++;
return true;
} else {
cout << "Stack is full. Current MAX_SIZE: " << MAX_SIZE << endl;
return false;
}
}
bool pop(int *n) {
if( sp > 0 ) {
sp--;
*n=stack[sp];
cout << "Removing" << endl;
cout << "stack[" << sp << "] = " << *n << endl;
return true;
} else {
cout << "Stack is empty." << endl;
return false;
}
}
int main(void) {
char c;
int i;
cout << "Stack begins!" << endl;
while(cin >> c) {
if(c=='i') {
cout << "Please type a number: ";
cin >> i;
push(&i);
}
if(c=='o') {
cout << "Please type a number: ";
pop(&i);
}
}
return 0;
}
In almost all programming languages, reliable, fast and efficient libraries for data structures and algorithms are provided to the programmers. Implementation of functions using the provided libraries is recommended instead of implementing it on your own, because the library is most often numerically optimized, well-written and bug-free. The stack implementation of the Standard Library Template (STL) is available in C++. For reference of what STL is, please visit the website below.
An example of stack written with STL.
//STACK written with STL
#include <iostream>
#include <stack>
using namespace std;
int main(void) {
stack<int> Stack;
for(int i = 1; i <= 6; i++) {
Stack.push(i);
cout << Stack.top() << " ";
}
cout << endl;
for(int i = 0; i <= 5; i++) {
cout << "Removing " << Stack.top() << endl;
Stack.pop();
}
cout << endl;
return 0;
}
Stack with four basic operations
For instance, let's say we are adding the first two numbers on a stack, then subtracting the following two numbers, and finally multiplying the two numbers on top of the stack. The operation input stream can be written in a Reverse Polish Notation.
#Input: 1 2 + 3 4 - *
(Reverse Polish Notation)
Operation:
1) 1 + 2 = 3
2) 3 - 4 = -1
3) 3 * -1 = -3
#Output: -3
#include <iostream>
#include <sstream>
using namespace std;
const int N = 100;
int S[N] = {};
int top;
void initialize( void ) {
int top = 0;
}
bool isFull( void ) {
if( top == N ) {
return true;
} else return false;
}
bool isEmpty( void ) {
if( top == 0 ) {
return true;
} else return false;
}
int push( int x ) {
if( isFull() ) {
cout << "Stack full! Overflow" << endl;
exit(1); //Overflow
} else {
S[++top] = x;
return x;
}
}
int pop( ) {
if( isEmpty() ) {
cout << "Stack empty! Underflow" << endl;
exit(2); //Underflow
} else {
top--;
return S[top+1];
}
}
int main (void) {
initialize();
char c[100];
int val1 = 0, val2 = 0; //Initialize val1 & val2
cout << "Stack begins!" << endl;
//Press CTRL+D for EOF on Linux or Mac machines
while(scanf("%s", c) != EOF) {
switch(c[0]) {
case '+':
val1 = pop();
val2 = pop();
push(val1 + val2);
break;
case '-':
val1 = pop();
val2 = pop();
push(val1 - val2);
break;
case '*':
val1 = pop();
val2 = pop();
push(val1 * val2);
break;
case '/':
val1 = pop();
val2 = pop();
push(val1 / val2);
break;
default:
push(atoi(c));
break;
}
}
cout << pop() << endl;
return 0;
}
Ref: Stack
この記事が気に入ったらサポートをしてみませんか?